# 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 Number of Good Pairs

1512. Number of Good Pairs

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.


Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.


Example 3:

Input: nums = [1,2,3]
Output: 0


Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int ans = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] == nums[j])++ans;
}
}
return ans;
}
};

# 剑指 Offer 06. 从尾到头打印链表

0 <= 链表长度 <= 10000

class Solution {
public:
vector<int> ans;
}
int i = 0, j = ans.size() - 1;
while(i < j) {
swap(ans[i++], ans[j--]);
}
return ans;
}
};

# Leetcode Running Sum of 1d Array

5453. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]


Constraints:

• 1 <= nums.length <= 1000
• -10^6 <= nums[i] <= 10^6

class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, 0);
ans[0] = nums[0];
for (int i = 1; i < n; ++i)ans[i] = ans[i - 1] + nums[i];
return ans;
}
};

# LCP 06. 拿硬币

LCP 06. 拿硬币

• 1 <= n <= 4
• 1 <= coins[i] <= 10

class Solution {
public:
int minCount(vector<int>& coins) {
int ans = 0;
for (int i = 0; i < coins.size(); ++i) {
ans += (coins[i] / 2);
if (coins[i] % 2 == 1)++ans;
}
return ans;
}
};

# LeetCode Count Number of Teams

1395. Count Number of Teams

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (ijk) with rating (rating[i]rating[j]rating[k]).
• A team is valid if:  (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).


Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.


Example 3:

Input: rating = [1,2,3,4]
Output: 4


Constraints:

• n == rating.length
• 1 <= n <= 200
• 1 <= rating[i] <= 10^5

class Solution {
public:
int numTeams(vector<int>& rating) {
int ans = 0, n = rating.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if (rating[i] < rating[j] && rating[j] < rating[k])++ans;
else if (rating[i] > rating[j] && rating[j] > rating[k])++ans;
}
}
}
return ans;
}
};

class Solution {
public:
int numTeams(vector<int>& rating) {
int ans = 0, n = rating.size();
for (int i = 1; i < n - 1; ++i) {
vector<int> less_num(2, 0), greater_num(2, 0);
for (int j = 0; j < n; ++j) {
if (rating[j] < rating[i])++less_num[j < i];
else if (rating[j] > rating[i])++greater_num[j > i];
}
ans += less_num[1] * greater_num[1] + less_num[0] * greater_num[0];
}
return ans;
}
};


# LeetCode Create Target Array in the Given Order

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

• Initially target array is empty.
• From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
• Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]


Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]
Output: [0,1,2,3,4]
Explanation:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]


Example 3:

Input: nums = [1], index = [0]
Output: [1]


Constraints:

• 1 <= nums.length, index.length <= 100
• nums.length == index.length
• 0 <= nums[i] <= 100
• 0 <= index[i] <= i

class Solution {
public:
vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
int n = nums.size();
vector<int> ans;
for (int i = 0; i < n; ++i) {
ans.insert(ans.begin() + index[i], nums[i]);
}
return ans;
}
};

# LeetCode Lucky Numbers in a Matrix

1380. Lucky Numbers in a Matrix

Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column


Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.


Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]


Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= n, m <= 50
• 1 <= matrix[i][j] <= 10^5.
• All elements in the matrix are distinct.

class Solution {
public:
vector<int> luckyNumbers(vector<vector<int>>& matrix) {
vector<int> ans;
int m = matrix.size(), n = matrix[0].size();
vector<int> rowmin(m, INT_MAX), colmax(n, INT_MIN);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
rowmin[i] = min(rowmin[i], matrix[i][j]);
colmax[j] = max(colmax[j], matrix[i][j]);
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (rowmin[i] == colmax[j])ans.push_back(rowmin[i]);
}
}
return ans;
}
};

# LeetCode Bulb Switcher III

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

At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.

Return the number of moments in which all turned on bulbs are blue.

Example 1:

Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.


Example 2:

Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).


Example 3:

Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.


Example 4:

Input: light = [2,1,4,3,6,5]
Output: 3


Example 5:

Input: light = [1,2,3,4,5,6]
Output: 6


Constraints:

• n == light.length
• 1 <= n <= 5 * 10^4
• light is a permutation of  [1, 2, ..., n]

Discuss

class Solution {
public:
int numTimesAllBlue(vector<int>& light) {
int ans = 0;
int curmax = 0;
for (int i = 0; i < light.size(); ++i) {
curmax = max(curmax, light[i]);
if (curmax == i + 1)++ans;
}
return  ans;
}
};

# LeetCode Print Binary Tree

Print a binary tree in an m*n 2D string array following these rules:

1. The row number m should be equal to the height of the given binary tree.
2. The column number n should always be an odd number.
3. The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
4. Each unused space should contain an empty string "".
5. Print the subtrees following the same rules.

Example 1:

Input:
1
/
2
Output:
[["", "1", ""],
["2", "", ""]]


Example 2:

Input:
1
/ \
2   3
\
4
Output:
[["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]]


Example 3:

Input:
1
/ \
2   5
/
3
/
4
Output:

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]


Note: The height of binary tree is in the range of [1, 10].

class Solution {
public:
int height(TreeNode* root) {
if (root == NULL)return 0;
if (root->left == NULL && root->right == NULL)return 1;
int lh = height(root->left), rh = height(root->right);
return (lh > rh ? lh : rh) + 1;
}
void work(TreeNode* root, vector<vector<string>>& strTree,int layer,int left,int right) {
if (root == NULL)return;
int mid = (left + right) / 2;
strTree[layer][mid] = to_string(root->val);
work(root->left, strTree, layer + 1, left, mid - 1);
work(root->right, strTree, layer + 1, mid + 1, right);
}
vector<vector<string>> printTree(TreeNode* root) {
int h = height(root);
vector<vector<string>> strTree(h, vector<string>((1 << h) - 1, ""));
work(root, strTree, 0, 0, strTree[0].size() - 1);
return strTree;
}
};