Permutations Leetcode шийдэл  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Apple-ийн Atlassian Bloomberg БайтДанс Ebay Facebook-ийн Гарена GoDaddy Goldman Sachs Google-ийн LinkedIn Microsoft- Oracle-ийн Борлуулалтын хүч SAP Uber VMware Walmart лабораторууд Yahoo
алгоритмууд Буцах кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions

Permutations Leetcode Solution гэсэн асуудал нь бүхэл тоонуудын энгийн дарааллыг гаргаж, бүрэн векторыг буцааж өгөхийг биднээс хүсдэг. массив өгөгдсөн дарааллын бүх сэлгэлтийн. Тиймээс, асуудлыг шийдэхээс өмнө. Бид сэлгээлтийг мэддэг байх ёстой. Тиймээс сэлгэх нь өгөгдсөн бүхэл тоонуудын зохион байгуулалтаас өөр зүйл биш юм. Тиймээс бид дарааллын бүх сэлгэлт хэрэгтэй гэж хэлэхэд. Бид өгөгдсөн дарааллын бүх боломжит зохицуулалтыг хэвлэх эсвэл буцааж өгөх шаардлагатай байна гэсэн үг юм. Илүү сайн ойлгохын тулд цөөн хэдэн жишээг авч үзье.

Given sequence: [1,2,3]
Permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Тайлбар: 1, 2, 3-ийг дараалан бичиж болох бүх арга замыг гаралт хэлбэрээр өгсөн болно. 6, 1, 2-ийг сэлгэн бичих нийт 3 арга байдаг.

[0,1]
[[0,1],[1,0]]

Тайлбар: 2, 0 гэж бичих ердөө 1 арга бий.

Permutations Leetcode Solution-т буцах хандлага  

Permutations Leetcode шийдэл

Permutations Leetcode Solution-ийн асуудал нь өгөгдсөн дарааллын бүх сэлгэлтийг бий болгохыг биднээс хүссэн юм. Ерөнхийдөө бид сэлгээ хийхийг шаарддаг эсвэл зарим дарааллын рекурс хийх нь хамгийн чухал зүйл юм. Гэхдээ энд рекурс хийх буюу ухрах нь жаахан зальтай юм. Нэг арга нь сонгоогүй элементүүдээс элементийг сонгож, хариултынхаа төгсгөлд байрлуулж болох байсан. Энэ арга нь сэлгэлт үүсгэж, энэ сэлгэлт үүссэн тул дахин давтах ёсгүй гэдгийг санах хэрэгтэй. Гэхдээ үүнийг хийхийн оронд бид даалгаврыг гүйцэтгэх энгийн аргыг олохыг хичээдэг. Хэрэв бид элемент сонгоод одоогийн элементтэй нь сольж байвал яах вэ. Дараа нь рекурсив дуудлага хийж, одоогийн индексийн дараа нэг индексийн дарааллын бүх сэлгэлтийг үүсгэнэ.

мөн үзнэ үү
Хоёр эрэмбэлэгдсэн холбосон жагсаалтыг нэгтгэх

Нэг индексийн өмнө сэлгэлт хийж дууссаны дараа. Бид сонгосон элементийг арилгаж дараа нь өөр элементийг сонгоод процедурыг давтана. Ингэснээр бид ашиглагдаагүй элемент бүрийг одоогийн байрлалд дор хаяж нэг удаа байрлуулсан эсэхийг шалгана. Бид жижиг дэд асуудалд рекурсив дуудлага хийснээс хойш. Жижиг дэд асуудал нь одоогийн индексийн дараа эхлэх дарааллын сэлгэлтийг үүсгэдэг. Эдгээр сэлгэлтүүдийг одоогийн сэлгэлтэд нэмснээр тухайн үеийн индекс дээр тохируулсан элемент бүхий сэлгэлтийн багцыг дуусгаж өгдөг. Энэ аргаар бид массивыг зүүнээс баруун тийш дайран өнгөрч, асуудлыг жижиг дэд асуудал болгон хуваадаг. Шаардлагатай болсны дараа бид боломжит сэлгэлтийг үүсгэсэн бөгөөд үүнийг хариултанд нэмнэ.

Буцах мөр  

Permutations Leetcode Solution-ийн C ++ код

#include <bits/stdc++.h>
using namespace std;

void permutationUtil(vector<int> &nums, int i, int &numsSize, vector<vector<int>> &answer){
    if(i == numsSize){
        answer.push_back(nums);
    }
    for(int j = i; j < numsSize; j++){
        swap(nums[i], nums[j]);
        permutationUtil(nums, i+1, numsSize, answer);
        swap(nums[i], nums[j]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> answer;
    int numsSize = nums.size();
    permutationUtil(nums, 0, numsSize, answer);
    return answer;
}

int main(){
    vector<int> nums({1, 2, 3});
    vector<vector<int>> answer = permute(nums);
    for(auto i: answer){
        for(auto j: i)
            cout<<j<<" ";
        cout<<"\t";
    }
}
1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2

Зөвшөөрлийн Leetcode шийдлийн Java код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void permutationUtil(List<Integer> nums, int i, int numsSize, List<List<Integer>> answer){
        if(i == numsSize){
            answer.add(new ArrayList<Integer>(nums));
        }
        for(int j = i; j < numsSize; j++){
            Collections.swap(nums, i, j);
            permutationUtil(nums, i+1, numsSize, answer);
            Collections.swap(nums, i, j);
        }
    }
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new LinkedList();
        int numsSize = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<numsSize;i++)
            list.add(nums[i]);
        permutationUtil(list, 0, numsSize, answer);
        return answer;
    }
 
    public static void main(String[] args){
    	int nums[] = {1, 2, 3};
    	List<List<Integer>> answer = permute(nums);
    	System.out.println(answer.toString());
    }
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (Sigma (P (N, K))), энд P нь n-ийн k сэлгэлт эсвэл хэсэгчилсэн сэлгэлт юм. Илүү албан ёсоор P (N, k) = (N!) / ((Nk)!).

мөн үзнэ үү
Leetcode шийдлийн дэд массивыг буцааж хоёр массивыг тэнцүү болго

Сансрын нарийн төвөгтэй байдал

O (N!), Учир нь бид N гэсэн бүх боломжит шийдлүүдийг хадгалах ёстой. хэмжээтэй бол N нь массивын хэмжээ юм.