# leetcode summary 901-950

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;
}
}```

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;
}

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 = nums;

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;
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 = nums;

// 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;
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], dp[i] 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] can only be transformed from dp[i-1]. Therefore, the state transition equation is as follows:

If S[i] is'1':
dp[i] = dp[i-1] + 1 \1 can only be converted from 0. Flip'1'to'0', and flip times plus 1
dp[i] = min(dp[i-1], dp[i-1]) \

If S[i] is'0':
dp[i] = dp[i-1] \
dp[i] = min(dp[i-1] + 1, dp[i-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;
}
}```

Tags: data structure

Posted by woozy on Tue, 31 May 2022 09:42:41 +0530