ပေါင်းစပ် Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple Facebook က Google Microsoft က Yahoo က
နောက်ပြန်

Combinations Leetcode Solution မှပြusနာကကျွန်တော်တို့ကို n, k တို့ကိန်းနှစ်ခုပေးတယ်။ 1 ကနေ n အထိ n element တွေထဲက k element တွေကိုကောက်ယူထားတဲ့ပာအားလုံးရဲ့အစီအစဉ်တွေကိုထုတ်လုပ်ဖို့ပြောတယ်။ ကျနော်တို့ကဤပာပြန်လာပါ အခင်းအကျင်း။ ပြfewနာကိုပိုမိုနားလည်ရန်ဥပမာအနည်းငယ်ကိုလေ့လာကြည့်ကြစို့။

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

ရှင်းလင်းချက် - ဒီ output ကပထမဆုံး n natural ကိန်းဂဏန်းများထဲက k element တွေကိုရွေးခြင်းနည်းလမ်းအားလုံးကိုပြသသည်။ ဒီမှာကိန်းဂဏန်းများ၏အမိန့်သည်အရေးမကြီးပါ။ နံပါတ်များသာစုဆောင်းခြင်းသည်အရေးပါသည်။

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

ရှင်းလင်းချက် - ဒီမှာတစ်ခုရှိတယ်။ ကျနော်တို့ကတစ်ခုတည်းဒြပ်စင်ရွေးရန်ပြောသည်နေကြသည်။ ထို့ကြောင့် output ကို [[1]] ဖြစ်ပါတယ်။

အဆိုပါပေါင်းစပ် Leetcode ဖြေရှင်းချက်များအတွက်ချဉ်းကပ်မှု

အဆိုပါပြproblemနာပေါင်းစပ် Leetcode ဖြေရှင်းချက်ပထမ ဦး ဆုံး n ကိန်းဂဏန်းများထဲက k element တွေကိုကောက်ယူအားလုံးပာထုတ်လုပ်ရန်ရိုးရှင်းစွာကျွန်တော်တို့ကိုမေးတယ်။ ဒါကြောင့်ဒီဟာက k element တွေကိုရွေးဖို့ nCk ပေါင်းစပ်မှုအားလုံးကိုရိုးရိုးလေးထုတ်လုပ်တာပါ။ ယေဘုယျအားဖြင့်ပာ၏မျိုးဆက်များပါ ၀ င်သောလုပ်ငန်းများကိုပြန်လည်အသုံးပြုခြင်းဖြင့်ဖြေရှင်းသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ပြtheနာကိုပြန်လည်တုံ့ပြန်သည့်နည်းလမ်းကိုကြိုးစားသည်။ ထိုပေါင်းစပ်မှုများကိုသိမ်းဆည်းရန်ရည်ရွယ်သော vector ကိုခြေရာခံပါ။

ဒါကြောင့်ကျွန်တော်တို့ဟာအချည်းနှီးသောအားနည်းချက်နှင့်စတင်ပါ။ ကျနော်တို့က element တစ်ခုတွန်းအားပေး။ ထို့နောက် n-1 ဒြပ်စင်များထဲမှ k-1 ဒြပ်စင်များကောက်ယူခြင်း၏ subproblem ကိုပြန်လည်တုံ့ပြန်ပါ။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည် 0 element များရွေးခြင်း၏ပြreachနာကိုရောက်ရှိသည်အထိပြtheနာကိုလျှော့ချသည်။ ဤသို့ဖြစ်လျှင်ကျွန်ုပ်တို့သည်ယာယီအားနည်းချက်ကိုကျွန်ုပ်တို့၏အဖြေသို့တွန်းပို့သည်။ နောက်ဆုံးတွင်၊ ဤအဖြေသည် n element များမှ k element များကောက်ယူခြင်းအစဉ်လိုက်ကိုသိမ်းဆည်းသည်။

ပေါင်းစပ် Leetcode ဖြေရှင်းချက်

ပေါင်းစပ် 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]]

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (* * nCk)၊ ဤနေရာတွင် nCk သည် elements element များမှ k element များကိုကောက်ယူခြင်း၏ binomial ကိန်းကိုဆိုလိုသည်။

အာကာသရှုပ်ထွေးမှု

အို (nCk), အထက်တွင်ဖော်ပြထားသည့်အတိုင်း nCk သည် binomial ကိန်းကိုရည်ညွှန်းသည်။