# 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 Minimum Number of Frogs Croaking

Given the string croakOfFrogs, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid “croak” means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid “croak” return -1.

Example 1:

Input: croakOfFrogs = "croakcroak"
Output: 1
Explanation: One frog yelling "croak" twice.


Example 2:

Input: croakOfFrogs = "crcoakroak"
Output: 2
Explanation: The minimum number of frogs is two.
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".


Example 3:

Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.


Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1


Constraints:

• 1 <= croakOfFrogs.length <= 10^5
• All characters in the string are: 'c''r''o''a' or 'k'.

class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
map<char, char> pre = { {'r','c'},{'o','r'},{'a','o'},{'k','a'} };
vector<vector<char>> ans;
map<char, int> count;
for (int i = 0; i < croakOfFrogs.size(); ++i) {
int letter = croakOfFrogs[i];
++count[letter];
if (!(count['c'] >= count['r'] && count['r'] >= count['o'] && count['o'] >= count['a'] && count['a'] >= count['k']))return -1;
if (letter == 'c') {
if (ans.empty()) {
ans.push_back({ 'c' });
}
else {
bool found = false;
for (int j = 0; j < ans.size(); ++j) {
if (ans[j].empty()) {
ans[j].push_back('c');
found = true;
break;
}
}
if (!found) {
ans.push_back({ 'c' });
}
}
}
else {
if (ans.empty())return -1;
else {
bool found = false;
for (int j = 0; j < ans.size(); ++j) {
if (!ans[j].empty() && ans[j].back() == pre[letter]) {
ans[j].push_back(letter);
found = true;
if (letter == 'k')ans[j].clear();
break;
}
}
if (!found)return -1;
}
}
}

for (int j = 0; j < ans.size(); ++j) {
if (!ans[j].empty())return -1;
}

return ans.size();
}
};

class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
int n = croakOfFrogs.size();
map<char, int> count;
int free = 0, ans = 0;
for (int i = 0; i < croakOfFrogs.size(); ++i) {
char letter = croakOfFrogs[i];
++count[letter];
if (!(count['c'] >= count['r'] && count['r'] >= count['o'] && count['o'] >= count['a'] && count['a'] >= count['k']))return -1;
if (letter == 'c'&&free == 0) {
++ans;
}
else if (letter == 'c'&&free > 0) {
--free;
}
else if (letter == 'k') {
++free;
}
}
if (count['c'] != count['k'])return -1;
return ans;
}
};


# LeetCode Dota2 Senate

LeetCode Dota2 Senate In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

1. Ban one senator's right: A senator can make another senator lose all his rights in this and all the following rounds.
2. Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.
Given a string representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n. The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure. Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire. Example 1:
Input: "RD"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:
Input: "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Note:
1. The length of the given string will in the range [1, 10,000].

1. DXDRR
2. DXDXR
3. XXDXR
4. XXDXX
Dire胜利；第一个D如果杀其后的第二个R：
1. DRDXR
2. DRXXR
3. XRXXR
Radiant胜利。 这其实很好理解，因为是round-based的投票方式，对于D来说，他必须首先把其后的第一个R杀掉，要不然很快就会轮到这个R杀己方人员了。 round-based的方式是用%n的方式实现，代码如下： [cpp] class Solution { public: string predictPartyVictory(string senate) { int r_cnt = 0, d_cnt = 0, n = senate.size(); for (int i = 0; i < n; ++i) { if (senate[i] == ‘R’) ++r_cnt; else ++d_cnt; } int pos = 0; while (r_cnt > 0 && d_cnt > 0) { if (senate[pos] == ‘X’) { pos = (pos + 1) % n; continue; } int pos_next = (pos + 1) % n; while (senate[pos_next] == senate[pos] || senate[pos_next] == ‘X’) pos_next = (pos_next + 1) % n; if (senate[pos_next] == ‘R’) –r_cnt; else –d_cnt; senate[pos_next] = ‘X’; pos = (pos + 1) % n; } return r_cnt == 0 ? "Dire" : "Radiant"; } }; [/cpp] 本代码提交AC，用时752MS。]]>

# LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard Imagine you have a special keyboard with the following keys: Key 1: (A): Prints one ‘A’ on screen. Key 2: (Ctrl-A): Select the whole screen. Key 3: (Ctrl-C): Copy selection to buffer. Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed. Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of ‘A’ you can print on screen. Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:
Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:
1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

• A: 打印一个字符A
• Ctrl-A: 全选
• Ctrl-C: 复制
• Ctrl-V: 粘贴

# LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order. Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:
1. The number of given pairs will be in the range [1, 1000].

# LeetCode Remove K Digits

LeetCode Remove K Digits Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

# LeetCode Coin Change

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1


Note:
You may assume that you have an infinite number of each kind of coin.

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

class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<vector<long long>> dp(n + 1, vector<long long>(amount + 1, 0));
for(int j = 1; j <= amount; ++j) dp[0][j] = INT_MAX;

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] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
}
}
if(dp[n][amount] >= INT_MAX) return -1;
else return dp[n][amount];
}
};

# LeetCode Course Schedule III

LeetCode Course Schedule III There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day. Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken. Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation:
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:
1. The integer 1 <= d, t, n <= 10,000.
2. You can’t take two courses simultaneously.

1. 选修第一门课程，now=3<8，优先队列堆顶为3
2. 选修第二门课程，now=3+7=10<=10，优先队列堆顶为7
3. 选修第三门课程，now=10+5=15>14，失败；发现堆顶课程的持续时间是7，大于当前课程的持续时间5，所以可以把堆顶课程换成该门课程，则新的now=10-7+5=8，堆顶为5。因为该门课程的持续时间比堆顶短，且关闭时间已排序，所以大于堆顶的关闭时间，所以把堆顶课程换成该课程，该课程肯定能过完成。且新的now=8比先前的now=10要小，使得可以完成第四门课程。
4. 选修第四门课，now=8+8=16<17，优先队列为8。

# LeetCode Gas Station

134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

• If there exists a solution, it is guaranteed to be unique.
• Both input arrays are non-empty and have the same length.
• Each element in the input arrays is a non-negative integer.

Example 1:

Input:
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.


Example 2:

Input:
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.


1. 对于某个点i，如果gas[i]-cost[i]>=0，则车能从i走到i+1。
2. 如果从A出发，无法到达B（但能到达B-1），则所有在A、B之间的起点都无法到达B。反证法，想象一下，如果A,B之间有一起点C能到达B，则说明C到B之间总的gas大于中的cost，又因为C在A,B之间，A能到达C，说明A到C之间中的gas大于cost。那么，既然A能到C，C能到B，则A能到B，和前提假设矛盾，所以原命题成立。
3. 如果圆环上中的gas大于总的cost，则一定有一个解。
4. 假设解的起点为i，则从i肯定能到达环上的任意一点。

1. 从0开始走，如果能到达i，但无法到达i+1，则所有0~i的点都不是起点，因为根据讨论2，0~i的点都无法到达i+1，而根据讨论4，0~i的点不可能是解。
2. 所以尝试起点为i+1，继续往前走。
3. 最后，如果满足3，因为其他所有点都不可能是正确答案，且根据题目，解是唯一的，所以上述过程找到的起点就是正确解。

class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
{
int gasSum = 0, costSum = 0, tank = 0, start = 0;
for (int i = 0; i < gas.size(); ++i) {
gasSum += gas[i];
costSum += cost[i];
tank += (gas[i] – cost[i]);
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
if (gasSum < costSum)
return -1;
else
return start;
}
};

# LeetCode Longest Uncommon Subsequence II

LeetCode Longest Uncommon Subsequence II Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings. A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string. The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1. Example 1:

Input: "aba", "cdc", "eae"
Output: 3

Note:
1. All the given strings’ lengths will not exceed 10.
2. The length of the given list will be in the range of [2, 50].