Leetcode қосындысының аралас шешімі  


Күрделілік дәрежесі орта
Жиі кіреді Adobe Airbnb Amazon алма Atlassian Bloomberg ByteDance еВау Facebook Голдман Сакс Google LinkedIn Microsoft Oracle Snapchat шаршы қиятын VMware Walmart зертханалары
алгоритмдер Array Кері шегіну кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions

Leetcode Solution жиынтығының шешімі бізге мүмкіндік береді массив немесе бүтін сандар тізімі және мақсат. Берілген мақсатқа бірнеше рет қосылатын осы бүтін сандарды қолданып жасауға болатын комбинацияларды табу керек дейді. Ресми түрде біз берілген бүтін сандарды берілген мақсатқа қосатындай етіп бірнеше рет қолдана аламыз. Қажетті нәтиже - бұл берілген мақсатқа тең сомасы бар комбинациялар.

мысалLeetcode қосындысының аралас шешімі  

candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]

Түсіндіру: Берілген нәтиже берілген мақсатқа дейін жинақталады. Біз кез-келген басқа комбинацияны ойлап табуға тырыссақ та. Біз бірдей бүтін сандарды басқа тәртіпте орналастырамыз. Бірақ тапсырыс тек комбинациялар үшін маңызды емес.

candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]

Түсініктеме: біз бірдей бүтін санды бірнеше рет қолдана аламыз. Шығарылымда біз 2-ні бірінші рет қолдандық. Сол сияқты, екінші шығарылымда 2 қайталанады. Біз барлық үш нәтиженің берілген мақсатқа сәйкес келетіндігін тексере аламыз.

Leetcode жиынтық шешімінің әдісі  

Мәселеге көзқарасты табу оңай. Әдетте, мұндай мәселелерде біз кері шегінуді қолдануымыз керек. Себебі мұндай сұрақтардан біз толық ізденіп, жауабын табуға міндеттіміз. Сонымен, алдымен бізге берілген бүтін сандардың тізімін сұрыптаймыз. Осыдан кейін біз бүтін сандардың ағымдағы уақытша тізіміне бүтін сан қосуды және берілген мақсатқа дейін қосу үшін қалған соманың есебін сақтайтын рекурсивті функция жасаймыз. Сонымен, рекурсивті функцияның ішінде біз екі негізгі жағдайды сақтаймыз. Бірінші базалық жағдай - бұл қажетті соманың теріс мәнге жететіндігін тексеру. Бұл жағдайда біз рекурсивті функциядан ораламыз. Екінші базалық жағдай, егер қалған сома нөлге тең болса, біздің талап етілетін шарт. Егер қалған сома нөлге тең болса, бұл біз қажетті межеге жеткенімізді білдіреді. Осы кезде біз бүтін сандардың ағымдағы уақытша тізімін массивтердің шығыс массивіне жібереміз.

Сондай-ақ, қараңыз
Монеталарды өзгерту проблемасы

код  

Leitcode Solution жиынтық шешіміне арналған C ++ коды

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

void backtrack(vector<vector<int>> &output, vector<int> &current, vector<int> &candidates, int remain, int start){
    if(remain < 0)
        return;
    else if(remain == 0)output.push_back(current);
    else {
        for(int i=start;i<candidates.size();i++){
            current.push_back(candidates[i]);
            backtrack(output, current, candidates, remain - candidates[i], i);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> output;
    vector<int> current;
    sort(candidates.begin(), candidates.end());
    backtrack(output, current, candidates, target, 0);
    return output;
}

int main(){
  vector<int> cand = {2, 3, 6, 7};
  vector<vector<int>> output = combinationSum(cand, 7)	;
  for(auto x: output){
    for(auto y: x)
      cout<<y<<" ";
    cout<<endl;
  }
}
2 2 3 
7

Біріктірілген жиынтық Leetcode шешіміне арналған Java коды

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

class Main
{
  public static List<List<Integer>> combinationSum(int[] nums, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(nums);
      backtrack(list, new ArrayList<>(), nums, target, 0);
      return list;
  }
  
  private static void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
      if(remain < 0) return;
      else if(remain == 0) list.add(new ArrayList<>(tempList));
      else{ 
          for(int i = start; i < nums.length; i++){
              tempList.add(nums[i]);
              backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
              tempList.remove(tempList.size() - 1);
          }
      }
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[] nums = {2, 3, 6, 7};
    List<List<Integer>> output = combinationSum(nums, 7);
    for(List<Integer> x: output){
      for(Integer y: x)
        System.out.print(y+" ");
      System.out.println();
    }
  }
}
2 2 3
7

Күрделілікті талдау  

Уақыттың күрделілігі

O (N ^ (M / T + 1)) Мұндағы N - үміткерлер саны, M - барлық берілген сандардың ішіндегі ең кіші үміткер, ал T - мақсатты мән. Осылайша уақыттың күрделілігі экспоненциалды болып табылады және алгоритм рекурсивті кері шегіну болғандықтан күтіледі.

Ғарыштың күрделілігі

O (T / M), мұндағы T - мақсатты мән, ал M - барлық басқа үміткерлер арасындағы минималды элемент.