Падмноства Leetcode  


Узровень складанасці серада
Часта пытаюцца ў амазонка яблык Bloomberg ByteDance facebook Google Microsoft Аракул
алгарытмы масіў Фанаграмы Біт Бітавая маніпуляцыя біты кадаваньне інтэрв'ю інтэрв'юп LeetCode LeetCodeSolutions

У задачы Subset Leetcode мы далі набор розных цэлых лікаў, нумароў, надрукаваць усе падмноствы (набор магутнасці).

нататка: Набор рашэнняў не павінен утрымліваць паўтараюцца падмноствы.

Масіў A - гэта падмноства масіва B, калі a можна атрымаць з B, выдаліўшы некаторыя (магчыма, нуль або ўсе) элементы.

Прыклад  

Уваход:

[1, 2, 3]

Вынахад:

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

Падыход 1: Ітэратыўнае рашэнне з выкарыстаннем бітавых маніпуляцый  

Кожная падмноства набору з n элементаў можа быць прадстаўлена ў выглядзе паслядоўнасці з n бітаў, якая адпавядае цэламу ліку паміж 0 ... 2n-1. Тыя, што ў паслядоўнасці бітаў, паказваюць, якія элементы ўключаны ў падмноства.

Алгарытм

  1. Абвясціце масіў вектараў "ans", у якіх мы будзем захоўваць усе нашы падмноствы.
  2. Ініцыялізуйце зменную n, якая ўяўляе памер масіва nums__.
  3. Выканайце цыкл для I ў дыяпазоне ад 0 да 2n-1
    1. Ініцыялізаваць масіў «temp», у якім мы будзем захоўваць бягучае падмноства.
    2. Запусціце цыкл для j у дыяпазоне ад 0 да n-1
      1. Калі ўсталяваны j-ы біт I, дадайце нумары [i] у масіў.
    3. Дадайце масіў "temp" у "ans"
  4. Надрукаваць канчатковы масіў ans.
Глядзіце таксама
Знайсці ўсе нумары, якія зніклі, у рашэнні з масівам Leetcode

Рэалізацыя для друку ўсіх падмностваў

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

Аналіз складанасці для друку ўсіх падмностваў

Часовая складанасць

Мы запускаем дзве ўкладзеныя завесы, адну з дыяпазону 2 ^ n, а другую з дыяпазону n. таму канчатковая складанасць часу - O (2 ^ n * n).

Касмічная складанасць

Ёсць 2 ^ n-1 падмноства, і для кожнага падмноства нам у сярэднім патрэбна O (n) прастора, таму агульная складанасць прасторы O (2 ^ n * n).

Ці можам мы яго аптымізаваць?

Так, мы можам аптымізаваць яго з дапамогай зваротнага адсочвання, паглядзім як!

Падыход 2: Рэкурсіўнае рашэнне з выкарыстаннем зваротнага адсочвання  

Мы перабіраем масіў nums і для кожнай пазіцыі ў нас ёсць два варыянты: альбо ўзяць i-ы элемент, альбо прапусціць яго.

Алгарытм

  1. Стварыце функцыю, якая прымае аргументы, масіў канчатковага адказу, масіў бягучага падмноства, масіў уводу і зменную "index", якая паказвае на бягучы элемент у масіве nums.
  2. Базавая ўмова: Калі "індэкс" роўны памеру масіва nums, дадайце наш бягучы масіў падмноства да канчатковага адказу, таму што зараз мы больш не можам прайсці масіў nums.
  3. Зараз у нас ёсць два варыянты выбару
    1. Прапусціце бягучы элемент і выклічце рэкурсіўную функцыю з індэксам + 1, а ўсе астатнія аргументы застануцца ранейшымі.
    2. Дадайце бягучы элемент да бягучага падмноства і выклічце рэкурсіўную функцыю з індэксам +1 і іншымі аргументамі. Пасля выкліку рэкурсіўнай функцыі зрабіце крок зваротнай адсочвання, выдаліўшы апошні элемент з бягучага падмноства.
  4. Раздрукуйце канчатковы адказ.
Глядзіце таксама
Максімальная колькасць манет, якія вы можаце атрымаць з рашэннем Leetcode

Зразумейце на прыкладзе

Возьмем уваходны масіў nums = [1,2,3]

Тады дрэва рэкурсіі будзе выглядаць так:

Падмноства LeetcodePin

У прыведзеным дрэве падмноства (i) - гэта рэкурсіўная функцыя, дзе i абазначае бягучы індэкс.

Рэалізацыя для друку ўсіх падмностваў

Праграма C ++ для падмноства Leetcode

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

Праграма JAVA для падмноства Leetcode

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, 

Аналіз складанасці для падмноства Leetcode

Часовая складанасць

Для кожнага індэкса мы робім 2 выклікі рэкурсіі, і ёсць n элементаў, таму агульная складанасць часу роўная O (2 ^ n).

Касмічная складанасць

Ёсць 2 ^ n-1 падмноства, і для кожнага падмноства нам у сярэднім патрэбна O (n) прастора, таму агульная складанасць прасторы O (2 ^ n * n).

Спасылкі