# LeetCode Wiggle Sort II

LeetCode Wiggle Sort II Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2]. Note: You may assume all input has valid answer. Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

# 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 Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree)

Implement a trie with insertsearch, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true


Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

const int MAXN = 26;
class Trie {
private:
struct Node {
char c;
bool isWord;
Node(char c_, bool isWord_)
: c(c_)
, isWord(isWord_)
{
for (int i = 0; i < MAXN; ++i)
children.push_back(NULL);
};
vector<Node*> children;
};
Node* root;
public: /** Initialize your data structure here. */
Trie() { root = new Node(‘ ‘, true); } /** Inserts a word into the trie. */
void insert(string word)
{
Node* cur = root;
for (int i = 0; i < word.size(); ++i) {
int idx = word[i] – ‘a’;
if (cur->children[idx] == NULL)
cur->children[idx] = new Node(word[i], false);
cur = cur->children[idx];
}
cur->isWord = true;
} /** Returns if the word is in the trie. */
bool search(string word)
{
Node* cur = root;
for (int i = 0; i < word.size(); ++i) {
int idx = word[i] – ‘a’;
if (cur->children[idx] == NULL)
return false;
cur = cur->children[idx];
}
return cur->isWord;
} /** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix)
{
Node* cur = root;
for (int i = 0; i < prefix.size(); ++i) {
int idx = prefix[i] – ‘a’;
if (cur->children[idx] == NULL)
return false;
cur = cur->children[idx];
}
return true;
}
};

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

210. Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

LeetCode Course Schedule的基础上，要求输出一种拓扑排序结果。

class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int> >& prerequisites)
{
vector<unordered_set<int> > pre(numCourses), next(numCourses);
for (const auto& p : prerequisites) {
pre[p.first].insert(p.second);
next[p.second].insert(p.first);
}
vector<int> ans;
queue<int> q;
for (int i = 0; i < numCourses; ++i) {
if (pre[i].empty())
q.push(i);
}
int edges = prerequisites.size();
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; ++i) {
int cur = q.front();
ans.push_back(cur);
q.pop();
for (const auto& nxt : next[cur]) {
pre[nxt].erase(cur);
–edges;
if (pre[nxt].empty())
q.push(nxt);
}
}
}
if (edges > 0)
return {};
else
return ans;
}
};

class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
vector<int> indegree(numCourses, 0);
for (int i = 0; i < prerequisites.size(); ++i) {
int a = prerequisites[i][0], b = prerequisites[i][1];
graph[b][a] = 1;
++indegree[a];
}
vector<int> ans;
while (true) {
int validid = -1;
for (int i = 0; i < numCourses; ++i) {
if (indegree[i] == 0) {
validid = i;
--indegree[i];
break;
}
}
if (validid == -1)break;
ans.push_back(validid);
for (int i = 0; i < numCourses; ++i) {
if (graph[validid][i] == 1) {
graph[validid][i] = 0;
--indegree[i];
}
}
}
if (ans.size() != numCourses)return { };
return ans;
}
};

# LeetCode K-diff Pairs in an Array

LeetCode K-diff Pairs in an Array Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k. Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:
1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won’t exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].

# LeetCode Next Greater Element III

LeetCode Next Greater Element III Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1. Example 1:

Input: 12
Output: 21

Example 2:
Input: 21
Output: -1

# LeetCode Design Excel Sum Formula

LeetCode Design Excel Sum Formula Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions: Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from ‘A’ to ‘Z’. It represents that the width is the number of characters from ‘A’ to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from ‘A’.   void Set(int row, char column, int val): Change the value at C(row, column) to be val.   int Get(int row, char column): Return the value at C(row, column).   int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula. numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, “F7” represents the cell at (7, F). If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.   Example 1:

Excel(3,"C");
// construct a 3*3 2D array with all zero.
//   A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6

Note:
1. You could assume that there won’t be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
2. The test cases are using double-quotes to represent a character.
3. Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

• Get(int row, char column)，获取坐标为(row,column)的cell的值
• Set(int row, char column, int val)，把坐标为(row,column)的值设置为val
• Sum(int row, char column, List of Strings : numbers)，numbers表示一系列求和公式，把公式计算结果填入坐标(row,column)中，并且当公式中的格子更新时，该公式计算出来的值也要更新。

• 对于get，如果坐标不在formula中，说明该格子是实实在在的值，直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
• 对于set，直接把matrix对应坐标设置为value就好，注意的是，因为set之后就变成了实实在在的值，所以要清空formula中该格子的公式（如果有的话）。
• 对于sum，计算字符串公式的值，把结果填入对应的格子，然后在formula中设置该格子的公式。

# LeetCode K Inverse Pairs Array

LeetCode K Inverse Pairs Array Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. We define an inverse pair as following: For ith and jth element in the array, if i < j and a[i] > a[j] then it’s an inverse pair; Otherwise, it’s not. Since the answer may very large, the answer should be modulo 109 + 7. Example 1:

Input: n = 3, k = 0
Output: 1
Explanation:
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.

Example 2:
Input: n = 3, k = 1
Output: 2
Explanation:
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Note:
1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

• 长度为n，且有k个逆序对的基础上，把第n+1个数放到原序列的末尾，则不增加逆序对，+dp[n][k]，xxxx*（xxxx表示原长度为n的序列，*表示新加入的数）
• 长度为n，且有k-1个逆序对的基础上，把第n+1个数插入到原序列倒数第一个空位上，xxx*x，因为插入的*是最大的数，和最后一个x形成一个逆序对，使得新的长度为n+1的序列的逆序对=k-1+1=k，所以+dp[n][k-1]
• 类似的，xx*xx，+dp[n][k-2]
• x*xxx，+dp[n][k-3]
• *xxxx，+dp[n][k-4]

# 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。