leetcode

Solution to some Leetcode problems written in C++

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

1187.cpp (1033B)

0 class Solution { 1 int dp[2001][2001][2]; 2 3 void norm(vector<int> &arr) { 4 sort(arr.begin(), arr.end()); 5 int i = 1, j = 1; 6 while (i < arr.size()) { 7 if (arr[i] != arr[i - 1]) arr[j++] = arr[i]; 8 i++; 9 } 10 arr.resize(j); 11 } 12 13 int rec(const vector<int> &arr1, const vector<int> &arr2, int i, int j, bool other) { 14 if (i >= arr1.size()) return 0; 15 int prev = !other ? i == 0 ? INT_MIN : arr1[i - 1] : arr2[j]; 16 j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin(); 17 if (dp[i][j][other]) return dp[i][j][other]; 18 19 int res = 2002; 20 if (j < arr2.size()) res = rec(arr1, arr2, i + 1, j, true) + 1; 21 if (prev < arr1[i]) res = min(res, rec(arr1, arr2, i + 1, j, false)); 22 return dp[i][j][other] = res; 23 } 24 25 public: 26 int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) { 27 norm(arr2); 28 int res = rec(arr1, arr2, 0, 0, false); 29 return res >= 2002 ? -1 : res; 30 } 31 };