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.

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].

LeetCode H-Index

274. 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.”

Example:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] 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, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

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[c];
}
return max(h – hash[c], c);
}
};

LeetCode Additive Number Additive number is a string whose digits can form additive sequence. 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. Follow up: How would you handle overflow for very large input integers?

LeetCode Count Complete Tree Nodes

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Note:

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.

Example:

Input:      1    / \   2   3  / \  / 4  5 6 Output: 6

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

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
Follow up: Can you do it in O(n) time?

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)

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.

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