国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

Leetcode 321 - Create Maximum Number(貪心)

2019-11-10 19:14:34
字體:
來源:轉載
供稿:網友

題意

給兩個數組nums1和nums2,和一個數字k,要求從nums1里面和nums2里面分別找出一些數字,構成一個新的數字,并且新的數字最大。并且nums1里面取的數字和nums2里面取的數字要保持相對順序不變。

思路

之前做過一道類似的題,只給一個數組,找出k個數,維持相對順序,求能組成的最大的數。

那么,這道題,其實就是說,在nums1里面找出x個,nums2里面找出y個,x + y == k,求能組成的最大的數。

那么,我們就枚舉從nums1里面取i個數(組成最大的數),nums2里面取k - i個數(組成最大的數)。最后歸并即可。

需要注意一下幾點:

找nums1里面由i個能組成的最大的數的時候,我們維護一個單調增的隊列。最后歸并的時候,當指針i和j指向的數相同的時候,還要考慮后續元素的影響

代碼

class Solution {public: vector<int> get(vector<int> nums1, int k) { vector<int> s; if (!k) return s; int re = nums1.size() - k; for (auto x : nums1) { while (re && s.size() && s.back() < x) {re--; s.pop_back();} s.push_back(x); } s.resize(k); return s; } vector<int> merge(vector<int> v1, vector<int> v2) { vector<int> ans; while (v1.size() || v2.size()) { vector<int> &tv = v1 > v2 ? v1 : v2; ans.push_back(tv[0]); tv.erase(tv.begin()); } return ans; } vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) { vector<int> ans; for (int i = 0; i <= k; i++) { if (i <= nums1.size() && k - i <= nums2.size()) {; vector<int> v1 = get(nums1, i); vector<int> v2 = get(nums2, k - i); ans = max(ans, merge(v1, v2)); } } return ans; }};
上一篇:面向過程(3)

下一篇:poj1517

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 成武县| 通榆县| 同江市| 宜黄县| 嵊泗县| 屯门区| 台南市| 水富县| 电白县| 永仁县| 高安市| 二连浩特市| 和田县| 宣威市| 北宁市| 神农架林区| 沙田区| 同德县| 平塘县| 抚顺县| 班戈县| 平泉县| 杂多县| 泰顺县| 崇文区| 枣阳市| 尼勒克县| 宿松县| 阳谷县| 新田县| 赤壁市| 华蓥市| 浦县| 乃东县| 随州市| 桓仁| 吐鲁番市| 灵宝市| 嘉黎县| 保山市| 阿克陶县|