小米算法编程题

被模板坑惨了

第一题： #include <iostream> #include<vector> #include<algorithm> #include <numeric> #include <limits> using namespace std; void combinationSum2DFS(vector<int> &num, int target, int start,  bool &falg) {     if (target == 0) { falg = true; return; }     for (int i = start; i < num.size(); ++i) {         if (target < num[i])return;         //out.push_back(num[i]);         combinationSum2DFS(num, target - num[i], i + 1, falg);         //out.pop_back();         while (i < num.size() - 1 && num[i] == num[i + 1])i++;         if (falg == true)             return;     } } bool miHomeGiftBag(vector<int> &num, int target) {     bool falg = false;     vector<int> out;     sort(num.begin(), num.end());     combinationSum2DFS(num, target, 0,  falg);     if (falg)         return true;     else return false; } int main() {     bool res;     int _p_size = 0;     cin >> _p_size;     vector<int> _p(_p_size, 0);     int _p_item;     for (int _p_i = 0; _p_i<_p_size; _p_i++) {         cin >> _p_item;         _p[_p_i] = _p_item;     }     int _M;     cin >> _M;     res = miHomeGiftBag(_p, _M);     cout << res << endl;     return 0; }

第二题： #include <iostream> #include<vector> using namespace std; int Judge(vector<int>&data, int mid, int m, int n) {     int cnt = 0;     int sum = 0;     for (int i = 0; i < n; i++)     {         if (sum + data[i] > mid)         {             sum = data[i];             cnt++;             if (cnt > m - 1)                {                 return 0;             }         }         else         {             sum += data[i];         }     }     return 1; } int Binary_Search(vector<int>&data, int left, int right, int m, int n) {     int mid = 0;     while (left < right)     {         mid = left + (right - left) / 2;         if (Judge(data, mid, m, n))          {             right = mid;         }         else    //         {             left = mid + 1;         }     }     return left; } int main() {     int n = 0, m = 0;     cin >> n >> m;     vector<int> data(n,0);     int max_num = 0;     int sum = 0;     int i = 0;     for (i = 0; i < n; i++)     {         cin >> data[i];         if (data[i] > max_num)         {             max_num = data[i];         }         sum += data[i];     }     cout << Binary_Search(data, max_num, sum, m, n);     return 0; }

leetcode 40和leetcode 410了解一下