# 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 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 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 Exclusive Time of Functions

LeetCode Exclusive Time of Functions Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions. Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function. A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0. Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id. Example 1:

Input:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:
1. Input logs will be sorted by timestamp, NOT log id.
2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
3. Two functions won’t start or end at the same time.
4. Functions could be called recursively, and will always end.
5. 1 <= n <= 100

# LeetCode Smallest Range

LeetCode Smallest Range You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists. We define the range [a,b] is smaller than range [c language=",d"][/c] if b-a < d-c or a < c if b-a == d-c. Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:
1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.
4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you’ll see this point.

1. i,j,k分别指向三个数组的开头，即i=j=k=0，相当于在[4,0,5]中找最大值和最小值，构成区间[0,5]，长度为5。
2. 最小值为j所在数组，所以++j，在新的数组[4,9,5]中找最大值和最小值，构成区间[4,9]，长度为5。
3. 最小值为i所在数组，所以++i，在新的数组[10,9,5]中找最大值和最小值，构成区间[5,10]，长度为5。
4. ++k，新数组[10,9,18]，区间[9,18]，长度为9。
5. ++j，新数组[10,12,18]，区间[10,18]，长度为8。
6. ++i，新数组[15,12,18]，区间[12,18]，长度为6。
7. ++j，新数组[15,20,18]，区间[15,20]，长度为5。
8. ++i，新数组[24,20,18]，区间[18,24]，长度为6。
9. ++k，新数组[24,20,22]，区间[20,24]，长度为4。
10. ++j，第二个数组遍历完毕，结束，遍历过程中，得到的长度最短的区间是[20,24]。

# 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 Basic Calculator II

LeetCode Basic Calculator II Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero. You may assume that the given expression is always valid. Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

# LeetCode Basic Calculator

224. Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2


Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

• 如果是操作数，直接压入numbers
• 如果是操作符op：
1. 如果op为左括号“（”，则直接把op压入opers
2. 如果op为右括号“）”，则把opers的运算符不断弹栈并压入numbers，直到栈顶为左括号“（”，此时将这一对括号丢弃
3. 如果opers为空，或者opers栈顶为左括号“（”，则直接把op压入opers
4. 此时，栈顶肯定不可能是括号了，如果op的优先级高于opers栈顶的优先级，则直接把op压入opers
5. 否则，把opers栈顶的运算符不断弹栈并压入numbers，直到栈顶为左括号，或者op的优先级高于opers栈顶的优先级。把op压入opers

// 优先级
unordered_map<string, int> priority = { { "+", 1 }, { "-", 1 }, { "*", 2 }, { "/", 2 } };
class Solution {
private:
void push(stack<string>& numbers, stack<string>& opers, const string& numOrop)
{
if (isdigit(numOrop[0])) {
numbers.push(numOrop);
}
else {
if (numOrop == ")") {
while (opers.top() != "(") {
numbers.push(opers.top());
opers.pop();
}
opers.pop();
}
else if (numOrop == "(") {
opers.push(numOrop);
}
else if (opers.empty() || opers.top() == "(") {
opers.push(numOrop);
}
else if (priority[numOrop] > priority[opers.top()]) {
opers.push(numOrop);
}
else {
while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) {
numbers.push(opers.top());
opers.pop();
}
opers.push(numOrop);
}
}
}
// 中缀转后缀表达式
list<string> in2post(const string& s)
{
stack<string> numbers, opers;
int start = 0, end = 1, n = s.size();
while (start < n) {
while (start < n && s[start] == ‘ ‘)
++start;
if (start >= n)
break;
if (isdigit(s[start])) {
end = start + 1;
while (end < n && isdigit(s[end]))
++end;
string num = s.substr(start, end – start);
push(numbers, opers, num);
start = end;
}
else {
string op = string(1, s[start]);
push(numbers, opers, op);
++start;
}
}
while (!opers.empty()) {
numbers.push(opers.top());
opers.pop();
}
list<string> ans;
while (!numbers.empty()) {
ans.push_front(numbers.top());
numbers.pop();
}
return ans;
}
// 求值后缀表达式的值
int eval(list<string>& post)
{
int ans = 0;
stack<int> numbers;
for (const auto& s : post) {
if (priority.find(s) != priority.end()) {
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
if (s == "+")
numbers.push(num1 + num2);
else if (s == "-")
numbers.push(num1 – num2);
else if (s == "*")
numbers.push(num1 * num2);
else
numbers.push(num1 / num2);
}
else
numbers.push(stoi(s));
}
return numbers.top();
}
public:
int calculate(string s)
{
list<string> ans = in2post(s);
return eval(ans);
}
};

unordered_map<string, int> priority = { {"+",1},{"-",1},{"*",2},{"/",2} };

class Solution {
private:
bool IsDigit(char c) {
return c >= '0'&&c <= '9';
}

vector<string> ParseString(const string &s) {
vector<string> vec;
int n = s.size();
int i = 0, j = 0;
while (i < n) {
while (i < n&&s[i] == ' ')++i;
if (i >= n)break;

if (!IsDigit(s[i])) {
vec.push_back(string(1, s[i]));
++i;
}
else {
j = i + 1;
while (j < n&&IsDigit(s[j]))++j;
vec.push_back(s.substr(i, j - i));
i = j;
}
}
return vec;
}

list<string> In2Post(const vector<string> &vec) {
stack<string> numbers, opers;
for (int i = 0; i < vec.size(); ++i) {
if (IsDigit(vec[i][0])) {
numbers.push(vec[i]);
}
else {
if (vec[i] == ")") { // 右括号
while (opers.top() != "(") {
numbers.push(opers.top());
opers.pop();
}
opers.pop();
}
else if (vec[i] == "(") { // 左括号
opers.push(vec[i]);
}
else { // 操作符
while (!opers.empty() && opers.top() != "("&&priority[vec[i]] <= priority[opers.top()]) {
numbers.push(opers.top());
opers.pop();
}
opers.push(vec[i]);
}
}
}

while (!opers.empty()) {
numbers.push(opers.top());
opers.pop();
}
list<string> lst;
while (!numbers.empty()) {
lst.push_front(numbers.top());
numbers.pop();
}
return lst;
}

int Evaluate(const list<string> &lst) {
stack<string> stk;
for (list<string>::const_iterator it = lst.begin(); it != lst.end(); ++it) {
if (IsDigit((*it)[0])) {
stk.push(*it);
}
else {
int b = atoi(stk.top().c_str());
stk.pop();
int a= atoi(stk.top().c_str());
stk.pop();
if (*it == "+") {
stk.push(to_string(a + b));
}
else if (*it == "-") {
stk.push(to_string(a - b));
}
}
}
return atoi(stk.top().c_str());
}

public:
int calculate(string s) {

vector<string> vec = ParseString(s);
list<string> lst = In2Post(vec);
return Evaluate(lst);
}
};

# LeetCode Mini Parser

LeetCode Mini Parser Given a nested list of integers represented as a string, implement a parser to deserialize it. Each element is either an integer, or a list — whose elements may also be integers or other lists. Note: You may assume that the string is well-formed:

• String is non-empty.
• String does not contain white spaces.
• String contains only digits 0-9, [, - ,, ].
Example 1:
Given s = "324",
You should return a NestedInteger object which contains a single integer 324.

Example 2:
Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
i.  An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789.

# LeetCode Find K Pairs with Smallest Sums

LeetCode Find K Pairs with Smallest Sums You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k. Define a pair (u,v) which consists of one element from the first array and one element from the second array. Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums. Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:
Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
Return: [1,1],[1,1]
The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:
Given nums1 = [1,2], nums2 = [3],  k = 3
Return: [1,3],[2,3]
All possible pairs are returned from the sequence:
[1,3],[2,3]