# LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.
Example 1:

        1
/ \
2   3
/   / \
4   2   4
/
4


The following are two duplicate subtrees:

      2
/
4


and

    4


Therefore, you need to return above trees' root in the form of a list.

  1
/
2


 2
\
1

class Solution {
private:
string DFS(TreeNode* root, unordered_map<string, vector<TreeNode*>>& inorders) {
if (root == NULL)return "";
string left = DFS(root->left, inorders);
string right = DFS(root->right, inorders);
string cur = "(" + left + "," + to_string(root->val) + "," + right + ")";
inorders[cur].push_back(root);
return cur;
}
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_map<string, vector<TreeNode*>> inorders;
DFS(root, inorders);
vector<TreeNode*> ans;
for (auto &it : inorders) {
if (it.second.size() > 1)
ans.push_back(it.second[0]);
}
return ans;
}
};


# LeetCode Replace Words

LeetCode Replace Words

In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the rootforming it. If a successor has many roots can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"


Note:

1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

const int kMaxN = 26;
class Solution {
private:
struct Node {
bool is_word_;
vector<Node*> children_;
Node() :is_word_(false) {
for (int i = 0; i < kMaxN; ++i)
children_.push_back(NULL);
}
};
Node *root_;
void InsertWord(const string& word) {
Node *cur = root_;
for (const auto& c : word) {
int idx = c - 'a';
if (cur->children_[idx] == NULL)cur->children_[idx] = new Node();
cur = cur->children_[idx];
}
cur->is_word_ = true;
}
void ConstructTree(const vector<string>& dict) {
root_ = new Node();
for (const auto& w : dict) {
InsertWord(w);
}
}
string SearchTree(const string& word) {
Node *cur = root_;
string ans = "";
for (const auto& c : word) {
int idx = c - 'a';
if (cur->children_[idx] == NULL)return "";
cur = cur->children_[idx];
ans.push_back(c);
if (cur->is_word_)return ans;
}
return "";
}
public:
string replaceWords(vector<string>& dict, string sentence) {
ConstructTree(dict);
string ans = "";
int i = 0, n = sentence.size();
for (int j = 0; j <= n; ++j) {
if (j == n || sentence[j] == ' ') {
string successor = sentence.substr(i, j - i);
string root = SearchTree(successor);
if (root == "")
ans += successor + " ";
else
ans += root + " ";
i = j + 1;
}
}
return ans.substr(0, ans.size() - 1);
}
};


# LeetCode Palindromic Substrings

LeetCode Palindromic Substrings
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".


Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".


Note:

1. The input string length won't exceed 1000.

class Solution {
public:
int countSubstrings(string s) {
int ans = 0, n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
++ans;
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
if (j >= n)break;
if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
dp[i][j] = 1;
++ans;
}
}
}
return ans;
}
};


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

bool cmp(const vector<int>& p1, const vector<int>& p2) {
return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
}
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), cmp);
int n = pairs.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = 1;
int ans = 1;
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = 1;
int j = i - 1;
while (j >= 0 && pairs[i][0] <= pairs[j][1]) {
--j;
}
if (j >= 0) {
dp[i][1] = max(dp[i][1], dp[j][1] + 1);
}
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); });
int n = pairs.size(), ans = 1;
vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; });
int ans = 0;
for (int i = 0, j = 0; j < pairs.size(); ++j) {
if (j == 0 || pairs[j][0] > pairs[i][1]) {
++ans;
i = j;
}
}
return ans;
}
};


# LeetCode Set Mismatch

LeetCode Set Mismatch
The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]


Note:

1. The given array size will in the range [2, 10000].
2. The given array's numbers won't have any order.

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
unordered_set<int> hash;
int sum = 0, n = nums.size();
for (const auto& num : nums) {
if (hash.find(num) != hash.end())ans[0] = num;
hash.insert(num);
sum += num;
}
ans[1] = ans[0] - sum + n*(n + 1) / 2;
return ans;
}
};


class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
for (int i = 0; i < nums.size(); ++i) {
int idx = nums[i] < 0 ? -nums[i] : nums[i];
if (nums[idx - 1] < 0) {
ans[0] = idx;
} else {
nums[idx - 1] = -nums[idx - 1];
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0) {
ans[1] = i + 1;
break;
}
}
return ans;
}
};


# LeetCode Design Search Autocomplete System

LeetCode Design Search Autocomplete System
Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
2. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
3. If less than 3 hot sentences exist, then just return as many as you can.
4. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Your job is to implement the following functions:
The constructor function:
AutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical dataSentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.
Now, the user wants to input a new sentence. The following function will provide the next character the user types:
List<String> input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.

Example:
Operation: AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
"i love you" : 5 times
"island" : 3 times
"ironman" : 2 times
"i love leetcode" : 2 times
Now, the user begins another search:
Operation: input('i')
Output: ["i love you", "island","i love leetcode"]
Explanation:
There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
Operation: input(' ')
Output: ["i love you","i love leetcode"]
Explanation:
There are only two sentences that have prefix "i ".
Operation: input('a')
Output: []
Explanation:
There are no sentences that have prefix "i a".
Operation: input('#')
Output: []
Explanation:
The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.

Note:

1. The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
2. The number of complete sentences that to be searched won't exceed 100. The length of each sentence including those in the historical data won't exceed 100.
3. Please use double-quote instead of single-quote when you write test cases even for a character input.
4. Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see herefor more details.

Trie树的应用题。Trie树的节点属性包含is_sentence_以该字符结尾是否是一个句子，cnt_该句子的频率。首先把历史数据插入到Trie树中，记录好相应的is_sentence_和cnt_。

const int N = 26;
class AutocompleteSystem {
private:
struct Node {
bool is_sentence_;
int cnt_;
vector<Node*> children_;
Node() :is_sentence_(false), cnt_(0){
for (int i = 0; i < N + 1; ++i)children_.push_back(NULL);
}
};
Node *root;
string cur_sentence_;
struct Candidate {
int cnt_;
string sentence_;
Candidate(int &cnt, string &sentence) :cnt_(cnt), sentence_(sentence) {};
bool operator<(const Candidate& cand) const {
return (cnt_ < cand.cnt_) || (cnt_ == cand.cnt_&&sentence_ > cand.sentence_); // caution
}
};
void AddSentence(const string& sentence, const int& time) {
Node *cur = root;
for (const auto& c : sentence) {
int idx = c - 'a';
if (c == ' ')idx = N;
if (cur->children_[idx] == NULL)cur->children_[idx] = new Node();
cur = cur->children_[idx];
}
cur->is_sentence_ = true;
cur->cnt_ += time; // caution
}
void FindSentences(Node *root, string &sentence, priority_queue<Candidate>& candidates) {
if (root != NULL&&root->is_sentence_)candidates.push(Candidate(root->cnt_, sentence));
if (root == NULL)return;
for (int i = 0; i < N + 1; ++i) {
if (root->children_[i] != NULL) {
if (i == N)
sentence.push_back(' ');
else
sentence.push_back('a' + i);
FindSentences(root->children_[i], sentence, candidates);
sentence.pop_back();
}
}
}
void StartWith(priority_queue<Candidate>& candidates) {
Node *cur = root;
for (const auto& c : cur_sentence_) {
int idx = c - 'a';
if (c == ' ')idx = N;
if (cur->children_[idx] == NULL)return;
cur = cur->children_[idx];
}
string sentence = cur_sentence_;
FindSentences(cur, sentence, candidates);
}
public:
AutocompleteSystem(vector<string> sentences, vector<int> times) {
root = new Node(); // caution
cur_sentence_ = ""; // caution
for (int i = 0; i < sentences.size(); ++i)AddSentence(sentences[i], times[i]);
}
vector<string> input(char c) {
if (c == '#') {
cur_sentence_ = ""; // caution
return{};
}
else {
cur_sentence_.push_back(c);
priority_queue<Candidate> candidates;
StartWith(candidates);
if (candidates.empty())return{};
vector<string> ans;
while (!candidates.empty()) {
ans.push_back(candidates.top().sentence_);
candidates.pop();
if (ans.size() == 3)break;
}
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

class Solution {
private:
struct Node {
int id_;
bool start_;
int timestamp_;
int exclude_time_;
};
void ParseLog(const string& log, Node& node) {
size_t colon_pos = log.find(':');
node.id_ = stoi(log.substr(0, colon_pos));
if (log[colon_pos + 1] == 's')
node.start_ = true;
else
node.start_ = false;
colon_pos = log.find(':', colon_pos + 1);
node.timestamp_ = stoi(log.substr(colon_pos + 1));
node.exclude_time_ = 0;
}
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> ans(n);
stack<Node> stk;
for (const auto& log : logs) {
Node node;
ParseLog(log, node);
if (node.start_) {
stk.push(node);
} else {
Node start_node = stk.top();
stk.pop();
int cur_time = node.timestamp_ - start_node.timestamp_ + 1 - start_node.exclude_time_; // caution
ans[node.id_] += cur_time; // caution
if (!stk.empty())stk.top().exclude_time_ += cur_time + start_node.exclude_time_; // caution
}
}
return ans;
}
};


# LeetCode Maximum Average Subarray I

LeetCode Maximum Average Subarray I
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75


Note:

1. 1 <= k <= n <= 30,000.
2. Elements of the given array will be in the range [-10,000, 10,000].

class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size();
if (n < k)return 0;
int i = 0, sum = 0, ans = INT_MIN;
for (int j = 0; j < k; ++j)sum += nums[j];
for (int j = k; j < n; ++j) {
ans = max(ans, sum);
sum += nums[j] - nums[i];
++i;
}
ans = max(ans, sum);
return ans / double(k);
}
};


# LeetCode Shopping Offers

LeetCode Shopping Offers
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and$5 respectively.
In special offer 1, you can pay $5 for 3A and 0B In special offer 2, you can pay$10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and$4 for 2A.


Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and$3 for B, $4 for C. You may pay$4 for 1A and 1B, and $9 for 2A ,2B and 1C. You need to buy 1A ,2B and 1C, so you may pay$4 for 1A and 1B (special offer #1), and $3 for 1B,$4 for 1C.
You cannot add more items, though only \$9 for 2A ,2B and 1C.


Note:

1. There are at most 6 kinds of items, 100 special offers.
2. For each item, you need to buy at most 6 of them.
3. You are not allowed to buy more items than you want, even if that would lower the overall price.

class Solution {
private:
int dot(vector<int>& price, vector<int>& needs) {
int ans = 0;
for (int i = 0; i < needs.size(); ++i) {
ans += price[i] * needs[i];
}
return ans;
}
int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) {
if (idx == special.size())return dot(price, needs); // 原价购买
int i = 0, n = special[idx].size();
vector<int> small_needs = needs;
for (i = 0; i < n - 1; ++i) {
if (special[idx][i] > needs[i])break;
small_needs[i] -= special[idx][i];
}
if (i == n - 1)return min(shopping(price, special, small_needs, idx) + special[idx][n - 1], shopping(price, special, needs, idx + 1));
else return shopping(price, special, needs, idx + 1);
}
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
return shopping(price, special, needs, 0);
}
};


# LeetCode Decode Ways II

LeetCode Decode Ways II
A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1
'B' -> 2
...
'Z' -> 26


Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:

Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".


Example 2:

Input: "1*"
Output: 9 + 9 = 18


Note:

1. The length of the input string will fit in range [1, 105].
2. The input string will only contain the character '*' and digits '0' - '9'.

const int MOD = 1000000007;
typedef long long ll;
class Solution {
public:
int numDecodings(string s) {
if (s == "" || s[0] == '0')return 0;
s = "^" + s;
int n = s.size();
vector<ll> dp(n, 0);
dp[0] = 1;
if (s[1] == '*')dp[1] = 9;
else dp[1] = 1;
for (int i = 2; i < n; i++)
{
if (s[i] >= '1' && s[i] <= '9')
dp[i] += dp[i - 1] % MOD; // 独自解析
if ((s[i - 1] == '1' && s[i] >= '0' && s[i] <= '9') || (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6'))
dp[i] += dp[i - 2] % MOD;
if (s[i - 1] == '*'&&s[i] >= '0'&&s[i] <= '9') {
if (s[i] >= '0'&&s[i] <= '6')dp[i] += dp[i - 2] * 2 % MOD;
if (s[i] > '6')dp[i] += dp[i - 2] % MOD;
}
if (s[i] == '*') {
dp[i] += dp[i - 1] * 9 % MOD; // 独自解析
if (s[i - 1] != '*') {
if (s[i - 1] == '1')dp[i] += dp[i - 2] * 9 % MOD;
else if (s[i - 1] == '2')dp[i] += dp[i - 2] * 6 % MOD;
}
else {
dp[i] += dp[i - 2] * 15 % MOD;
}
}
dp[i] %= MOD;
}
return dp[n - 1];
}
};


class Solution {
public:
int numDecodings(string s) {
if (s == "" || s[0] == '0')return 0;
s = "^" + s;
int n = s.size();
vector<ll> dp(n, 0);
dp[0] = 1;
if (s[1] == '*')dp[1] = 9;
else dp[1] = 1;
for (int i = 2; i < n; i++) {
char cur = s[i], pre = s[i - 1];
ll &curCnt = dp[i], preCnt = dp[i - 1], prePreCnt = dp[i - 2];
if (cur == '0') {
if (pre == '1'|| pre == '2')curCnt += prePreCnt % MOD;
else if (pre == '*')curCnt += prePreCnt * 2 % MOD;
else return 0;
}
else if (cur == '*') {
curCnt += preCnt * 9 % MOD;
if (pre == '1')curCnt += prePreCnt * 9 % MOD;
else if (pre == '2')curCnt += prePreCnt * 6 % MOD;
else if (pre == '*')curCnt += prePreCnt * 15 % MOD;
}
else { // ['1','9']
curCnt += preCnt % MOD;
if(pre=='1')curCnt += prePreCnt % MOD;
else if (pre == '2' && cur <= '6')curCnt += prePreCnt % MOD;
else if (pre == '*') {
if (cur <= '6')curCnt += prePreCnt * 2 % MOD;
else curCnt += prePreCnt % MOD;
}
}
curCnt %= MOD;
}
return dp[n - 1];
}
};