Хосолсон Leetcode шийдэл  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Airbnb Амазоны Apple-ийн Atlassian Bloomberg БайтДанс Ebay Facebook-ийн Goldman Sachs Google-ийн LinkedIn Microsoft- Oracle-ийн Snapchat Square Uber VMware Walmart лабораторууд
алгоритмууд Array Буцах кодлох ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions

Асуудлын хослолын нийлбэр Leetcode шийдэл нь бидэнд массив эсвэл бүхэл тоонуудын жагсаалт ба зорилт. Өгөгдсөн зорилтот түвшинд хэдэн удаа нэмэгдэхийг эдгээр бүхэл тоог ашиглан хийж болох хослолуудыг олохыг бидэнд хэллээ. Илүү албан ёсоор бид өгөгдсөн бүхэл тоонуудыг тухайн зорилтот түвшинд нэмж хэдэн удаа ашиглаж болно. Шаардлагатай гаралт нь өгөгдсөн зорилттой тэнцүү нийлбэртэй хослолууд юм.

Жишээ ньХосолсон Leetcode шийдэлPin  

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 давтагдана. Бүх 3 гаргалтууд нь өгөгдсөн зорилтод нийцэж байгааг бид шалгаж чадна.

Leetcode хосолмол шийдлийн арга  

Асуудлыг шийдвэрлэх арга замыг олоход хялбар байдаг. Ерөнхийдөө иймэрхүү асуудлуудад бид буцах мөрийг ашиглахыг шаарддаг. Учир нь ийм асуултанд бид бүрэн хайлт хийж, хариултыг нь олохыг шаарддаг. Эхлээд бидэнд өгсөн бүхэл тоонуудын жагсаалтыг эрэмбэлье. Үүний дараа бид одоо байгаа бүхэл тоонуудын түр зуурын жагсаалтад бүхэл тоо нэмж, өгөгдсөн зорилтод нэмэхэд шаардагдах үлдсэн нийлбэрийг тэмдэглэж байх рекурсив функцийг бий болгодог. Тиймээс рекурсив функц дотор бид хоёр үндсэн тохиолдлыг хадгалдаг. Эхний суурь тохиолдол нь шаардагдах үлдсэн нийлбэр сөрөг гарсан эсэхийг шалгах явдал юм. Энэ тохиолдолд бид рекурсив функцээс буцах болно. Хоёрдахь суурь тохиолдол нь үлдсэн нийлбэр нь тэгтэй тэнцэх тохиолдолд бидний шаардагдах нөхцөл юм. Хэрэв үлдсэн нийлбэр нь тэг байвал бид шаардлагатай зорилгодоо хүрсэн гэсэн үг юм. Энэ үед бид бүхэл тоонуудын түр зуурын жагсаалтыг массивын гаралтын массив руу түлхэж оруулна.

мөн үзнэ үү
Зоос солих асуудал

код  

Combination Sum Leetcode шийдлийн 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

Combination Sum 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 бол бусад бүх нэр дэвшигчдийн дунд хамгийн бага элемент юм.

1