Leetcode alt dəsti

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg ByteDance Facebook google microsoft Kahin
alqoritmlər Geyim Geri qayıtma Parça Bit manipulyasiya Bits kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 50

Alt Set Leetcode problemində bir-birindən fərqli tam ədədlər, ədədlər verdik, bütün alt dəstləri (güc dəsti) çap edin.

Qeyd: Çözüm dəstində təkrar alt dəstlər olmamalıdır.

Bir sıra A, bəzi (ehtimal ki, sıfır və ya hamısı) elementlərin silinməsi ilə B-dən əldə edilə biləcəyi təqdirdə, B dizisinin alt hissəsidir.

misal

Input:

[1, 2, 3]

Çıxış:

[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

Yanaşma 1: Bit manipulyasiyasından istifadə edərək təkrarlanan həll

N element dəstinin hər alt dəsti 0… 2n-1 arasındakı bir tam ədədə uyğun gələn n bit ardıcıllığı kimi təmsil oluna bilər. Bit ardıcıllığında olanlar alt elementə hansı elementlərin daxil olduğunu göstərir.

Alqoritm

  1. Bəyan et array bütün alt dəstlərimizi saxlayacağımız “ans” vektorlarından.
  2. Nums_array ölçüsünü təmsil edən n dəyişənini başladın.
  3. 0 - 2 aralığında I üçün bir döngə çalıştırınn-1
    1. Mövcud alt dəstimizi saxlayacağımız bir sıra "temp" başlayın.
    2. 0-dan n-1 aralığında j üçün bir döngə işlədin
      1. I-nin jth biti qoyulubsa, temp massivinə nums [i] əlavə edin.
    3. “Temp” massivini “ans” a əlavə edin
  4. Son ans dizisini çap edin.

Bütün alt dəstləri çap etmək üçün tətbiqetmə

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    for (int i = 0; i < (1 << (nums.size())); i++)
    {
        vector<int> temp;
        for (int j = 0; j < nums.size(); j++)
        {
            if (i & (1 << j))
            {
                temp.push_back(nums[j]);
            }
        }
        ans.push_back(temp);
    }
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Bütün alt dəstləri çap etmək üçün mürəkkəblik analizi

Zaman mürəkkəbliyi

Biri 2 ^ n aralığında, digəri n aralığında iki iç içə döngə işlədirik. beləliklə son zaman mürəkkəbliyi O (2 ^ n * n) -dir.

Kosmik mürəkkəblik

2 ^ n-1 alt dəsti var və hər alt üçün ortalama O (n) boşluğuna ehtiyacımız var, beləliklə ümumi kosmik mürəkkəblik O (2 ^ n * n) təşkil edir.

Optimize edə bilərikmi?

Bəli, geriyə baxaraq onu optimallaşdırmaq olar, gəlin görək necə!

Yanaşma 2: Backtracking istifadə edərək rekursiv həll

Nums seriyası üzərində təkrarlayırıq və hər bir mövqe üçün iki seçimimiz var, ya ith elementini götürün ya da atlayın.

Alqoritm

  1. Arqumentləri, son cavab massivini, cari alt massivini, giriş massivini və ədədlər massivindəki cari elementi göstərən dəyişən “indeks” i götürən bir funksiya yaradın.
  2. Əsas şərt: Əgər "indeks" saylar massivinin ölçüsünə bərabərdirsə, onda indiki alt sıra massivimizi son cavaba əlavə edin, çünki artıq saylar cərgəsini keçə bilmərik.
  3. İndi iki seçimimiz var
    1. Mövcud elementi atlayın və indeks + 1 ilə rekursiv funksiyanı çağırın və bütün digər arqumentlər eyni qalacaq.
    2. Mövcud elementi cari alt hissəyə əlavə edin və +1 indeksi və digər arqumentlərlə rekursiv funksiyanı çağırın. Rekursiv funksiyanı çağırdıqdan sonra, son elementi cari altdan silməklə geri addım atın.
  4. Son cavabı çap edin.

Nümunə ilə başa düş

Giriş ədədi ədədi götürək = [1,2,3]

Sonra rekursiya ağacı belə olacaq:

Leetcode alt dəstiPin

Yuxarıda göstərilən ağacda (i) alt cari indeksin göstərildiyi rekursiv funksiyadır.

Bütün alt dəstləri çap etmək üçün tətbiqetmə

Subset Leetcode üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
void subsets(vector<vector<int>> &ans, vector<int> &temp, vector<int> &nums, int i)
{
    if (i == nums.size())
    {
        ans.push_back(temp);
        return;
    }
    subsets(ans, temp, nums, i + 1);
    temp.push_back(nums[i]);
    subsets(ans, temp, nums, i + 1);
    temp.pop_back();
    return;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    vector<int> temp;
    subsets(ans, temp, nums, 0);
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

Subset Leetcode üçün JAVA proqramı

import java.util.*; 
public class Main
{
    static List<List<Integer>> res;
    public static void subsets(int[] nums,int index,List<Integer> list){
        if(index==nums.length-1){
            res.add(new ArrayList<Integer>(list));
            list.add(nums[index]);
            res.add(new ArrayList<Integer>(list));
            list.remove(list.size()-1);
            return;
        }
        subsets(nums,index+1,list);
        list.add(nums[index]);
        subsets(nums,index+1,list);
        list.remove(list.size()-1);
    }
  public static void main(String[] args) {
      res = new ArrayList<>();
      int[] nums={2, 3, 4};
      List<Integer> list = new ArrayList<Integer>();
      subsets(nums, 0, list);
      for(List<Integer> subset:res){
          for(int i: subset){
              System.out.print(i+", ");
          }
            System.out.println();
      }
  }
}

4, 
3, 
3, 4, 
2, 
2, 4, 
2, 3, 
2, 3, 4, 

Alt Leetcode üçün Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Hər indeks üçün 2 rekursiya çağırışı edirik və n element var, beləliklə ümumi vaxt mürəkkəbliyi O (2 ^ n) -dir.

Kosmik mürəkkəblik

2 ^ n-1 alt dəsti var və hər alt üçün ortalama O (n) boşluğuna ehtiyacımız var, beləliklə ümumi kosmik mürəkkəblik O (2 ^ n * n) təşkil edir.

References

Şərh yaz

Translate »