Add C++ Solution 13 14 15

jinshendan · jinshendan · commit df95f778ff11 · 2023-02-07T00:46:24.000+01:00
diff --git a/Problems/.DS_Store b/Problems/.DS_Store
diff --git a/Problems/13-Max-Consecutive-Ones-III/Max-Consecutive-Ones-III.cpp b/Problems/13-Max-Consecutive-Ones-III/Max-Consecutive-Ones-III.cpp
@@ -0,0 +1,29 @@
+class Solution {
+public:
+    int longestOnes(vector<int>& nums, int k) {
+        int n = nums.size();
+        vector<int> prefixSum(n+1, 0);
+        for (int i = 1; i <= n; i++) prefixSum[i] = prefixSum[i-1] + nums[i-1];
+
+        int res = 0;
+        for (int i = 1; i <= n; i++)
+        {
+            int left  = i;
+            int right = n;
+
+            int ans = 0;
+            while (left <= right)
+            {
+                int mid = (right-left)/2+left;
+                int num0 = (mid-i+1)-prefixSum[mid] + prefixSum[i-1];   // in [i..mid]
+                if (num0 <= k) {ans = mid; left = mid + 1;}
+                else {right = mid-1;}
+            }
+
+            res = max(res, ans - i + 1);
+        }
+        
+        return res;
+        
+    }
+};
diff --git a/Problems/14-Search-a-2D-Matrix/Search-a-2D-Matrix.cpp b/Problems/14-Search-a-2D-Matrix/Search-a-2D-Matrix.cpp
@@ -0,0 +1,26 @@
+class Solution {
+public:
+    int getValue(vector<vector<int>>& matrix, int mid)
+    {
+        int n = matrix.size();
+        int m = matrix[0].size();
+        int i = mid / m;
+        int j = mid % m;
+        return matrix[i][j];
+    }
+
+    bool searchMatrix(vector<vector<int>>& matrix, int target) {
+        int n = matrix.size();
+        int m = matrix[0].size();
+        int left = 0, right = n * m-1;
+        while (left <= right)
+        {
+            int mid = (right - left)/2+left;
+            int value = getValue(matrix, mid);
+            if (target == value) return true;
+            if (target < value) right = mid-1;
+            else left = mid + 1;
+        }
+        return false;
+    }
+};
diff --git a/Problems/15-Maximum-Tastiness-of-Candy-Basket/Maximum-Tastiness-of-Candy-Basket.cpp b/Problems/15-Maximum-Tastiness-of-Candy-Basket/Maximum-Tastiness-of-Candy-Basket.cpp
@@ -0,0 +1,33 @@
+class Solution {
+public:
+    bool check(int x, vector<int>& price, int k)
+    {
+        int n = price.size();
+        int last = 0;
+        int idx = 1;
+        for (int i = 1; i < k; i++)
+        {
+            while (idx < n && price[idx] - price[last] < x) idx++;
+            if (idx == n) return false;
+            last = idx;
+            idx++;
+        }
+        return true;
+    }
+    int maximumTastiness(vector<int>& price, int k) {
+        sort(price.begin(), price.end());
+        int left = 0, right = price[price.size()-1] - price[0];
+        int ans = 0;
+        while (left <= right)
+        {
+            int mid = (right-left)/2+left;
+            if (check(mid, price, k))
+            {
+                ans = mid;
+                left = mid+1;
+            }
+            else right = mid-1;
+        }
+        return ans;
+    }
+};
