# LeetCode Reconstruct Itinerary

LeetCode Reconstruct Itinerary
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

class Solution {
private:
bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) {
if (lines == 0) return true;
int n = hash2.size();
for (int i = 0; i < n; ++i) { // 字典序从小到大深搜
if (graph[start][i] > 0) {
--graph[start][i];
ans += hash2[i];
if (dfs(ans, hash2, graph, i, lines - 1))return true;
++graph[start][i];
ans = ans.substr(0, ans.size() - 3);
}
}
return false;
}
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
map<string, int> hash1;
vector<string> hash2;
int cnt = 0, n = tickets.size();
for (int i = 0; i < tickets.size(); ++i) { // 记录
hash1[tickets[i].first] = 0;
hash1[tickets[i].second] = 0;
}
for (auto it = hash1.begin(); it != hash1.end(); ++it) {
it->second = cnt++; // 字典序从小到大编号
hash2.push_back(it->first);
}
vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图
for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]];
int start = hash1["JFK"];
string ans = "JFK";
dfs(ans, hash2, graph, start, n); // 深搜
vector<string> Itinerary;
for (int i = 0; i <= ans.size() - 3; i += 3)Itinerary.push_back(ans.substr(i, 3));
return Itinerary;
}
};


# LeetCode 132 Pattern

LeetCode 132 Pattern
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:

Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.


Example 2:

Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].


Example 3:

Input: [-1, 3, 2, 0]
Output: True
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

class Solution {
public:
bool find132pattern(vector<int>& nums) {
int i = 0, j = 0, k = 0, n = nums.size();
while (i < n) {
while (i < n - 1 && nums[i] >= nums[i + 1])++i;
j = i + 1;
while (j < n - 1 && nums[j] <= nums[j + 1])++j;
k = j + 1;
while (k < n) {
if (nums[k] > nums[i] && nums[k] < nums[j])return true;
++k;
}
++i;
}
return false;
}
};


class Solution {
public:
bool find132pattern(vector<int>& nums) {
stack<int> stk;
int third = INT_MIN;
for (int i = nums.size() - 1; i >= 0; --i) {
if (nums[i] < third)return true;
else {
while (!stk.empty() && nums[i] > stk.top()) {
third = stk.top();
stk.pop();
}
stk.push(nums[i]);
}
}
return false;
}
};


# LeetCode H-Index

LeetCode H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
Hint:

1. An easy approach is to sort the array first.
2. What are the possible values of h-index?
3. A faster approach is to use extra space.

class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end(), std::greater<int>());
int h = 1;
while (h <= citations.size()) {
if (citations[h - 1] < h)return h - 1;
++h;
}
return h - 1;
}
};


class Solution {
public:
int hIndex(vector<int>& citations) {
int maxC = -1, n = citations.size();
if (n == 0)return 0;
for (int i = 0; i < n; ++i)maxC = max(maxC, citations[i]);
vector<int> hash(maxC + 1, 0);
for (int i = 0; i < n; ++i)++hash[citations[i]];
int c = maxC, h = hash[maxC];
while (c >= h) {
--c;
h += hash;
}
return max(h - hash, c);
}
};


A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
How would you handle overflow for very large input integers?

typedef long long LL;
class Solution {
private:
bool dfs(const string& num, int start, LL last1, LL last2, int cnt) {
int n = num.size();
if (start == n&&cnt >= 3)return true;
//if (start < n&&num[start] == '0')return false; // "101" is true
int m = num.size() - start; // left length
bool ans = false;
for (int i = 1; i <= m; ++i) {
if (i != 1 && num[start] == '0')continue; // leading zero
LL sum = atoll(num.substr(start, i).c_str());
if (cnt >= 2) {
if (last1 + last2 > sum)continue;
else if (last1 + last2 < sum)return false;
else ans = dfs(num, start + i, last2, sum, cnt + 1);
}
else if (cnt == 0)ans = dfs(num, start + i, sum, last2, cnt + 1);
else if(cnt==1)ans= dfs(num, start + i, last1, sum, cnt + 1);
if (ans)return true;
}
return false;
}
public:
return dfs(num, 0, 0, 0, 0);
}
};


# LeetCode Count Complete Tree Nodes

LeetCode Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

class Solution {
public:
int countNodes(TreeNode* root) {
if (!root)return 0;
int lh = 0, rh = 0;
TreeNode *l = root, *r = root;
while (l) {
++lh;
l = l->left;
}
while (r) {
++rh;
r = r->right;
}
if (lh == rh)return (1 << lh) - 1;
return countNodes(root->left) + countNodes(root->right) + 1;
}
};


class Solution {
private:
int height(TreeNode* root, int lh, int rh) {
if (lh == -1) {
lh = 0;
TreeNode *l = root;
while (l) {
++lh;
l = l->left;
}
}
if (rh == -1) {
rh = 0;
TreeNode *r = root;
while (r) {
++rh;
r = r->right;
}
}
if (lh == rh)return (1 << lh) - 1;
return height(root->left, lh - 1, -1) + height(root->right, -1, rh - 1) + 1;
}
public:
int countNodes(TreeNode* root) {
return height(root, -1, -1);
}
};


# LeetCode Water and Jug Problem

LeetCode Water and Jug Problem
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True


Example 2:

Input: x = 2, y = 6, z = 5
Output: False

1. 盛满5L水罐；
2. 将5L水罐中的水导入3L水罐，此时5L水罐中还剩2L水；
3. 将3L水罐中的水清空；
4. 将5L水罐中的2L水倒入3L水罐中；
5. 盛满5L水罐；
6. 将5L水罐中的水倒入3L水罐中，此时5L水罐中剩余4L水，3L水罐中是满的；
7. 将3L水罐中的水清空，此时只剩5L水罐中的4L水。

class Solution {
private:
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x%y);
}
public:
bool canMeasureWater(int x, int y, int z) {
return z == 0 || (x + y >= z&&z%gcd(x, y) == 0);
}
};


# LeetCode Wiggle Subsequence

LeetCode Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2


Can you do it in O(n) time?

class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int ans = 1, i = 0, j = 1;
bool up = false;
while (j < n && nums[j] == nums[i])++j;
if (nums[j] > nums[i])up = true;
else up = false;
while (j < n) {
if (nums[j] > nums[i] && up) {
++ans;
up = false;
while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
}
else if (nums[j] < nums[i] && !up) {
++ans;
up = true;
while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
}
i = j++;
}
return ans;
}
};


class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])down[i] = max(down[i], up[j] + 1);
}
}
return 1 + max(up[n - 1], down[n - 1]);
}
};


class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
up[0] = down[0] = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) {
up[i] = down[i - 1] + 1;
down[i] = down[i - 1];
}
else if (nums[i] < nums[i - 1]) {
down[i] = up[i - 1] + 1;
up[i] = up[i - 1];
}
else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return max(up[n - 1], down[n - 1]);
}
};


class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int up = 1, down = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
}
else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return max(up, down);
}
};


# LeetCode Perfect Number

LeetCode Perfect Number
We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.
Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.
Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14


Note: The input number n will not exceed 100,000,000. (1e8)

class Solution {
public:
bool checkPerfectNumber(int num) {
if (num <= 1)return false;
int ans = 0, n = sqrt(num);
for (int i = 1; i <= n; ++i) {
if (num%i == 0) {
ans += i;
if (i != 1 && num / i != i)ans += num / i;
}
}
return ans == num;
}
};


# LeetCode Target Sum

LeetCode Target Sum
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.


Note:

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

class Solution {
private:
void dfs(vector<int>& nums, int step, int S, int& ans) {
if (step == nums.size() && S == 0) {
++ans;
return;
}
if (step == nums.size())return;
dfs(nums, step + 1, S - nums[step], ans);
dfs(nums, step + 1, S + nums[step], ans);
}
public:
int findTargetSumWays(vector<int>& nums, int S) {
int ans = 0;
dfs(nums, 0, S, ans);
return ans;
}
};


dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]

DP的代码如下：

class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; ++i)sum += nums[i];
if (S<-sum || S>sum)return 0;
//if (S == -sum || S == sum)return 1; // nums={1,0},S=1; 1=1+0=1-0
vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0));
dp[0][sum] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2 * sum + 1; ++j) {
//考虑第i个数字是+还是-
//i从1开始，所以第i个数字的下标是i-1
if (j >= nums[i - 1])dp[i][j] += dp[i - 1][j - nums[i - 1]];
if (j + nums[i - 1] < 2 * sum + 1)dp[i][j] += dp[i - 1][j + nums[i - 1]];
}
}
return dp[n][S + sum];
}
};


DP的问题一般都可以优化空间，比如上述代码可以用两个数组互相滚动赋值来代替n+1个数组。

class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; ++i)sum += nums[i];
if (S<-sum || S>sum)return 0;
vector<vector<int>> dp(2, vector<int>(2 * sum + 1, 0));
int i = 0, pre = (i & 1) ? 1 : 0, cur = (i & 1) ? 0 : 1;
dp[pre][sum] = 1; // 取0个数字，加和为0的方案有1种。把和0偏移到sum位置
while (i < n) {
pre = (i & 1) ? 1 : 0;
cur = (i & 1) ? 0 : 1;
for (int j = 0; j < 2 * sum + 1; ++j) {
if (dp[pre][j] != 0) {
if (j + nums[i] < 2 * sum + 1)dp[cur][j + nums[i]] += dp[pre][j]; // 在j的基础上加nums[i]
if (j - nums[i] >= 0)dp[cur][j - nums[i]] += dp[pre][j]; // 在j的基础上减nums[i]
}
}
fill(dp[pre].begin(), dp[pre].end(), 0); // 清空pre数组，因为下一轮pre要用作cur数组
++i;
}
return dp[cur][S + sum];
}
};


# LeetCode Maximum XOR of Two Numbers in an Array

LeetCode Maximum XOR of Two Numbers in an Array
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:

Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

• 0^0=0 | 0=0^0
• 0^1=1 | 0=1^1
• 1^0=1 | 1=0^1
• 1^1=0 | 1=1^0

class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int ans = 0, mask = 0;
for (int i = 31; i >= 0; --i) {
unordered_set<int> hash;
for (const auto& num : nums) {
}
int tmpmax = ans | (1 << i);
for (const auto& prefix : hash) {
if (hash.find(prefix ^ tmpmax) != hash.end()) {
ans = tmpmax;
break;
}
}
}
return ans;
}
};