ការអនុញ្ញាតដំណោះស្រាយឡេឡេកូដ

សំណួរសំភាសន៍រចនាប្រព័ន្ធ អាចជាការបើកចំហរ ដូច្នេះវាពិបាកពេកក្នុងការដឹងពីវិធីត្រឹមត្រូវក្នុងការរៀបចំ។ ឥឡូវនេះខ្ញុំអាចបំបែកការរចនានៃ Amazon, Microsoft និង Adobe បន្ទាប់ពីទិញ សៀវភៅ​នេះ. ពិនិត្យឡើងវិញប្រចាំថ្ងៃ សំណួររចនា ហើយខ្ញុំសន្យាថាអ្នកអាចបំបែកការរចនាជុំ។

បញ្ហាការអនុញ្ញាត Leetcode ដំណោះស្រាយផ្តល់នូវលំដាប់ធម្មតានៃចំនួនគត់ហើយស្នើឱ្យយើងត្រឡប់វ៉ិចទ័រពេញលេញឬ អារេ នៃការអនុញ្ញាតទាំងអស់នៃលំដាប់ដែលបានផ្តល់ឱ្យ។ ដូច្នេះមុននឹងចូលដោះស្រាយបញ្ហា។ យើងគួរតែស៊ាំនឹងការអនុញ្ញាត។ ដូច្នេះការអនុញ្ញាតគឺគ្មានអ្វីក្រៅពីការរៀបចំចំនួនគត់ដែលបានផ្តល់ឱ្យនោះទេ។ ដូច្នេះនៅពេលយើងនិយាយថាយើងត្រូវការការអនុញ្ញាតទាំងអស់នៃលំដាប់។ យើងមានន័យថាយើងតម្រូវឱ្យបោះពុម្ពឬប្រគល់ការរៀបចំដែលអាចធ្វើទៅបាននៃលំដាប់ដែលបានផ្តល់ឱ្យ។ សូមក្រឡេកមើលឧទាហរណ៍មួយចំនួនសម្រាប់ការយល់ដឹងកាន់តែប្រសើរ។

Given sequence: [1,2,3]

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

ការពន្យល់ៈវិធីទាំងអស់ដែលអ្នកអាចសរសេរ ១, ២, ៣ តាមលំដាប់លំដោយត្រូវបានផ្តល់ជាលទ្ធផល។ មានវិធីសរុបចំនួន ៦ ក្នុងការសរសេរ ១, ២, ៣ នៅក្នុងលិខិតអនុញ្ញាតិ។

[0,1]

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

ការពន្យល់៖ មានតែវិធី ២ ទេដែលអាចសរសេរ ០, ១ ។

វិធីសាស្រ្តនៃការដើរថយក្រោយសម្រាប់ការអនុញ្ញាត Leetcode ដំណោះស្រាយ

ពិន

បញ្ហាការអនុញ្ញាត Leetcode ដំណោះស្រាយបានស្នើសុំឱ្យយើងបង្កើតការអនុញ្ញាតិទាំងអស់នៃលំដាប់ដែលបានផ្តល់ឱ្យ។ ជាទូទៅយើងតំរូវអោយបង្កើតលិខិតអនុញ្ញាតិឬការហៅតាមលំដាប់លំដោយខ្លះៗគឺជាគន្លឹះដែលត្រូវទៅ។ ប៉ុន្តែនៅទីនេះការហៅឡើងវិញឬការសម្លាប់រង្គាលគឺជាល្បិចបន្តិច។ វិធីមួយអាចត្រូវបានជ្រើសរើសយកធាតុមួយពីធាតុដែលមិនបានរៀបចំហើយដាក់វានៅចុងបញ្ចប់នៃចម្លើយ។ វិធីនេះបង្កើតការអនុញ្ញាតិហើយត្រូវប្រាកដថាចងចាំថាការអនុញ្ញាតនេះត្រូវបានបង្កើតហើយមិនគួរត្រូវបានធ្វើម្តងទៀតទេ។ ប៉ុន្តែជំនួសឱ្យការធ្វើបែបនេះយើងព្យាយាមរកវិធីសាមញ្ញដើម្បីអនុវត្តភារកិច្ច។ តើមានអ្វីប្រសិនបើយើងជ្រើសរើសយកធាតុហើយប្តូរវាជាមួយធាតុបច្ចុប្បន្ន។ បន្ទាប់មកធ្វើការហៅខ្លួនឯងដើម្បីបង្កើតការអនុញ្ញាតទាំងអស់សម្រាប់លំដាប់មួយបន្ទាប់ពីសន្ទស្សន៍បច្ចុប្បន្ន។

នៅពេលដែលយើងបានបញ្ចប់ជាមួយនឹងការបង្កើតការអនុញ្ញាតនូវសន្ទស្សន៍មួយនៅខាងមុខ។ យើងដកធាតុដែលបានជ្រើសរើសហើយបន្ទាប់មកជ្រើសរើសយកធាតុផ្សេងទៀតហើយធ្វើបែបបទម្តងទៀត។ វិធីនេះយើងធ្វើឱ្យប្រាកដថាយើងបានដាក់ធាតុដែលមិនប្រើនីមួយៗយ៉ាងហោចណាស់ម្តងក្នុងទីតាំងបច្ចុប្បន្ន។ ហើយចាប់តាំងពីយើងបានហៅការហៅទូរស័ព្ទទៅកម្មវិធីរងតូចជាងមុន។ ធាតុរងតូចៗកំពុងបង្កើតការអនុញ្ញាតិសម្រាប់លំដាប់ដែលចាប់ផ្តើមបន្ទាប់ពីសន្ទស្សន៍បច្ចុប្បន្ន។ ការបន្ថែមការអនុញ្ញាតទាំងនោះទៅនឹងការអនុញ្ញាតបច្ចុប្បន្នបញ្ចប់សំណុំនៃការអនុញ្ញាតិជាមួយនឹងធាតុដែលបានកំណត់នៅសន្ទស្សន៍បច្ចុប្បន្ន។ វិធីនេះយើងបន្តឆ្លងកាត់អារេពីឆ្វេងទៅស្តាំនិងបែងចែកបញ្ហានេះទៅជារូបតូចៗ។ នៅពេលយើងឈានដល់តំរូវការយើងបានបង្កើតលិខិតអនុញ្ញាតដែលអាចធ្វើបានហើយយើងបន្ថែមវាទៅចម្លើយ។

លេខកូដបម្រុង

កូដ 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

កូដចាវ៉ាសំរាប់ការអនុញ្ញាតដំណោះស្រាយឡេឡេកូដ

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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

អូ (ស៊ីជីម៉ា (P (N, ខេ)), ដែល P ជាអនុគមន៍ k នៃ n ឬអនុញ្ញាតិដោយផ្នែក។ ជាផ្លូវការបន្ថែមទៀត P (N, k) = (N!) / ((Nk)!) ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (ន។ ) ដោយសារយើងត្រូវរក្សាទុករាល់ដំណោះស្រាយដែលអាចមានដែលជា N! ក្នុងទំហំដែល N ជាទំហំនៃអារេ។