Permutations Leetcode шешімі  


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon алма Atlassian Bloomberg ByteDance еВау Facebook Гарена GoDaddy Голдман Сакс Google LinkedIn Microsoft Oracle Salesforce SAP қиятын 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

Permutations 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 (Сигма (P (N, K)), мұндағы P - n-нің немесе ішінара ауыстырудың k ауыстыруы. Ресми түрде P (N, k) = (N!) / ((Nk)!).

Сондай-ақ, қараңыз
Leitcode шешімінің ішкі жиымдарын кері айналдыру арқылы екі массивті теңестіріңіз

Ғарыштың күрделілігі

O (N!), өйткені біз барлық мүмкін шешімдерді сақтауымыз керек! өлшемде, мұндағы N - массивтің өлшемі.