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

កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម Atlassian ទីភ្នាក់ងារ Bloomberg ByteDance របស់ eBay Facebook Garena GoDaddy ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google LinkedIn ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle ការលក់ SAP Uber VMware បន្ទប់ពិសោធន៍វ៉លម៉ាត ក្រុមហ៊ុន Yahoo
ក្បួនដោះស្រាយ បទថយក្រោយ ការសរសេរកូដ សំភាសន៍ កិច្ចសម្ភាសន៍ លេខកូដសម្ងាត់ LeetCodeSolutionsចំនួនមើល 125

សំណួរសំភាសន៍រចនាប្រព័ន្ធ អាចជាការបើកចំហរ ដូច្នេះវាពិបាកពេកក្នុងការដឹងពីវិធីត្រឹមត្រូវក្នុងការរៀបចំ។ ឥឡូវនេះខ្ញុំអាចបំបែកការរចនានៃ 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 ជាទំហំនៃអារេ។

បទសម្ភាសន៍រចនាប្រព័ន្ធបំបែក
Translate »
1