Տեղափոխումներ Leetcode լուծում  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon խնձոր Atlassian Bloomberg ByteDance eBay facebook Garena Godaddy Goldman Sachs-ը Google LinkedIn Microsoft Պատգամախոս Salesforce SAP Uber VMware Walmart Labs Անտաշ անասուն նողկալի արարած
ալգորիթմները Հետադարձ կապ կոդավորում հարցազրույց հարցազրույցի պատրաստում 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 լուծման համար  

Տեղափոխումներ Leetcode լուծումPin

Permutations Leetcode Solution- ի խնդիրը խնդրեց մեզ առաջացնել տվյալ հաջորդականության բոլոր փոխարկումները: Ընդհանրապես, մեզանից պահանջվում է փոխակերպում առաջացնել, կամ հաջորդականության ինչ-որ հետադարձ կատարելու բանալին է: Բայց այստեղ հետընթացը կամ հետընթացը մի փոքր բարդ է: Մի եղանակ կարող էր լինել չընտրված տարրերից տարր ընտրել և տեղադրել այն պատասխանի վերջում: Այս եղանակով առաջանում է փոխարկում և ինչ-որ կերպ համոզվեք, որ հիշեք, որ այս փոխարկումն առաջացել է և չպետք է կրկնվի: Բայց սա անելու փոխարեն, մենք փորձում ենք գտնել առաջադրանքը կատարելու պարզ միջոց: Ինչ անել, եթե մենք ընտրենք մի տարր և փոխենք այն ընթացիկ տարրի հետ: Դրանից հետո կատարեք ռեկուրսիվ զանգ ՝ ընթացիկ ցուցիչից հետո հաջորդականության մեկ ցուցանիշի բոլոր փոխարկումները առաջ բերելու համար:

Տես նաեւ,
Միաձուլեք երկու տեսակավորված կապված ցուցակները

Երբ ավարտենք տեղաշարժերը մեկ ցուցանիշով առաջ: Մենք հեռացնում ենք վերցված տարրը, այնուհետև ընտրում ենք մեկ այլ տարր և կրկնում ենք ընթացակարգը: Այս կերպ մենք համոզվում ենք, որ յուրաքանչյուր չօգտագործված տարր գոնե մեկ անգամ տեղադրել ենք ներկայիս դիրքում: Եվ քանի որ մենք հետադարձ զանգ կատարեցինք ավելի փոքր ենթախնդրի: Ընթացիկ ինդեքսից անմիջապես հետո սկսվող հաջորդականության փոխարկումն առաջացնող փոքր ենթածրագիրը: Այդ փոխարկումները ընթացիկ փոխադարձությանն ավելացնելը լրացնում է փոխարկումների ամբողջությունը `ընթացիկ ինդեքսում տեղադրված տարրով: Այս եղանակով մենք անընդմեջ նետում ենք զանգվածը ձախից աջ և խնդիրը բաժանում ավելի փոքր ենթախնդիրների: Կարիքին հասնելուն պես մենք առաջացրել ենք հնարավոր փոխարկում և այն ավելացնում ենք պատասխանի:

Հետադարձ կոդ  

C ++ ծածկագիր Permutations Leetcode Solution- ի համար

#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]]

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (սիգմա (P (N, K)), որտեղ P- ն n- ի կամ մասնակի փոխարկման k փոխադարձությունն է: Ավելի պաշտոնական ՝ P (N, k) = (N!) / ((Nk)!):

Տես նաեւ,
Կատարի՛ր հավասար երկու հավասարաչափ ՝ հետադարձ զանգվածը փոխելով Leetcode լուծումը

Տիեզերական բարդություն

ՎՐԱ!), քանի որ մենք պետք է պահենք բոլոր հնարավոր լուծումները, որոնք N! չափով, որտեղ N - զանգվածի չափը: