# LeetCode Maximum Length of Subarray With Positive Product

1567. Maximum Length of Subarray With Positive Product

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.


Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].


Example 4:

Input: nums = [-1,2]
Output: 1


Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4


Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
vector<int> dp_pos(n, 0), dp_neg(n, 0);
if(nums[0] > 0) dp_pos[0] = 1;
else if(nums[0] < 0) dp_neg[0] = 1;
int ans = dp_pos[0];
for(int i = 1; i < n; ++i) {
if(nums[i] > 0) {
dp_pos[i] = dp_pos[i - 1] + 1;
dp_neg[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
} else if(nums[i] < 0) {
dp_pos[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
dp_neg[i] = dp_pos[i - 1] + 1;
}
ans = max(ans, dp_pos[i]);
}
return ans;
}
};

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
int pos_len = 0, neg_len = 0;
if(nums[0] > 0) pos_len = 1;
else if(nums[0] < 0) neg_len = 1;
int ans = pos_len;
for(int i = 1; i < n; ++i) {
if(nums[i] > 0) {
++pos_len;
neg_len = neg_len > 0 ? neg_len + 1 : 0;
} else if(nums[i] < 0) {
int tmp = pos_len;
pos_len = neg_len > 0 ? neg_len + 1 : 0;
neg_len = tmp + 1;
} else if(nums[i] == 0) {
pos_len = neg_len = 0;
}
ans = max(ans, pos_len);
}
return ans;
}
};

# LeetCode Detect Pattern of Length M Repeated K or More Times

5499. Detect Pattern of Length M Repeated K or More Times

Given an array of positive integers arr,  find a pattern of length m that is repeated k or more times.

pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.


Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.


Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.


Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.


Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.


Constraints:

• 2 <= arr.length <= 100
• 1 <= arr[i] <= 100
• 1 <= m <= 100
• 2 <= k <= 100

class Solution {
public:
bool containsPattern(vector<int>& arr, int m, int k) {
int n = arr.size();
if(m * k > n) return false;
for(int i = 0; i < n; ++i) {
int rep = 0;
for(int j = i; j < n; j += m) {
bool good = true;
for(int u = 0; u < m; ++u) {
if(u + j >= n || arr[u + j] != arr[i + u]) {
good = false;
break;
}
}
if(!good) break;
else ++rep;
}
if(rep >= k) return true;
}
return false;
}
};

# LeetCode K Closest Points to Origin

973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].


Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)


Note:

1. 1 <= K <= points.length <= 10000
2. -10000 < points[i][0] < 10000
3. -10000 < points[i][1] < 10000

1.先排序（快排）时间复杂度为nlogn
2.建堆，堆的大小为K，建立大根堆或者小根堆，时间复杂度为nlogK(如果要求出前K个较大的，那么就建立小根堆，一旦比堆顶大，那么就入堆)；
3.结合快速排序划分的方法，不断减小问题的规模

class Solution {
private:
vector<int> origin;

int CalDist(vector<int> &p1, vector<int> &p2) {
return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
}

void MySwap(vector<vector<int>>& points, int u, int v) {
swap(points[u][0], points[v][0]);
swap(points[u][1], points[v][1]);
}

void Work(vector<vector<int>>& points, int l, int r, int K) {
if (l >= r) return;

int pivot = r;
int pdist = CalDist(points[pivot], origin);
int i = l;
for (int j = l; j < r; ++j) {
int idist = CalDist(points[j], origin);
if (idist < pdist) {
MySwap(points, i++, j);
}
}
MySwap(points, i, pivot);

if (K == i)return;
else if (K < i)Work(points, l, i - 1, K);
else Work(points, i + 1, r, K);
}
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
origin = { 0, 0 }; // 求与该点距离最近的top-k个点，本题中该点是原点

for (int i = 0; i < points.size(); ++i) {
printf("x=%d,y=%d,dist=%d\n", points[i][0], points[i][1], CalDist(points[i], origin));
}

Work(points, 0, points.size() - 1, K - 1);

vector<vector<int>> ans;
for (int i = 0; i < K; ++i) ans.push_back(points[i]);
return ans;
}
};

# LeetCode Maximum Sum Circular Subarray

918. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3


Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10


Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4


Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3


Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1


Note:

1. -30000 <= A[i] <= 30000
2. 1 <= A.length <= 30000

LeetCode Maximum Subarray的升级版，即数组首尾相连了。我一开始想到的解法是，既然数组首尾相连了，那就2*n次dp即可，即把原数组复制一遍，接到原数组后面，形成2*n长的数组，然后照样跑原来的DP算法。这个解法是不对的，比如如果数组是[1,2,3,4]这种全是正数，则跑2n遍之后，ans会一直max更新，导致最后的ans是1+…+4+1+…4，即数组加了两遍，每个数重复加了。另外对于数组[5,-3,5]这种，也会完整数组加两遍。

class Solution {
public:
int maxSubarraySumCircular(vector<int>& A) {
int n = A.size();
vector<int> dp(n, 0);

// 最大连续子串
dp[0] = A[0];
int ans1 = A[0], sum = A[0];
for(int i = 1; i < n; ++i) {
dp[i] = max(dp[i - 1], 0) + A[i];
ans1 = max(ans1, dp[i]);

sum += A[i];
}

// 最小连续子串
fill(dp.begin(), dp.end(), 0);
dp[0] = A[0];
int ans2 = A[0];
for(int i = 1; i < n; ++i) {
dp[i] = min(dp[i - 1], 0) + A[i];
ans2 = min(ans2, dp[i]);
}

if(ans2 == sum) ans2 = INT_MIN; // 注意最小连续子串和不能是全长数组
else ans2 = sum - ans2;

return max(ans1, ans2);
}
};

# LeetCode Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).


Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3


Example 4:

Input: nums = [0,0,0], target = 0
Output: 3


Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6

class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
int n = nums.size();
vector<int> dp(n + 1, 0);
for(int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
int sum = 0;
for(int j = i; j > 0 && dp[j] == dp[i]; --j) {
sum += nums[j - 1];
if(sum == target) dp[i] = max(dp[i], dp[j - 1] + 1);
}
}
return dp[n];
}
};

class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
int n = nums.size();
unordered_map<int, int> hash;
hash[0] = -1;
int prefix_sum = 0, right_most = -1;
int ans = 0;
for(int i = 0; i < n; ++i) {
prefix_sum += nums[i];
int supplement = prefix_sum - target;
if(hash.find(supplement) != hash.end()) {
int left = hash[supplement];
if(left >= right_most) {
++ans;
right_most = i;
}
}
hash[prefix_sum] = i;
}
return ans;
}
};

# LeetCode Find Kth Bit in Nth Binary String

5484. Find Kth Bit in Nth Binary String

Given two positive integers n and k, the binary string  Sn is formed as follows:

• S1 = "0"
• Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".


Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001". The 11th bit is "1".


Example 3:

Input: n = 1, k = 1
Output: "0"


Example 4:

Input: n = 2, k = 3
Output: "1"


Constraints:

• 1 <= n <= 20
• 1 <= k <= 2n - 1

class Solution {
private:
string InvertStr(string &s) {
string ans = "";
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '0')ans.push_back('1');
else ans.push_back('0');
}
return ans;
}
public:
char findKthBit(int n, int k) {
string s = "0";
for (int i = 2; i <= n; ++i) {
string inv_str = InvertStr(s);
reverse(inv_str.begin(), inv_str.end());
s = s + "1" + inv_str;
}
return s[k - 1];
}
};

# LeetCode Make The String Great

5483. Make The String Great

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

• 0 <= i <= s.length - 2
• s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".


Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""


Example 3:

Input: s = "s"
Output: "s"


Constraints:

• 1 <= s.length <= 100
• s contains only lower and upper case English letters.

class Solution {
public:
string makeGood(string s) {
stack<char> stk;
for(int i = 0; i < s.size(); ++i) {
if(!stk.empty() && abs(stk.top() - s[i]) == 32) {
stk.pop();
} else {
stk.push(s[i]);
}
}
string ans="";
while(!stk.empty()) {
ans = string(1, stk.top()) + ans;
stk.pop();
}
return ans;
}
};

# LeetCode Coin Change 2

518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1


Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.


Example 3:

Input: amount = 10, coins = [10]
Output: 1


Note:

You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

LeetCode Coin Change类似，也用动态规划。假设dp[i][j]表示用前i硬币，凑齐j块钱的方案数。则有两种情况，一是不用第i类硬币，有dp[i-1][j]种情况；二是用第i类硬币，则还需要凑齐j-coins[i]块钱，因为每类硬币无穷个，所以还是用前i类硬币凑齐j-coins[i]块钱，即有dp[i][j-coins[i]]种情况。两种情况数相加即可。完整代码如下：

class Solution {
public:
int change(int amount, vector<int>& coins) {
if(amount == 0) return 1;
int n = coins.size();
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
for(int i = 0; i <= n; ++i) dp[i][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= amount; ++j) {
dp[i][j] = dp[i - 1][j];
if(j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
}
}
return dp[n][amount];
}
};

# LeetCode Number of Good Leaf Nodes Pairs

5474. Number of Good Leaf Nodes Pairs

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.


Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.


Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].


Example 4:

Input: root = [100], distance = 1
Output: 0


Example 5:

Input: root = [1,1,1], distance = 2
Output: 1


Constraints:

• The number of nodes in the tree is in the range [1, 2^10].
• Each node’s value is between [1, 100].
• 1 <= distance <= 10

class Solution {
private:
void CollectLeaves(TreeNode *root, unordered_map<TreeNode*, vector<TreeNode*>> &all_paths, vector<TreeNode*> &one_path) {
if (root == NULL)return;
one_path.push_back(root);
if (root->left == NULL && root->right == NULL) {
all_paths[root] = one_path;
}
else {
CollectLeaves(root->left, all_paths, one_path);
CollectLeaves(root->right, all_paths, one_path);
}
one_path.pop_back();
}
int CalDist(vector<TreeNode*> &path1, vector<TreeNode*> &path2) {
int m = path1.size(), n = path2.size();
int i = 0;
while (i < m&&i < n) {
if (path1[i] != path2[i])break;
++i;
}
return (m - i) + (n - i);
}

public:
int countPairs(TreeNode* root, int distance) {
unordered_map<TreeNode*, vector<TreeNode*>> all_paths;
vector<TreeNode*> one_path;
CollectLeaves(root, all_paths, one_path);
vector<TreeNode*> leaves;
for (unordered_map<TreeNode*, vector<TreeNode*>>::iterator it = all_paths.begin(); it != all_paths.end(); ++it) {
leaves.push_back(it->first);
}

int ans = 0;
for (int i = 0; i < leaves.size(); ++i) {
for (int j = i + 1; j < leaves.size(); ++j) {
int d = CalDist(all_paths[leaves[i]], all_paths[leaves[j]]);
if (d <= distance)++ans;
}
}

return ans;
}
};

# LeetCode Bulb Switcher IV

5473. Bulb Switcher IV

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

• Choose any bulb (index i) of your current configuration.
• Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".


Example 3:

Input: target = "00000"
Output: 0


Example 4:

Input: target = "001011101"
Output: 5


Constraints:

• 1 <= target.length <= 10^5
• target[i] == '0' or target[i] == '1'

0. 00000
1. 11111
2. 10000
3. 10111

class Solution {
public:
int minFlips(string target) {
int n = target.size();
int ans = 0;
int  i = 0;
while (i < n) {
int j = i + 1;
while (j < n&&target[j] == target[i])++j;
++ans;
i = j;
}
if (target[0] == '0')return ans - 1;
else return ans;
}
};