Add C++

jinshendan · jinshendan · commit 4ee54262add9 · 2023-02-19T22:25:48.000+01:00
diff --git a/Problems/.DS_Store b/Problems/.DS_Store
diff --git a/Problems/23-Partition-Array-for-Maximum-Sum/Partition-Array-for-Maximum-Sum.cpp b/Problems/23-Partition-Array-for-Maximum-Sum/Partition-Array-for-Maximum-Sum.cpp
@@ -0,0 +1,22 @@
+class Solution {
+public:
+    int maxSumAfterPartitioning(vector<int>& arr, int k) {
+        int n = arr.size();
+        vector<long long> dp(n+1, 0);
+        dp[1] = arr[0];
+        for (int i = 2; i <= n; i++)
+        {
+            long long maxValue = -1;
+            for (int j = i-1; j >= max(0, i-k); j--)
+            {
+                if (arr[j] > maxValue) maxValue = arr[j];
+                long long cur  =  maxValue * (i - j) + dp[j];
+                if ( cur > dp[i])
+                {
+                    dp[i] = cur; 
+                }
+            }
+        }
+        return dp[n];
+    }
+};
diff --git a/Problems/24-Where-Will-the-Ball-Fall/Where-Will-the-Ball-Fall.cpp b/Problems/24-Where-Will-the-Ball-Fall/Where-Will-the-Ball-Fall.cpp
@@ -0,0 +1,29 @@
+class Solution {
+public:
+    vector<int> findBall(vector<vector<int>>& grid) {
+        int m = grid.size();
+        int n = grid[0].size();
+
+        vector<vector<int>> dp(m+1, vector<int>(n, -1));
+        for (int j = 0; j < n; j++) dp[m][j] = j;
+
+        for (int i = m-1; i >= 0; i--)
+        {
+            for (int j = n-1; j >= 0; j--)
+            {
+                if (j != n-1 and grid[i][j+1] == -1 and grid[i][j] == -1)
+                {
+                    dp[i][j+1] = dp[i+1][j];
+                }
+                else if (j != 0 and grid[i][j-1] == 1 and grid[i][j] == 1)
+                {
+                    dp[i][j-1] = dp[i+1][j];
+                }
+            }
+        }
+
+        vector<int> ans(n, 0);
+        for (int j = 0; j < n; j++) ans[j] = dp[0][j];
+        return ans;
+    }
+};
diff --git a/Problems/25-Flip-String-to-Monotone-Increasing/Flip-String-to-Monotone-Increasing.cpp b/Problems/25-Flip-String-to-Monotone-Increasing/Flip-String-to-Monotone-Increasing.cpp
@@ -0,0 +1,21 @@
+class Solution {
+public:
+    int minFlipsMonoIncr(string s) {
+        int n = s.length();
+        vector<int> accZero(n+1, 0);
+        for (int i = n-1; i>= 0; i--)
+        {
+            accZero[i] = accZero[i+1];
+            if (s[i] == '0') accZero[i]++;
+        }
+
+        int ans = accZero[0];
+        int numOne = 0;
+        for (int i = 0; i < n ; i++)
+        {
+            if (s[i] == '1') numOne++;
+            ans = min(ans, (numOne + accZero[i+1]));
+        }
+        return ans;
+    }
+};
diff --git a/Problems/26-Knight-Dialer/Knight-Dialer.cpp b/Problems/26-Knight-Dialer/Knight-Dialer.cpp
@@ -0,0 +1,25 @@
+class Solution {
+public:
+    int knightDialer(int n) {
+        const int M = 1000000007;
+        vector<vector<int>> dp(10, vector<int>(n+1, 0));
+        for (int i = 0; i < 10; i++) dp[i][0] = 1;
+
+        for (int j = 1; j < n; j++)
+        {
+            dp[1][j] = (dp[6][j-1] + dp[8][j-1]) % M;
+            dp[2][j] = (dp[7][j-1] + dp[9][j-1]) % M;
+            dp[3][j] = (dp[4][j-1] + dp[8][j-1]) % M;
+            dp[4][j] = ((dp[3][j-1] + dp[9][j-1]) % M + dp[0][j-1]) % M;
+            dp[5][j] = 0;
+            dp[6][j] = ((dp[1][j-1] + dp[7][j-1]) % M + dp[0][j-1]) % M;
+            dp[7][j] = (dp[2][j-1] + dp[6][j-1]) % M;
+            dp[8][j] = (dp[1][j-1] + dp[3][j-1]) % M;
+            dp[9][j] = (dp[2][j-1] + dp[4][j-1]) % M;
+            dp[0][j] = (dp[4][j-1] + dp[6][j-1]) % M;
+        }
+        int ans = 0;
+        for (int i = 0; i < 10; i++) ans = (ans + dp[i][n-1]) % M;
+        return ans;
+    }
+};
diff --git a/Problems/27-Ways-to-Make-a-Fair-Array/Ways-to-Make-a-Fair-Array.cpp b/Problems/27-Ways-to-Make-a-Fair-Array/Ways-to-Make-a-Fair-Array.cpp
@@ -0,0 +1,47 @@
+class Solution {
+public:
+    int waysToMakeFair(vector<int>& nums) {
+        int n = nums.size();
+        if (n == 1) return 1;
+
+        vector<int> v(n, 0);
+        v[0] = nums[0];
+        v[1] = nums[1];
+
+        for (int i = 2; i < n; i++)
+        {
+            v[i] = v[i-2] + nums[i];
+        }
+    
+        int lastEven = (n % 2 == 0)?(n-2):(n-1);
+        int lastOdd = (n % 2 == 1)?(n-2):(n-1);
+
+        int ans = 0;
+        for (int i = 0; i < n; i++)
+        {
+            if (i == 0)
+            {
+                if (v[lastEven] - v[0] == v[lastOdd]) ans++;
+            }
+            else if (i == 1)
+            {
+                if (v[0] + v[lastOdd] - v[1] == v[lastEven] - v[0]) ans++;
+            }
+            else
+            if (i % 2 == 0) 
+            {
+                auto sumEven = v[i-2] + v[lastOdd] - v[i-1];
+                auto sumOdd = v[i-1] + v[lastEven] - v[i];
+                if (sumEven == sumOdd) ans++;
+            }
+            else
+            {
+                auto sumEven = v[i-1] + v[lastOdd] - v[i];
+                auto sumOdd = v[i-2] + v[lastEven] - v[i-1];
+                if (sumEven == sumOdd) ans++;
+
+            }
+        }
+        return ans;
+    }
+};
diff --git a/README.md b/README.md
@@ -28,7 +28,11 @@ Solutions in various programming languages are provided. Enjoy it.
 20. 2023/02/11 [#2405 Optimal Partition of String](https://github.com/LeetcodeRush/Leetcode/tree/main/Problems/20-Optimal-Partition-of-String): Greedy
 21. 2023/02/12 [#1529 Minimum Suffix Flips](https://github.com/LeetcodeRush/Leetcode/tree/main/Problems/21-Minimum-Suffix-Flips): Greedy
 22. 2023/02/13 [#1768 Merge Strings Alternately](https://github.com/LeetcodeRush/Leetcode/tree/main/Problems/22-Merge-Strings-Alternately): String
-
+23. 2023/02/14 [#1043 Partition Array for Maximum Sum](): DP
+24. 2023/02/15 [#1706 Where Will the Ball Fall](): DP
+25. 2023/02/16 [#926 Flip String to Monotone Increasing](): DP
+26. 2023/02/17 [#935 Knight Dialer](): DP
+27. 2023/02/18 [#1664 Ways to Make a Fair Array](): DP
 
 ## Weekly Contest
 
