国产探花免费观看_亚洲丰满少妇自慰呻吟_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

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 丹东市| 宾川县| 独山县| 常山县| 得荣县| 舞阳县| 天镇县| 隆尧县| 高陵县| 磐石市| 桦川县| 马关县| 唐海县| 东阿县| 广丰县| 繁峙县| 乐都县| 武清区| 莲花县| 罗定市| 保山市| 安阳市| 乌恰县| 芦溪县| 高陵县| 馆陶县| 神池县| 明溪县| 昭通市| 旺苍县| 民乐县| 棋牌| 吴川市| 蒲江县| 都江堰市| 台湾省| 兖州市| 顺平县| 长沙县| 吐鲁番市| 宜兴市|