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 XOR Operation in an Array

1486. XOR Operation in an Array

Given an integer n and an integer start.

Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.

Return the bitwise XOR of all elements of nums.

Example 1:

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.


Example 2:

Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.

Example 3:

Input: n = 1, start = 7
Output: 7


Example 4:

Input: n = 10, start = 5
Output: 2


Constraints:

• 1 <= n <= 1000
• 0 <= start <= 1000
• n == nums.length

class Solution {
public:
int xorOperation(int n, int start) {
int ans = 0;
for (int i = 0; i < n; ++i) {
ans ^= (start + 2 * i);
}
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 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;
}
};