# 剑指 Offer 07. 重建二叉树

3


/ \
9 20
/ \
15 7

0 <= 节点个数 <= 5000

class Solution {
private:
TreeNode* buildTree(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir, unordered_map<int,int> &hash) {
if(pr < pl || ir < il) return NULL;
TreeNode *root = new TreeNode(preorder[pl]);
int im = hash[preorder[pl]];
int len_left = im - il, len_right = ir - im;
root->left = buildTree(preorder, pl + 1, pl + len_left, inorder, il, im - 1, hash);
root->right = buildTree(preorder, pl + len_left + 1, pr, inorder, im + 1, ir, hash);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int,int> hash;
for(int i = 0; i < inorder.size(); ++i) hash[inorder[i]] = i;

int n = preorder.size();
return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, hash);
}
};

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

# 剑指 Offer 03. 数组中重复的数字

[2, 3, 1, 0, 2, 5, 3]

2 <= n <= 100000

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

class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; ++i) {
while(nums[i] != i) {
if(nums[i] == nums[nums[i]]) return nums[i];
swap(nums[i],nums[nums[i]]);
}
}
return 0;
}
};

# LeetCode Avoid Flood in The City

1488. Avoid Flood in The City

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.

Given an integer array rains where:

• rains[i] > 0 means there will be rains over the rains[i] lake.
• rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

• ans.length == rains.length
• ans[i] == -1 if rains[i] > 0.
• ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.


Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.


Example 3:

Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.


Example 4:

Input: rains = [69,0,0,0,69]
Output: [-1,69,1,1,-1]
Explanation: Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 <= x,y <= 10^9


Example 5:

Input: rains = [10,20,20]
Output: []
Explanation: It will rain over lake 20 two consecutive days. There is no chance to dry any lake.


Constraints:

• 1 <= rains.length <= 10^5
• 0 <= rains[i] <= 10^9

class Solution {
public:
vector<int> avoidFlood(vector<int>& rains) {
int n = rains.size();

vector<int> ans;
unordered_map<int, int> full_lakes;
set<int> dry_days;

for (int i = 0; i < n; ++i) {
if (rains[i] == 0) {
dry_days.insert(i);
ans.push_back(1); // 先随便填一个数，后续会覆盖，填入真正要抽干的湖编号
}
else {
if (full_lakes.find(rains[i]) != full_lakes.end()) { // 这个湖之前就满了，需要抽干
int last_day = full_lakes[rains[i]];
set<int>::iterator it = dry_days.lower_bound(last_day); //从之前满的那天往后选不下雨的一天抽干
if (it == dry_days.end()) {
return {}; // 失败
}
ans[*it] = rains[i];
dry_days.erase(it);
}
full_lakes[rains[i]] = i; // 填入新的下雨日期
ans.push_back(-1);
}
}

return ans;
}
};

# LeetCode Making File Names Unique

1487. Making File Names Unique

Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a folder with the name names[i].

Since two files cannot have the same name, if you enter a folder name which is previously used, the system will have a suffix addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.

Return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.

Example 1:

Input: names = ["pes","fifa","gta","pes(2019)"]
Output: ["pes","fifa","gta","pes(2019)"]
Explanation: Let's see how the file system creates folder names:
"pes" --> not assigned before, remains "pes"
"fifa" --> not assigned before, remains "fifa"
"gta" --> not assigned before, remains "gta"
"pes(2019)" --> not assigned before, remains "pes(2019)"


Example 2:

Input: names = ["gta","gta(1)","gta","avalon"]
Output: ["gta","gta(1)","gta(2)","avalon"]
Explanation: Let's see how the file system creates folder names:
"gta" --> not assigned before, remains "gta"
"gta(1)" --> not assigned before, remains "gta(1)"
"gta" --> the name is reserved, system adds (k), since "gta(1)" is also reserved, systems put k = 2. it becomes "gta(2)"
"avalon" --> not assigned before, remains "avalon"


Example 3:

Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
Output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
Explanation: When the last folder is created, the smallest positive valid k is 4, and it becomes "onepiece(4)".


Example 4:

Input: names = ["wano","wano","wano","wano"]
Output: ["wano","wano(1)","wano(2)","wano(3)"]
Explanation: Just increase the value of k each time you create folder "wano".


Example 5:

Input: names = ["kaido","kaido(1)","kaido","kaido(1)"]
Output: ["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
Explanation: Please note that system adds the suffix (k) to current name even it contained the same suffix before.


Constraints:

• 1 <= names.length <= 5 * 10^4
• 1 <= names[i].length <= 20
• names[i] consists of lower case English letters, digits and/or round brackets.

class Solution {
public:
vector<string> getFolderNames(vector<string>& names) {
vector<string> ans;
unordered_map<string, int> show_times;
for (int i = 0; i < names.size(); ++i) {
if (show_times.find(names[i]) == show_times.end()) {
ans.push_back(names[i]);
show_times[names[i]] = 1;
}
else {
int k = show_times[names[i]];
string next_name = names[i] + "(" + to_string(k) + ")";
while (show_times.find(next_name) != show_times.end()) {
show_times[names[i]] = ++k;
next_name = names[i] + "(" + to_string(k) + ")";
}
ans.push_back(next_name);
show_times[next_name] = 1;
}
}
return ans;
}
};

# LeetCode Minimum Number of Days to Make m Bouquets

5455. Minimum Number of Days to Make m Bouquets

Given an integer array bloomDay, an integer m and an integer k.

We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.


Example 2:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.


Example 3:

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here's the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.


Example 4:

Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
Output: 1000000000
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.


Example 5:

Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
Output: 9


Constraints:

• bloomDay.length == n
• 1 <= n <= 10^5
• 1 <= bloomDay[i] <= 10^9
• 1 <= m <= 10^6
• 1 <= k <= n

class Solution {
bool IsValid(vector<int>& bloomDay, int day, int m, int k) {
int bouquets = 0, n = bloomDay.size();
int i = 0, good = 0;
while (i < n) {
while (i<n&&bloomDay[i]>day)++i;
if (i >= n)break;

int j = i;
while (j < n&&bloomDay[j] <= day)++j;
// [i,j) 都开花了

good += (j - i) / k;

i = j;
}
return good >= m;
}
public:
int minDays(vector<int>& bloomDay, int m, int k) {
int n = bloomDay.size();
if (m*k > n)return -1;

map<int, int> hash;
for (int i = 0; i < n; ++i)++hash[bloomDay[i]];
if (m*k == n)return (--hash.end())->first; // 最后一天

int unique_day = hash.size();
vector<int> days(unique_day, 0);
vector<int> num_bloomed(unique_day, 0);

int d = 0, nb = 0;
int left = 0, right = unique_day - 1, found_left = false;
for (map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) {
nb += it->second;
if (nb >= m * k && !found_left) {
left = d;
found_left = true;
}

days[d] = it->first;
num_bloomed[d] = nb;

++d;
}

while (left <= right) {
int mid = left + (right - left) / 2;
bool valid = IsValid(bloomDay, days[mid], m, k);
if (valid)right = mid - 1;
else left = mid + 1;
}

return days[right + 1];
}
};

# Leetcode Least Number of Unique Integers after K Removals

5454. Least Number of Unique Integers after K Removals

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.


Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length

class Solution {
public:
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
int n = arr.size();
vector<pair<int, int>> num_counts;
unordered_map<int, int> hash;
for (int i = 0; i < n; ++i)++hash[arr[i]];
for (unordered_map<int, int>::iterator it = hash.begin(); it != hash.end(); ++it) {
num_counts.push_back(make_pair(it->second, it->first));
}
sort(num_counts.begin(), num_counts.end());
int m = num_counts.size(), sum = 0;

if (k == 0)return m;
else if (k == n)return 0;

for (int i = 0; i < m; ++i) {
sum += num_counts[i].first;
if (sum == k)return m - i - 1;
else if (sum > k)return m - i;
}

return 0;
}
};


# LeetCode Destination City

5400. Destination City

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBiReturn the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".


Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are:
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
Clearly the destination city is "A".


Example 3:

Input: paths = [["A","Z"]]
Output: "Z"


Constraints:

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• All strings consist of lowercase and uppercase English letters and the space character.

class Solution {
public:
string destCity(vector<vector<string>>& paths) {
map<string, pair<int,int>> count;
for (int i = 0; i < paths.size(); ++i) {
string src = paths[i][0], dest = paths[i][1];
++count[src].first; // 出度
++count[dest].second; // 入度
}
for (map<string, pair<int, int>>::iterator it = count.begin(); it != count.end(); ++it) {
if (it->second.first == 0) {
return it->first;
}
}
return "";
}
};

# LeetCode First Unique Number

LeetCode First Unique Number

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

• FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
• int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
• void add(int value) insert value to the queue.

Example 1:

Input:
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:


[null,2,null,2,null,3,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2);            // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3);            // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1

Example 2:

Input:
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:


[null,-1,null,null,null,null,null,17]

Explanation: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); // return -1 firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3] firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7] firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17] firstUnique.showFirstUnique(); // return 17

Example 3:

Input:
[[[809]],[],[809],[]]
Output:


[null,809,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^8
• 1 <= value <= 10^8
• At most 50000 calls will be made to showFirstUnique and add.

class FirstUnique {
private:
list<int> uniques_;
unordered_map<int, list<int>::iterator> hash;
public:
FirstUnique(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
}
}

int showFirstUnique() {
if (uniques_.empty())return -1;
else return uniques_.front();
}

if (hash.find(value) == hash.end()) {
uniques_.push_back(value);
hash[value] = --uniques_.end();
}
else {
if (hash[value] != uniques_.end()) {
uniques_.erase(hash[value]);
hash[value] = uniques_.end();
}
}
}
};

# LeetCode Counting Elements

LeetCode Counting Elements

Given an integer array arr, count element x such that x + 1 is also in arr.

If there’re duplicates in arr, count them seperately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.


Example 3:

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.


Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.


Constraints:

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

class Solution {
public:
int countElements(vector<int>& arr) {
set<int> unique_nums;
for (int i = 0; i < arr.size(); ++i) {
unique_nums.insert(arr[i]);
}
int ans = 0;
for (int i = 0; i < arr.size(); ++i) {
if (unique_nums.find(arr[i] + 1) != unique_nums.end())++ans;
}
return ans;
}
};