leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0321.cpp (1319B)

0 class Solution { 1 static bool greater(const vector<int> &nums1, const vector<int> &nums2, int i, int j) { 2 while (i < size(nums1) && j < size(nums2) && nums1[i] == nums2[j]) 3 i++, j++; 4 return j == size(nums2) || (i < size(nums1) && nums1[i] > nums2[j]); 5 } 6 7 static vector<int> merge(const vector<int> &nums1, const vector<int> &nums2, int k) { 8 vector<int> res(k); 9 10 for (int i = 0, j = 0, l = 0; l < k; l++) { 11 res[l] = greater(nums1, nums2, i, j) ? nums1[i++] : nums2[j++]; 12 } 13 14 return res; 15 } 16 17 static vector<int> maxArr(const vector<int> &nums, int k) { 18 const int n = size(nums); 19 vector<int> res(k); 20 21 for (int i = 0, j = 0; i < n; i++) { 22 while (n - i + j > k && j > 0 && res[j - 1] < nums[i]) 23 j--; 24 if (j < k) res[j++] = nums[i]; 25 } 26 27 return res; 28 } 29 30 public: 31 vector<int> maxNumber(const vector<int> &nums1, const vector<int> &nums2, int k) const { 32 const int n = size(nums1), m = size(nums2); 33 vector<int> res(k); 34 35 for (int i = max(0, k - m); i <= k && i <= n; i++) { 36 const auto candid = merge(maxArr(nums1, i), maxArr(nums2, k - i), k); 37 res = max(res, candid); 38 } 39 40 return res; 41 } 42 };