Համակցություններ Leetcode լուծում


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon խնձոր facebook Google Microsoft Անտաշ անասուն նողկալի արարած
Հետադարձ կապ

Խնդիրը Համակցություններ Leetcode Solution- ը մեզ տալիս է երկու ամբողջ թիվ `n և k: Մեզ ասում են, որ գեներացնելու ենք բոլոր հաջորդականությունները, որոնք ունեն k տարրեր, որոնք ընտրված են n տարրերից 1-ից մինչև n: Մենք վերադարձնում ենք այս հաջորդականությունները որպես դասավորություն, Եկեք մի քանի օրինակով անցնենք խնդրին ավելի լավ պատկերացնելու համար:

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

Բացատրություն. Արդյունքը ցույց է տալիս առաջին n բնական թվերից k տարրեր ընտրելու բոլոր եղանակները: Այստեղ թվերի դասավորությունը նշանակություն չունի: Միայն թվերի հավաքածուն է կարևոր:

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

Բացատրություն. Այստեղ, քանի որ մենք ունենք մեկ տարր: Մեզ ասում են նաև, որ ընտրենք մեկ տարր: Այսպիսով արդյունքը [[1]] է:

Համադրություն Leetcode լուծման մոտեցում

Խնդիրը Համակցություններ Leetcode Solution- ը մեզ խնդրեց պարզապես առաջացնել առաջին n բնական թվերից k տարրեր ընտրելու բոլոր հաջորդականությունները: Այսպիսով, սա պարզապես առաջացնում է բոլոր nCk համադրությունները, որոնք առկա են k տարրեր ընտրելու համար: Ընդհանրապես, հաջորդականությունների գեներացման հետ կապված խնդիրները լուծվում են ՝ օգտագործելով ռեկուրսիան: Այսպիսով, մենք փորձում ենք ռեկուրսիվ մոտեցում ցուցաբերել խնդրին: Եվ հետևեք մի վեկտորի, որի նպատակն է պահպանել նման զուգակցումները:

Այսպիսով, մենք սկսում ենք դատարկ վեկտորից: Մենք դրա մեջ տարր ենք մղում: Հետո ռեկուրսիվ լուծեք մնացած n-1 տարրերից k-1 տարրեր ընտրելու ենթախնդիր: այս կերպ մենք շարունակում ենք նվազեցնել խնդիրը, մինչև հասնենք 0 տարր ընտրելու խնդրին: Երբ դա պատահում է, մենք սեղմում ենք այս ժամանակավոր վեկտորը մեր պատասխանին: Ի վերջո, այս պատասխանը պահպանում է n տարրերից k տարրեր ընտրելու բոլոր հաջորդականությունները:

Համակցություններ 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

Java կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (k * nCk), այստեղ nCk նշանակում է n տարրերից k տարրեր ընտրելու երկիշխանության գործակից:

Տիեզերական բարդություն

O (nCk), ինչպես նշված է nCk- ի վերևում, այստեղ վերաբերում է երկիշխանության գործակիցին: