Иҷозати ҳалли Leetcode  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon себ Atlassian Блумберг ByteDance мехаранд Facebook Гарена GoDaddy Голдман Sachs Google LinkedIn Microsoft Oracle Salesforce 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  

Иҷозати ҳалли Leetcodeпайвандак

Масъалаи 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

Кодекси Java барои ҳалли Permutations Leetcode

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 - ивазкунии к ё ивазкунии қисман. Ба таври расмӣ, P (N, k) = (N!) / ((Nk)!).

ҳамчунин нигаред
Ду массивро бо роҳи баргардонидани зерқаторҳои Leetcode Solution баробар кунед

Мураккабии фазо

О (Н!), зеро мо бояд ҳамаи ҳалли имконпазирро, ки N! ба андозае, ки N андозаи массив аст.