პერმუტაციები Leetcode Solution


Რთული ტური საშუალო
ხშირად ეკითხებიან Adobe Amazon Apple Atlassian Bloomberg ByteDance eBay Facebook გარენა მიდი მამიკო Goldman Sachs Google LinkedIn microsoft Oracle Salesforce SAP Uber VMware Walmart Labs Yahoo
Backtracking

პრობლემა 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 გზა არსებობს.

უკუკავშირის მიდგომა პერმუტაციებისთვის Leetcode Solution

პერმუტაციები Leetcode Solution

პრობლემა Permutations Leetcode Solution გვთხოვდა მოცემული თანმიმდევრობის ყველა პერმუტაციის შექმნას. საერთოდ, ჩვენგან ვალდებულნი ვართ გამოვიყენოთ პერმუტაცია, ან რიგი თანმიმდევრობის რეკურსია. მაგრამ აქ რეკურსია ან უკან დახევა ცოტა სახიფათოა. ერთ-ერთი გზა შეიძლება ყოფილიყო არააკრეფილი ელემენტის ელემენტის არჩევა და პასუხის ბოლოს დასმა. ამ გზით წარმოიქმნება პერმუტაცია და რატომღაც დარწმუნდით, რომ გახსოვთ, რომ ეს პერმუტაცია წარმოიშვა და არ უნდა განმეორდეს. ამის ნაცვლად, ჩვენ ვცდილობთ ვიპოვოთ ამოცანის შესრულების მარტივი გზა. რა მოხდება, თუ ჩვენ აირჩევთ ელემენტს და შევცვლით მას მიმდინარე ელემენტთან. შემდეგ გააკეთეთ რეკურსიული ზარი, რათა წარმოიქმნას ყველა ჩანაცვლება მიმდევრობის ერთი ინდექსის მიმდინარე ინდექსის შემდეგ

მას შემდეგ, რაც ჩვენ დასრულდა permutations ერთი ინდექსი წინ. ჩვენ ამოვიღებთ არჩეულ ელემენტს, შემდეგ კი ვიღებთ სხვა ელემენტს და ვიმეორებთ პროცედურას. ამ გზით ჩვენ დარწმუნდებით, რომ თითოეული გამოუყენებელი ელემენტი ერთხელ მაინც მოვათავსეთ ამჟამინდელ მდგომარეობაში. და რადგან რეკურსიული ზარი მივიღეთ უფრო მცირე ქვეპრობლემისკენ. მომცრო ქვეპროგრამა წარმოქმნის მიმდევრობის მნიშვნელობას მიმდინარე ინდექსის შემდეგ. მიმდინარე პერმუტაციისთვის ამ პერმუტაციების დამატება ასრულებს პერმუტაციის ნაკრს და მიმდინარე ინდექსში მითითებული ელემენტით. ამ გზით ჩვენ განვაგრძობთ მასივის გადახედვას მარცხნიდან მარჯვნივ და დაყოფთ პრობლემას უფრო მცირე ქვეპროგრამებად. საჭიროების დადგომისთანავე შევქმენით შესაძლო პერმუტაცია და ვამატებთ პასუხს.

უკუკავშირის კოდი

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

Java კოდი პერმუტაციებისთვის Leetcode Solution

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)!).

სივრცის სირთულე

O (N!), ვინაიდან ჩვენ უნდა შევინახოთ ყველა შესაძლო გადაწყვეტილება, რომელიც არის N! ზომით, სადაც N არის მასივის ზომა.