901. stock price span
Description:
Idea: monotone stack.
class StockSpanner { Stack<Integer> prices, weights; public StockSpanner() { prices = new Stack(); weights = new Stack(); } public int next(int price) { int w = 1; while (!prices.isEmpty() && prices.peek() <= price) { prices.pop(); w += weights.pop(); } prices.push(price); weights.push(w); return w; } }
904. fruit baskets
Description:
Idea: the problem can be regarded as the longest continuous subsequence. A sequence can contain up to two elements.
907. sum of minimum values of subarray
Description:
Idea:
class Solution { public int sumSubarrayMins(int[] A) { int MOD = 1_000_000_007; Stack<RepInteger> stack = new Stack(); int ans = 0, dot = 0; for (int j = 0; j < A.length; ++j) { // Add all answers for subarrays [i, j], i <= j int count = 1; while (!stack.isEmpty() && stack.peek().val >= A[j]) { RepInteger node = stack.pop(); count += node.count; dot -= node.val * node.count; } stack.push(new RepInteger(A[j], count)); dot += A[j] * count; ans += dot; ans %= MOD; } return ans; } } class RepInteger { int val, count; RepInteger(int v, int c) { val = v; count = c; } }
910. minimum difference II
Description:
Idea: the key point is that at a certain node, all the previous numbers add K, and all the subsequent numbers subtract K
915 Split array
Description:
Idea: auxiliary array stores the largest element on the left.
918. maximum sum of circular subarrays
Description:
Idea:
import java.util.Arrays; public class Solution { public int maxSubarraySumCircular(int[] A) { int len = A.length; // Special case judgment if (len == 0) { return 0; } if (len == 1) { return A[0]; } int maxSubArray = maxSubArray(A); int minSubArrayExcludeHeadAndTail = minSubArray(A); int sum = 0; for (int value : A) { sum += value; } return Math.max(maxSubArray, sum - minSubArrayExcludeHeadAndTail); } public int maxSubArray(int[] nums) { int len = nums.length; // dp[i]: with nums[i] Ending「continuity」Maximum sum of subintervals int[] dp = new int[len]; dp[0] = nums[0]; for (int i = 1; i < len; i++) { if (dp[i - 1] >= 0) { dp[i] = dp[i - 1] + nums[i]; } else { // dp[i - 1] < 0 When, the front part is discarded dp[i] = nums[i]; } } // Scan the whole world to find the maximum value int res = dp[0]; for (int i = 1; i < len; i++) { res = Math.max(res, dp[i]); } return res; } public int minSubArray(int[] nums) { // Ideas and maxSubArray Completely consistent. Change the maximum to the minimum // But the sum of intervals here does not include the head and tail int len = nums.length; // dp[i]: with nums[i] Ending「continuity」Minimum sum of subintervals int[] dp = new int[len]; dp[0] = nums[0]; // take care i Subscript of for (int i = 1; i < len - 1; i++) { if (dp[i - 1] >= 0) { // Adding the previous number will make the result larger, so the previous part is discarded dp[i] = nums[i]; } else { dp[i] = dp[i - 1] + nums[i]; } } // Scan the whole world to find the minimum value int res = dp[0]; for (int i = 1; i < len; i++) { res = Math.min(res, dp[i]); } return res; } public static void main(String[] args) { Solution solution = new Solution(); // int[] A = {1, -2, 3, -2}; // int[] A = {5, -3, 5}; int[] A = {3, -1, 2, -1}; int res = solution.maxSubarraySumCircular(A); System.out.println(res); } }
There are two cases, one is the case of not crossing the boundary, and the other is the case of crossing the boundary
If there is no boundary crossing, the maximum sum of subarrays can be obtained directly;
In the case of crossing the boundary, we can sum the array and subtract the minimum sum of acyclic subarrays to get the maximum sum of subarrays in the case of crossing the boundary;
921. minimum additions to make parentheses valid
Description:
Idea: stack
class Solution { public: int minAddToMakeValid(string S) { stack<char> temp; for(int i=0;i<S.size();i++) { if(temp.empty()) { temp.push(S[i]); } else{ if(S[i]==')'&&temp.top()=='(') { temp.pop(); } else{ temp.push(S[i]); } } } return temp.size(); } };
923. multiple possibilities of the sum of three numbers
Description:
Idea: this can be done through hashmap <num, count>.
Dynamic planning can also be used. dp[n][j][k] refers to the number in which the sum of J numbers in the first n numbers is K.
First, dp[i][j][k] represents the number of schemes with K size selected from the first I numbers. The definition here is extended from the definition of 01 knapsack. A constraint is added here, which is to select J arrays from the previous I numbers into k size. The advantage of this is that if the last number is selected, dp[i - 1][j - 1][k - A[i]] can be simply used to calculate the total number of choices excluding the last number according to the defined optimal substructure properties; If the last number is not selected, the unselected number will be added directly, that is, dp[i - 1][j][k].
926. flip string to monotonic increment
Description:
Idea:
dp[i][0], dp[i][1] respectively represents the minimum number of flips for the final selection of 0 and 1 by the character S[i],
Considering the increment, dp[i][0] can only be transformed from dp[i-1][0]. Therefore, the state transition equation is as follows:
If S[i] is'1':
dp[i][0] = dp[i-1][0] + 1 \1 can only be converted from 0. Flip'1'to'0', and flip times plus 1
dp[i][1] = min(dp[i-1][0], dp[i-1][1]) \
If S[i] is'0':
dp[i][0] = dp[i-1][0] \
dp[i][1] = min(dp[i-1][0] + 1, dp[i-1][1] + 1) \
class Solution: def minFlipsMonoIncr(self, S: str) -> int: zero, one = 0, 0 for c in S: if c == '1': one, zero = min(zero, one), zero + 1 else: one = min(zero + 1, one + 1) return min(zero, one)
930. same binary subarray as
Description:
Idea: prefix and +hash
931. descending path minimum sum
Description;
Idea: dynamic planning, from bottom to top.
939. minimum area rectangle
Description:
Idea: put all the points into the set, enumerate the two points on the diagonal of the rectangle, and judge whether the other two points appear in the set. For example, when enumerating to (1,1) and (5,5), we need to determine whether (1,5) and (5,1) also appear in the set.
945. minimum increment to make the array unique
Description:
Idea:
class Solution { public int minIncrementForUnique(int[] A) { // Sort first Arrays.sort(A); int move = 0; // Traverses the array. If the current element is less than or equal to its previous element, it becomes the previous number+1 for (int i = 1; i < A.length; i++) { if (A[i] <= A[i - 1]) { int pre = A[i]; A[i] = A[i - 1] + 1; move += A[i] - pre; } } return move; } }
946. verify stack sequence
Description;
Idea:
class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { int N = pushed.length; Stack<Integer> stack = new Stack(); int j = 0; for (int x: pushed) { stack.push(x); while (!stack.isEmpty() && j < N && stack.peek() == popped[j]) { stack.pop(); j++; } } return j == N; } }
948. token placement
Description: L
Idea: if we play the game of token placement, we must find the token with the least energy when making the token face up. Similarly, when making the token face up, you must find the token with the most energy.
class Solution { public int bagOfTokensScore(int[] tokens, int P) { Arrays.sort(tokens); int lo = 0, hi = tokens.length - 1; int points = 0, ans = 0; while (lo <= hi && (P >= tokens[lo] || points > 0)) { while (lo <= hi && P >= tokens[lo]) { P -= tokens[lo++]; points++; } ans = Math.max(ans, points); if (lo <= hi && points > 0) { P += tokens[hi--]; points--; } } return ans; } }