ໃບອະນຸຍາດ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Atlassian Bloomberg ByteDance eBay ເຟສບຸກ Garena GoDaddy Goldman Sachs ກູໂກ LinkedIn Microsoft Oracle Salesforce SAP Uber VMware Walmart Labs Yahoo
Backtracking

The Permutations Leetcode Solution ບັນຫາ ລຳ ດັບແບບງ່າຍດາຍຂອງ ຈຳ ນວນເຕັມແລະຂໍໃຫ້ພວກເຮົາກັບຄືນຮູບ vector ເຕັມຫລື array ຂອງການອະນຸຍາດທັງ ໝົດ ຂອງ ລຳ ດັບດັ່ງກ່າວ. ສະນັ້ນ, ກ່ອນຈະແກ້ໄຂບັນຫາ. ພວກເຮົາຄວນຄຸ້ນເຄີຍກັບການອະນຸຍາດ. ສະນັ້ນ, ການອະນຸຍາດແມ່ນບໍ່ມີຫຍັງນອກ ເໜືອ ຈາກການຈັດ ຈຳ ນວນທີ່ໃຫ້ໄວ້. ດັ່ງນັ້ນ, ເມື່ອພວກເຮົາເວົ້າວ່າພວກເຮົາຕ້ອງການການອະນຸຍາດທັງ ໝົດ ຕາມ ລຳ ດັບ. ພວກເຮົາ ໝາຍ ຄວາມວ່າພວກເຮົາ ຈຳ ເປັນຕ້ອງໄດ້ພິມຫລືສົ່ງຄືນການຈັດການທີ່ເປັນໄປໄດ້ທັງ ໝົດ ຂອງ ລຳ ດັບ. ຂໍໃຫ້ພິຈາລະນາບາງຕົວຢ່າງເພື່ອຄວາມເຂົ້າໃຈທີ່ດີຂື້ນ.

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.

ວິທີການ Backtracking ສໍາລັບການອະນຸຍາດ Leetcode Solution

ໃບອະນຸຍາດ Leetcode

ບັນຫາການອະນຸຍາດ Leetcode Solution ໄດ້ຂໍໃຫ້ພວກເຮົາສ້າງໃບອະນຸຍາດທັງ ໝົດ ຕາມ ລຳ ດັບ. ໂດຍທົ່ວໄປແລ້ວ, ພວກເຮົາມີຄວາມ ຈຳ ເປັນທີ່ຈະຕ້ອງສ້າງບົດອະນຸຍາດຫລືການຮຽກຄືນບາງ ລຳ ດັບແມ່ນກຸນແຈທີ່ຈະຕ້ອງໄປ. ແຕ່ໃນທີ່ນີ້ການເອີ້ນຄືນຫລືການເລົ່າຄືນ ໃໝ່ ແມ່ນເປັນເລື່ອງຍາກ. ວິທີ ໜຶ່ງ ອາດແມ່ນການເລືອກເອົາອົງປະກອບ ໜຶ່ງ ຈາກອົງປະກອບທີ່ບໍ່ໄດ້ວາງແຜນໄວ້ແລະວາງມັນໄວ້ໃນຕອນທ້າຍຂອງ ຄຳ ຕອບ. ວິທີການນີ້ຈະສ້າງການອະນຸຍາດແລະເຮັດໃຫ້ແນ່ໃຈວ່າຈື່ໄດ້ວ່າການອອກ ກຳ ລັງກາຍນີ້ໄດ້ຖືກສ້າງຂື້ນແລະບໍ່ຄວນເຮັດຊ້ ຳ ອີກ. ແຕ່ແທນທີ່ຈະເຮັດສິ່ງນີ້, ພວກເຮົາພະຍາຍາມຊອກຫາວິທີງ່າຍໆໃນການປະຕິບັດວຽກງານ. ຈະເປັນແນວໃດຖ້າພວກເຮົາເລືອກເອົາອົງປະກອບແລະແລກປ່ຽນກັບອົງປະກອບປັດຈຸບັນ. ຫຼັງຈາກນັ້ນ, ເຮັດການເອີ້ນຄືນເພື່ອສ້າງທຸກໆການອະນຸຍາດ ສຳ ລັບ ລຳ ດັບ ໜຶ່ງ ຫຼັງຈາກດັດສະນີປັດຈຸບັນ.

ເມື່ອພວກເຮົາເຮັດ ສຳ ເລັດແລ້ວກັບການສ້າງໃບອະນຸຍາດໃຫ້ດັດສະນີ ໜຶ່ງ ຂ້າງ ໜ້າ. ພວກເຮົາເອົາອົງປະກອບທີ່ຖືກເກັບອອກມາ, ແລະຈາກນັ້ນເລືອກເອົາອົງປະກອບອື່ນແລະເຮັດຂັ້ນຕອນ ໃໝ່. ວິທີນີ້ພວກເຮົາຮັບປະກັນວ່າພວກເຮົາໄດ້ຈັດວາງແຕ່ລະອົງປະກອບທີ່ບໍ່ໄດ້ໃຊ້ຢ່າງ ໜ້ອຍ ໜຶ່ງ ຄັ້ງໃນ ຕຳ ແໜ່ງ ປະຈຸບັນ. ແລະນັບຕັ້ງແຕ່ພວກເຮົາໄດ້ຮຽກຮ້ອງກັບຄືນໄປຫາໂຄງການຍ່ອຍທີ່ນ້ອຍກວ່າ. ໂຄງຮ່າງຍ່ອຍຂະ ໜາດ ນ້ອຍ ກຳ ລັງສ້າງການອະນຸມັດ ສຳ ລັບ ລຳ ດັບເລີ່ມຕົ້ນຫຼັງຈາກດັດສະນີປັດຈຸບັນ. ການເພີ່ມການອະນຸຍາດເຫລົ່ານັ້ນເຂົ້າໃນການອະນຸຍາດໃນປະຈຸບັນແມ່ນ ສຳ ເລັດການຕັ້ງຄ່າອະນຸຍາດກັບອົງປະກອບທີ່ ກຳ ນົດໄວ້ໃນດັດຊະນີປັດຈຸບັນ. ວິທີນີ້ພວກເຮົາຈະສືບຕໍ່ຜ່ານແຖວຈາກຊ້າຍຫາຂວາແລະແບ່ງປັນບັນຫາອອກເປັນໂຄງການນ້ອຍໆ. ເມື່ອພວກເຮົາບັນລຸຄວາມຕ້ອງການທີ່ພວກເຮົາໄດ້ສ້າງການອະນຸຍາດທີ່ເປັນໄປໄດ້ແລະພວກເຮົາເພີ່ມມັນໃສ່ ຄຳ ຕອບ.

ລະຫັດ Backtracking

ລະຫັດ C ++ ສຳ ລັບໃບອະນຸຍາດ 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 (Sigma (P (N, K)), ບ່ອນທີ່ P ແມ່ນ permutation k ຂອງ n ຫຼືບາງສ່ວນຂອງການອະນຸຍາດ. ຢ່າງເປັນທາງການ, P (N, k) = (N!) / ((Nk)!).

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N!), ເນື່ອງຈາກວ່າພວກເຮົາຕ້ອງເກັບຮັກສາທຸກວິທີທາງທີ່ເປັນໄປໄດ້ເຊິ່ງແມ່ນ N! ໃນຂະ ໜາດ ທີ່ N ແມ່ນຂະ ໜາດ ຂອງຂບວນ.