បន្សំដំណោះស្រាយឡេឡេកូដ  


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម Facebook ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Yahoo
ក្បួនដោះស្រាយ បទថយក្រោយ ការសរសេរកូដ សំភាសន៍ កិច្ចសម្ភាសន៍ LeetCode LeetCodeSolutions

ដំណោះស្រាយបន្សំឡេឡេលេខកូដផ្តល់ឱ្យយើងនូវចំនួនគត់ពីរគឺ n និង k ។ យើងត្រូវបានគេប្រាប់ឱ្យបង្កើតលំដាប់ទាំងអស់ដែលមានធាតុ k ដែលបានជ្រើសរើសចេញពីធាតុ n ពី 1 ដល់ n ។ យើងត្រឡប់លំដាប់ទាំងនេះជាអា អារេ។ សូមឱ្យយើងឆ្លងកាត់ឧទាហរណ៍មួយចំនួនដើម្បីឱ្យមានការយល់ដឹងកាន់តែច្បាស់អំពីបញ្ហា។

n = 4, k = 2
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

ការពន្យល់ៈលទ្ធផលបង្ហាញគ្រប់វិធីក្នុងការជ្រើសរើសយកធាតុ k ចេញពីលេខធម្មជាតិ n ដំបូង។ នៅទីនេះការតម្រៀបលេខមិនសំខាន់ទេ។ មានតែការប្រមូលលេខប៉ុណ្ណោះ។

n = 1, k = 1
[[1]]

ការពន្យល់៖ នៅទីនេះចាប់តាំងពីយើងមានធាតុតែមួយ។ យើងត្រូវបានគេប្រាប់ឱ្យជ្រើសរើសធាតុតែមួយ។ ដូច្នេះលទ្ធផលគឺ [[1]] ។

វិធីសាស្រ្តសម្រាប់ដំណោះស្រាយបន្សំឡេឡេកូដ  

ដំណោះស្រាយបន្សំឡេឡេលេខកូដបានស្នើសុំឱ្យយើងបង្កើតលំដាប់ទាំងអស់នៃការជ្រើសរើសយកធាតុ k ចេញពីលេខធម្មជាតិ n ដំបូង។ ដូច្នេះនេះគ្រាន់តែបង្កើតបន្សំ nCk ទាំងអស់ដែលអាចរកបានដើម្បីជ្រើសរើសធាតុ k ។ ជាទូទៅភារកិច្ចដែលទាក់ទងនឹងជំនាន់នៃជំនាន់ត្រូវបានដោះស្រាយដោយប្រើការហៅខ្លួនឯង។ ដូច្នេះ, យើងព្យាយាមវិធីសាស្រ្តហៅខ្លួនឯងដើម្បីដោះស្រាយបញ្ហា។ ហើយតាមដានវ៉ិចទ័រដែលមានគោលបំណងរក្សាទុកបន្សំបែបនេះ។

ដូច្នេះយើងចាប់ផ្តើមជាមួយវ៉ិចទ័រទទេ។ យើងរុញធាតុមួយទៅក្នុងវា។ បន្ទាប់មកដោះស្រាយឡើងវិញនូវអនុរងនៃការជ្រើសរើសយកធាតុ K-1 ចេញពីធាតុ n-1 ដែលនៅសល់។ តាមរបៀបនេះយើងបន្តកាត់បន្ថយបញ្ហារហូតដល់យើងឈានដល់បញ្ហានៃការរើសយកធាតុ ០ ។ នៅពេលរឿងនេះកើតឡើងយើងរុញវ៉ិចទ័របណ្តោះអាសន្ននេះទៅនឹងចំលើយរបស់យើង។ នៅចុងបញ្ចប់ចម្លើយនេះរក្សាទុកលំដាប់ទាំងអស់នៃការជ្រើសរើសយកធាតុ K ចេញពីធាតុ n ។

សូម​មើល​ផង​ដែរ
រាប់លេខសេសនៅក្នុងដំណោះស្រាយចន្លោះ Leetcode

បន្សំដំណោះស្រាយឡេឡេកូដពិន

លេខកូដសំរាប់ដំណោះស្រាយបន្សំឡេឡេកូដ  

លេខកូដ C ++

#include <bits/stdc++.h>
using namespace std;

void rec(int i, int k, int n, vector<int>& cur, vector<vector<int>>& res){
    if(cur.size()==k) {
        res.push_back(cur);
    } else {
        for(int j=i;j<=n;j++) {
            cur.push_back(j);
            rec(j+1, k, n, cur, res);
            cur.pop_back();
        }
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> cur;
    rec(1, k, n, cur, res);
    return res;
}

int main(){
    vector<vector<int>> output = combine(4, 2);
    for(auto singleList: output){
        for(auto element: singleList)
            cout<<element<<" ";
        cout<<endl;
    }
}
1 2
1 3
1 4
2 3
2 4
3 4

ចាវ៉ាកូដ

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  static List<List<Integer>> res = new ArrayList<List<Integer>>();
  
    public static void rec(int i, int k, int n, ArrayList<Integer> cur){
        if(cur.size()==k) {
            res.add(new ArrayList(cur));
        } else {
            for(int j=i;j<=n;j++) {
                cur.add(j);
                rec(j+1, k, n, cur);
                cur.remove(cur.size()-1);
            }
        }
    }
    
    public static List<List<Integer>> combine(int n, int k) {
        ArrayList<Integer> cur = new ArrayList<Integer>();
        rec(1, k, n, cur);
        return res;
    }

  public static void main (String[] args) throws java.lang.Exception{
    List<List<Integer>> res = combine(4, 2);
    System.out.println(res);
  }
}
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

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

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

O (k * nCk), នៅទីនេះ nCk មានន័យថាមេគុណមីណូមនៃការជ្រើសរើសយកធាតុ K ចេញពីធាតុ n ។

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

O (nCk), ដូចដែលបានបញ្ជាក់ខាងលើ nCk នៅទីនេះសំដៅទៅលើមេគុណមីណូម៉ាល់។

1