Permutasiyalar Leetcode Solution

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Atlassian Bloomberg ByteDance eBay Facebook Garena GoDaddy Goldman Sachs google LinkedIn microsoft Kahin Salesforce SAP Über VMware Walmart Laboratoriyaları Yahoo
alqoritmlər Geri qayıtma kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 41

Problem Permutations Leetcode Həlli sadə bir sıra ardıcıllığı təmin edir və tam bir vektor qaytarmağımızı xahiş edir. array verilmiş ardıcıllığın bütün permutasiyalarından. Beləliklə, problemin həllinə başlamazdan əvvəl. Yer dəyişdirmələri ilə tanış olmalıyıq. Beləliklə, permutasiya verilmiş tam ədədlərin düzülüşündən başqa bir şey deyildir. Beləliklə, bir ardıcıllığın bütün permütasiyalarına ehtiyacımız olduğunu söylədikdə. Verilən ardıcıllığın bütün mümkün tənzimləmələrini çap etməyimizi və ya geri qaytarmağımızı tələb etdiyimizi ifadə edirik. Daha yaxşı başa düşmək üçün bir neçə nümunəyə nəzər salaq.

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

İzahat: 1, 2, 3 ardıcıllıqla yazmağın bütün yolları nəticə olaraq verilmişdir. Yer dəyişdirmədə 6, 1, 2 yazmağın cəmi 3 yolu var.

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

İzahat: 2, 0 yazmağın yalnız 1 yolu var.

Permutasiyalar Leetcode Həlli üçün Backtracking Yanaşması

Permutasiyalar Leetcode SolutionPin

Permutations Leetcode Solution problemi, verilən ardıcıllığın bütün permutasiyalarını yaratmağımızı istədi. Ümumiyyətlə, biz bir permütasiya yaratmalıyıq və ya bir sıra ardıcıllıqla rekursiya etmək üçün açardır. Ancaq burada rekursiya və ya geri çəkilmə biraz çətindir. Bir yolu seçilməmiş elementlərdən bir element seçib cavabın sonunda yerləşdirmək olardı. Bu yolla bir permütasiya yaradır və birtəhər bu permütasiyanın yaradıldığını və təkrarlanmamalı olduğunu xatırlamağa əmin olun. Ancaq bunu etmək əvəzinə tapşırığı yerinə yetirmək üçün sadə bir yol tapmağa çalışırıq. Bir element seçib cari elementlə dəyişdirsək nə olar. Sonra cari indeksdən sonra bir indeks ardıcıllığı üçün bütün permütasiyaları yaratmaq üçün rekursiv bir zəng edin.

Bir dəfə bir indeks qabaqda permütasiyalar yaratmaqla işimiz bitdi. Seçilmiş elementi çıxarırıq və sonra başqa bir element seçib proseduru təkrarlayırıq. Beləliklə, istifadə olunmayan hər bir elementi ən azı bir dəfə mövcud vəziyyətə qoyduğumuza əminik. Və daha kiçik bir alt problemə rekursiv bir zəng etdiyimiz üçün. Cari indeksdən dərhal sonra başlayan ardıcıllıq üçün permütasiya yaradan daha kiçik alt problem. Bu permutasiyaların cari permutasiyaya əlavə edilməsi cari indeksdə müəyyən edilmiş bir element ilə bir sıra permutation tamamlayır. Bu şəkildə massivi soldan sağa keçir və problemi daha kiçik alt problemlərə ayırırıq. Ehtiyacımıza çatdıqdan sonra mümkün permütasiya yaratdıq və bunu cavaba əlavə edirik.

Kod geri qayıt

Permutations Leetcode Solution üçün C ++ kodu

#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

Permutasiyalar üçün Java Kodu 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]]

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (Sigma (P (N, K)), burada P n və ya qismən permutasiyanın k permütasiyasıdır. Daha rəsmi olaraq P (N, k) = (N!) / ((Nk)!).

Kosmik Mürəkkəblik

O (N!), çünki N olan bütün mümkün həlləri saxlamalıyıq! ölçüdə, burada N massivin ölçüsüdür.

Şərh yaz

Translate »
1