leetcode solvers

# String

## LeetCote_string_383_Ransom Note

### 题意

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true


### 实现

class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> count(26, 0);
for (char ch : magazine)
++count[ch - 'a'];
for (char ch : ransomNote)
{
if (count[ch - 'a'] == 0)
return false;
--count[ch - 'a'];
}
return true;
}
};


### 复杂度

• 时间复杂度

$O(N) + O(M)$,N, M分别为magzineransomNote的长度

• 空间复杂度

$O(1)$,只要一个长度为26的数组即可

### Problem Description

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

### Method

#### 直接遍历所有情况

class Solution {
public:
vector<string> ips;
string ip;
for (int a = 1; a < 4; ++a)
for (int b = 1; b < 4; ++b)
for (int c = 1; c < 4; ++c)
for (int d = 1; d < 4; ++d)
{
if (a + b + c + d == s.length())
{
int part1 = stoi(s.substr(0, a));
int part2 = stoi(s.substr(a, b));
int part3 = stoi(s.substr(a+b, c));
int part4 = stoi(s.substr(a+b+c, d));
if (part1 <= 255 && part2 <= 255 && part3 <= 255 && part4 <= 255)
{
ip = to_string(part1) + "." + to_string(part2) + "." + to_string(part3) + "." + to_string(part4);
if (ip.length() == s.length() + 3)
ips.push_back(ip);
}
}
}
return ips;

}
};


#### DFS

class Solution {
public:
vector<string> res;
restoreIP(s, res, 0, "", 0);
return res;
}

private:
void restoreIP(string& s, vector<string>& solution, int idx, string restored, \
int count)
{
if (count > 4) return;
if (count == 4 && idx == s.length()) solution.push_back(restored);

for (int i = 1; i < 4; ++i)
{
if (idx + i > s.length()) break;
string substring = s.substr(idx, i);
if ((substring[0] == '0' && substring.length() > 1) || \
(i == 3 && stoi(substring) > 255))
continue;
restoreIP(s, solution, idx + i, restored + substring + (count == 3 ? "" : "."),\
count + 1);

}
}
};


## 385 Mini Parser

### Problem Description

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.

Subscribe to see which companies asked this question

### Method

class Solution {
public:
NestedInteger deserialize(string s) {
istringstream in(s);
return deserialize(in);
}
private:
NestedInteger deserialize(istringstream &in) {
int num;
if (in >> num)
return NestedInteger(num);
in.clear();
in.get();
NestedInteger list;
while(in.peek() != ']')
{
if (in.peek() == ',')
in.get();
}
in.get();
return list;
}
};


## 3 Longest Substring Without Repeating Characters

### Problem Description

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Subscribe to see which companies asked this question

### Method

start指向最近一个重复字符，如果当前字符上次出现的位置大于start,则将start更新为当前当前字符上次出现的位置，否则当前字符不会造成重复。

class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> alphatable(256, -1);
int start = -1, maxlen = 0;
for (int i = 0; i < s.length(); ++i) {
if (alphatable[s[i]] > start)
start = alphatable[s[i]];
alphatable[s[i]] = i;
maxlen = max(maxlen, i - start);
}
return maxlen;
}
};


## 30. Substring with Concatenation of All Words

### Problem Description

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]

You should return the indices: [0,9].
(order does not matter).

### Method

class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> counts;
for (string word : words)
counts[word]++;
int n = s.length(), num = words.size(), len = words[0].length();
vector<int> indexes;
for (int i = 0; i < n - num * len + 1; ++i)
{
unordered_map<string, int> seen;
int j = 0;
for (; j < num; ++j)
{
string substring = s.substr(i + len * j, len);
if (counts.find(substring) != counts.end())
{
seen[substring]++;
if (seen[substring] > counts[substring])
break;
}
else
break;
}
if (j == num) indexes.push_back(i);
}
return indexes;
}
};


## 151 Reverse Words in a String

### Problem Description

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

### Method

class Solution
{
public:
void reverseWords(string &s)
{
/************** 去除单词间重复空格 ************/
string::iterator new_end = std::unique(s.begin(), s.end(), \
[](char lhs, char rhs){return (lhs == rhs) && (lhs == ' ');});
s.erase(new_end, s.end());

/******************   翻转整个字符串   *************/
reverse(s.begin(), s.end());
// 给字符串首尾添加空格方便判断单词位置
s = " " + s + " ";
int start = 0;
for (int i = 0; i < s.length() - 1; ++i)
{
if (s[i] == ' ' && s[i + 1] != ' ')
start = i + 1;
if (s[i] != ' ' && s[i + 1] == ' ')
{
reverse(s.begin() + start, \
s.begin() + i + 1);
start = i + 1;
}
}
// 去除首位空格
s.erase(0, s.find_first_not_of(" "));
s.erase(s.find_last_not_of(" ") + 1);
}
};


## 5. Longest Palindromic Substring

### Problem Desceiption

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Output: “bab”

Note: “aba” is also a valid answer.
Example:

Input: “cbbd”

Output: “bb”

### Method

class Solution {
public:
string longestPalindrome(string s) {
// 关键是依次以每个字符为回文中心向两边扩展
if (s.empty()) return "";
if (s.size() == 1) return s;
int start = 0, max_len = 1;
int i = 0;
while(i < s.length())
{
// 如果回文中心到字符串尾部的长度小于当前最长回文的一半，则不可能出现更长的回文，结束
if (s.size() - i <= max_len / 2)
break;
int left = i, right = i;
// 跳过重复字符串
while(right < s.length() - 1 && s[right] == s[right + 1])
++right;
// 下一个可能的回文中心必定在重复字符串之外，因为需要保证两边有相同数量的字符
i = right + 1;
while(right < s.length() - 1 && left > 0 && s[right + 1] == s[left - 1])
{
++right;
--left;
}
int new_len = right - left + 1;
if (new_len > max_len)
{
start = left;
max_len = new_len;
}
}
return s.substr(start, max_len);

}
};


## 17. Letter Combinations of a Phone Number

### Problem Description

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

### Method

class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.empty())
return res;
string charmap[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
res.push_back("");
for (int i = 0; i < digits.size(); ++i)
{
vector<string> tmpvec;
string chars = charmap[digits[i] - '0'];
for (int j = 0; j < chars.size(); ++j)
for (string str : res)
tmpvec.push_back(str + chars[j]);
res = tmpvec;
}
return res;
}
};


## 49. Group Anagrams

### Problem Description

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

[
[“ate”, “eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note: All inputs will be in lower-case.

### Method

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, multiset<string>> mp;
for (string str : strs)
{
string tmp = str;
sort(tmp.begin(), tmp.end());
mp[tmp].insert(str);
}
vector<vector<string>> res;
for (auto m : mp)
{
vector<string> anagram(m.second.begin(), m.second.end());
res.push_back(anagram);
}
return res;
}
};


## 91. Decode Ways

### Problem Description

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 >2) or “L” (12).

The number of ways decoding “12” is 2.

### Method

• 如果s[i]为0
• 如果s[i-1] = '2' || s[i-1] = '1'则只有s[i-1]s[i]是合法的解码规则, 即s[:i]的解码总数是l2;
• 其他情况下不管是s[i]还是s[i-1]s[i]都没有合法的解码规则，整个字符串不能解码，返回0
• 如果s[i]不等于0(0-9)
• 如果s[i-1] = '2' && s[i] <= 6 或者s[i-1] = '1', 则s[i]s[i-1]s[i]都符合解码规则，s[:i]的解码总数为l1 + l2;
• 否则只有s[i]符合解码规则而s[i-1]s[i]不符合任何解码规则，s[:i]解码总数为l1;
class Solution {
public:
int numDecodings(string s) {

if (!s.size() || s.front() == '0') return 0;
int l1 = 1, l2 = 1;
for (int i = 1; i < s.size(); ++i)
{
if (s[i] == '0')
{
if (s[i - 1] == '1' || s[i - 1] == '2')
{
int tmp = l1;
l1 = l2;
l2 = tmp;
}
else
return 0;
}
else
{
if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))
{
int tmp = l1;
l1 = l1 + l2;
l2 = tmp;
}
else
l2 = l1;
}
}
return l1;
}
};


int numDecodings(string s) {
if (!s.size() || s.front() == '0') return 0;
// r2: decode ways of s[i-2] , r1: decode ways of s[i-1]
int r1 = 1, r2 = 1;

for (int i = 1; i < s.size(); i++) {
// zero voids ways of the last because zero cannot be used separately
if (s[i] == '0') r1 = 0;

// possible two-digit letter, so new r1 is sum of both while new r2 is the old r1
if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') {
r1 = r2 + r1;
r2 = r1 - r2;
}

// one-digit letter, no new way added
else {
r2 = r1;
}
}

return r1;
}


## 227. Basic Calculator II

### Problem Description

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.

### Method

class Solution {
public:
int calculate(string s) {
s = "+" + s + "]";
istringstream in(s);
stack<int> numStk;
int num;
char op;
while (in.peek() != ']')
{
op = in.get();
if (op == ' ')
continue;
in >> num;
if (op == '+')
numStk.push(num);
if (op == '-')
numStk.push(-num);
if (op == '*')
{
int res = numStk.top() * num;
numStk.pop();
numStk.push(res);
}
if (op == '/')
{
int res = numStk.top() / num;
numStk.pop();
numStk.push(res);
}
}
long long rst= 0;
while (!numStk.empty())
{
rst += numStk.top();
numStk.pop();
}
return rst;
}
};


## 71. Simplify Path

### Problem Description

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = “/home/“, => “/home”
path = “/a/./b/../../c/“, => “/c”
Corner Cases:
Did you consider the case where path = “/../“?
In this case, you should return “/“.
Another corner case is the path might contain multiple slashes ‘/‘ together, such as “/home//foo/“.
In this case, you should ignore redundant slashes and return “/home/foo”.

### Method

c++ 中getline类似于java中的split

string simplifyPath(string path) {
string res, tmp;
vector<string> stk;
stringstream ss(path);
while(getline(ss,tmp,'/')) {
if (tmp == "" or tmp == ".") continue;
if (tmp == ".." and !stk.empty()) stk.pop_back();
else if (tmp != "..") stk.push_back(tmp);
}
for(auto str : stk) res += "/"+str;
return res.empty() ? "/" : res;
}


## 43. Multiply Strings

### Problem Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

### Method

string multiply(string num1, string num2) {
string sum(num1.size() + num2.size(), '0');

for (int i = num1.size() - 1; 0 <= i; --i) {
int carry = 0;
for (int j = num2.size() - 1; 0 <= j; --j) {
int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
sum[i + j + 1] = tmp % 10 + '0';
carry = tmp / 10;
}
sum[i] += carry;
}

size_t startpos = sum.find_first_not_of("0");
if (string::npos != startpos) {
return sum.substr(startpos);
}
return "0";
}


## 10. Regular Expression Matching

### Problem Description

Implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char s, const char p)

Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a“) → true
isMatch(“aa”, “.
“) → true
isMatch(“ab”, “.“) → true
isMatch(“aab”, “c
a*b”) → true

### Method

1. p[j-1]!='*'，这时候如果前一段s和p匹配(dp[i-1][j-1] == true)且当前字符相等(p[j-1]==s[i-1])或p[j-1] == '.'dp[i][j]==truee
2. p[j-1]=='*',有两种情况
1. ‘*’前面的字符出现0次
dp[i][j] = dp[i][j-2]
2. ‘*’前面的字符出现至少1次
dp[i][j] = dp[i-1][j] && s[i-1] == p[i-2] || p[i-2] == '.'
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool> > dp(m + 1, vector<bool> (n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++)
for (int j = 1; j <= n; j++)
if (p[j - 1] == '*')
dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
return dp[m][n];
}
};


## 72. Edit Distance

### Problem Description

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

1. 删除字符
2. 插入字符
3. 替换字符

### Method

1. 如果word1[i]==word2[j],则两字符串已经相等dp[i][j]==dp[i-1][j-1]
2. 如果word1[i]!=word2[j],则需要考虑以下情况
1. 如果word1比word2更长，且已知dp[i-1][j],则需要将多余的字符删掉，dp[i][j] == dp[i-1][j] + 1
2. 如果dp[i][j-1]后，word1比word2更短，且已知dp[i][j-1],则需要把word2第j一个字符删除（或将该字符复制到word1的末尾），dp[i][j] == dp[i][j-1] + 1
3. 如果dp[i-1][j-1]操作后word1和word2等长，则只需要将word1第i个字符改为word2的第j个字符，dp[i][j] == dp[i-1][j-1] + 1
class Solution {
public:
int minDistance(string word1, string word2) {
size_t m = word1.length(), n = word2.length();
if (m == 0)
return n;
if (n == 0)
return m;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 0; i <= m; ++i)
dp[i][0] = i;
for (int j = 0; j <= n; ++j)
dp[0][j] = j;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1));
return dp[m][n];
}
};


## 68. Text Justification

### Problem Description

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]
L: 16.

Return the formatted lines as:
[
“This is an”,
“example of text”,
“justification. “
]
Note: Each word is guaranteed not to exceed L in length.

Corner Cases:
A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.

### Method

1. 计算每行最多能容纳的单词数
2. 在单词之间补零
1. 若为最后一行，单词之间只能由一个空格
2. 若不是最后一行，在单词之间平分多余的空格，然后将剩余的空格分给每个单词的左边
vector<string> fullJustify(vector<string> &words, int L) {
vector<string> res;
for(int i = 0, k, l; i < words.size(); i += k) {
//计算本行单词数量k
for(k = l = 0; i + k < words.size() and l + words[i+k].size() <= L - k; k++) {
l += words[i+k].size();
}

string tmp = words[i];
for(int j = 0; j < k - 1; j++) {
//若为最后一行，每个单词之间只添加一个空格
if(i + k >= words.size()) tmp += " ";
// 如果不是最后一行，先在单词间添加相等数量的空格，剩余空格添加到单词左边
else tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' ');
tmp += words[i+j+1];
}
tmp += string(L - tmp.size(), ' ');
res.push_back(tmp);
}
return res;
}


## 76. Minimum Window Substring

### Problem Description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
T = “ABC”
Minimum window is “BANC”.

Note:
If there is no such window in S that covers all characters in T, return the empty string “”.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

### Method

string minWindow(string s, string t) {
vector<int> map(128,0);
for(auto c: t) map[c]++;
int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
while(end<s.size()){
if(map[s[end++]]-->0) counter--; //in t
while(counter==0){ //valid
if(map[s[begin++]]++==0) counter++;  //make it invalid
}
}
}


# 关于大多数寻找子串的问题，都可以使用下面的模板

int findSubstring(string s){
vector<int> map(128,0);
int counter; // check whether the substring is valid
int begin=0, end=0; //two pointers, one point to tail and one  head
int d; //the length of substring

for() { /* initialize the hash map here */ }

while(end<s.size()){

if(map[s[end++]]-- ?){  /* modify counter here */ }

while(/* counter condition */){

/* update d here if finding minimum*/

//increase begin to make it invalid/valid again

if(map[s[begin++]]++ ?){ /*modify counter here*/ }
}

/* update d here if finding maximum*/
}
return d;
}


int lengthOfLongestSubstringTwoDistinct(string s) {
vector<int> map(128, 0);
int counter = 0;
int start = 0, end = 0;
int d = 0;
while (end < s.size())
{
if (map[s[end++]]++ == 0) counter ++;
while (counter > 2) if(map[s[start++]]-- == 1) counter--;
d = max(d, end - start);
}
return d;
}


int lengthOfLongestSubstring(string s) {
vector<int> map(128, 0);
int begin = 0, end = 0;
int d = 0;
while(end < s.size())
{
if (map[s[end++]]++ > 0) counter++;
while(counter > 0) if (map[s[begin++]]-- > 1) counter--;
d = max(d, end - begin);
}
}


### Problem Description

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:

beginWord = "hit"

endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

### Method

1. 如果替换一位字符后的单词出现在了endVec中，那么已经找到了变换路径，返回len+1;
2. 若替换一位后的单词不在endVec中，但是在WordList中，则该单词可能是路径中间单词，将其存入下一次的左边搜索空间(tmp)中, 同时将该单词从wordList中删除，避免重复使用。

class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
string::size_type len = 1, strLen = beginWord.length();
vector<string> beginVec({beginWord}), endVec({endWord});
while (beginVec.size() > 0 and endVec.size() > 0)
{
// 以较长的vector作为beginVec，能有效减少比较的次数
if (beginVec.size() > endVec.size())
beginVec.swap(endVec);

vector<string> tmp;
for (string word : beginVec)
{
for (string::size_type i = 0; i < word.length(); ++i)
{
for (char ch = 'a'; ch <= 'z'; ++ch)
{
char old = word[i];
if (ch == old)
continue;
word[i] = ch;

auto posWordList = find(wordList.begin(), wordList.end(), word);
// 如果替换一个字符后的word存在于endWord，说明已经找到路径了，直接返回路径长度
if (find(endVec.begin(), endVec.end(), word) != endVec.end())
return len + 1;
// 如果替换一个字符后的word不在endWord中，但在wordList中，则将该word存入下次的beginVec(tmp)中
else if ( posWordList != wordList.end())
{
tmp.push_back(word);
wordList.erase(posWordList);
}
word[i] = old;
}

}
}
beginVec = tmp;
++len;
}
return 0;
}
};


### Problem Description

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

 [
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]


Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

### Method

class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
vector<string> path({beginWord});
vector<vector<string>> res;
unordered_map<string, vector<string>> forest;
return res;

}

bool findLadders(string start, string end, vector<string> &wordList, unordered_map<string, vector<string>> &forest)
{
vector<string> beginVec({start}), endVec({end});
bool flip = false, found = false;
while (!beginVec.empty() and !endVec.empty())
{
if (beginVec.size() > endVec.size())
{
flip = !flip;
beginVec.swap(endVec);
}
vector<string> tmp;
for (string word : beginVec)
{
string originWord = word;
for (int i = 0; i < word.length(); ++i)
{
char old = word[i];
for (char ch = 'a'; ch <= 'z'; ++ch)
{
if (ch == old)
continue;
word[i] = ch;
if (find(endVec.begin(), endVec.end(), word) != endVec.end())
{
flip ? forest[word].push_back(originWord) : forest[originWord].push_back(word);
found = true;
}
else if (find(wordList.begin(), wordList.end(), word) != wordList.end())
{
flip ? forest[word].push_back(originWord) : forest[originWord].push_back(word);
tmp.push_back(word);
}
}
word[i] = old;
}
}
if (found) return true;
for (string word : tmp)
wordList.erase(find(wordList.begin(), wordList.end(), word));
beginVec = tmp;

}
return false;
}

void getLadders(string begin, string end, unordered_map<string, vector<string>> &nexts, \
vector<string> &path, vector<vector<string>> res)
{
if (begin == end)
{
res.push_back(path);
return;
}
for (string str : nexts[begin])
{
path.push_back(str);
path.pop_back();
}
}

};


## 115. Distinct Subsequences

### Problem Description

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:

S = "rabbbit", T = "rabbit"

Return 3.

### Method

1. 如果i>0 and j==0即s子串长度大于0,t子串长度为0，这时只有把s子串中所有字符删除才能变换为t子串，故这种情况下dp[i][j]=dp[i][0]=1
2. 如果i < j,这时s子串已经比t的子串要短了，不可能通过删除字符的方法将s的子串转换为t的子串，故dp[i][j]=0

1. s[i-1]==t[j-1]:这时有两种情况:

1. s[0,...,i-1]转换到t[0,...,j-1]的过程中把s[i-1]删除了，此时相当于要把s[0,...,i-2]转换为t[0,...,i-1],即dp[i][j]=dp[i-1][j]

2. s[0,...,i-1]转换到t[0,...,j-1]的过程保留了s[i-1],这时，因为s[i-1]已经和t[j-1]对应上了，这对字符不起作用，所以dp[i][j]=dp[i-1][j-1]

因此，结合上面两种情况dp[i][j]=dp[i-1][j]+dp[i-1][j-1]

2. s[i-1]!=t[j-1]

此时，若保留s[i-1]，两个串必定对不上，所以应该将其删除，因此dp[i][j]=dp[i-1][j]

class Solution {
public:
int numDistinct(string s, string t) {
int m = s.length(), n = t.length();

vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i = 0; i <= m; ++i)
dp[i][0] = 1;

for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n ; ++j)
{
dp[i][j] = dp[i-1][j];
if(s[i-1] == t[j-1])
dp[i][j] += dp[i-1][j-1];
}
return dp[m][n];
}
};


## 97 Interleaving String

### Problem Description

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,

Given:

s1 = "aabcc",

s2 = "dbbca",

When s3 = "aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

### Method

1. 若果i==0 and j==0,则两个空串必然能构成另一个空串，dp[0][0]=true
2. 假如i==0j==0,则s3[0,...,i+j-1]只能由另外一个非空字符串构成，dp[i][0]=dp[i-1][0] && s1[i-1] == s3[i-1]dp[i][0]=dp[0][j-1] && s2[j-1] == s3[j-1]
3. 其他情况下，s3新增加的字符要么来自于s1要么来自于s2,如果来自于s1的话dp[i-1][j] && (s1[i-1] == s3[i - 1 +j]，如果来自于s2的话dp[i][j-1] && (s2[j-1] == s3[i + j -1])
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
string::size_type len1 = s1.length(), len2 = s2.length();
if (s3.length() != len1 + len2)
return false;
vector<vector<bool>> dp(len1+1, vector<bool>(len2+1, false));
for (int i = 0; i <= len1; ++i)
for(int j = 0; j <= len2; ++j)
{
if (i == 0 and j == 0)
dp[i][j] = true;
else if (i == 0)
dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1]);
else if (j == 0)
dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1]);
else
// s3的当前字符要么来自s1要么来自s2
dp[i][j] = (dp[i][j-1] && (s2[j-1] == s3[i + j -1])) || (dp[i-1][j] && (s1[i-1] == s3[i - 1 +j]));
}
return dp[len1][len2];
}
};


## 87. Scramble String

### Problem Description

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

great


/ \
gr eat
/ \ / \
g r e at
/ \
a t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

rgeat


/ \
rg eat
/ \ / \
r g e at
/ \
a t

We say that “rgeat” is a scrambled string of “great”.

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

rgtae


/ \
rg tae
/ \ / \
r g ta e
/ \
t a

We say that “rgtae” is a scrambled string of “great”.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

### Method

class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1 == s2)
return true;
// 判断两个字符串每个字符数是否相等
vector<int> table(26, 0);
for (char ch : s1)
table[ch - 'a']++;
for (char ch : s2)
table[ch - 'a']--;
for (int num : table)
if (num != 0)
return false;
string::size_type len = s1.length();
for (int i = 1; i < len; ++i)
{
if (isScramble(s1.substr(0, i), s2.substr(0, i)) and isScramble(s1.substr(i), s2.substr(i)))
return true;
if (isScramble(s1.substr(0, i), s2.substr(len - i)) and isScramble(s1.substr(i), s2.substr(0, len - i)))
return true;
}
return false;

}
};


## 65. Valid Number

### Problem Description

Validate if a given string is numeric.

Some examples:

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Update (2015-02-10):

The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

class Solution {
public:
bool isNumber(string str) {
int state=0, flag=0; // flag to judge the special case "."
while(str[0]==' ')  str.erase(0,1);//delete the  prefix whitespace
while(str[str.length()-1]==' ') str.erase(str.length()-1, 1);//delete the suffix whitespace
for(int i=0; i<str.length(); i++){
if('0'<=str[i] && str[i]<='9'){
flag=1;
if(state<=2) state=2;
else state=(state<=5)?5:7;
}
else if('+'==str[i] || '-'==str[i]){
if(state==0 || state==3) state++;
else return false;
}
else if('.'==str[i]){
if(state<=2) state=6;
else return false;
}
else if('e'==str[i]){
if(flag&&(state==2 || state==6 || state==7)) state=3;
else return false;
}
else return false;
}
return (state==2 || state==5 || (flag&&state==6) || state==7);
}
};


## 494. Target Sum

### Problem Description

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:

The length of the given array is positive and will not exceed 20.

The sum of elements in the given array will not exceed 1000.

Your output answer is guaranteed to be fitted in a 32-bit integer.

### Method

P - N == S

P- N + P + N == S + sum(nums), 即2*P == S + sum(nums),因此，我们的问题转化成了求子数组使得其和等于(S+sum(nums))/2，另外需要注意的是，我们可以看到上式左边乘2了，所以S+sum(nums)必须是偶数，如果不是偶数肯定没有符合要求的结果，直接返回0.

class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if ((sum + S) % 2 != 0 or sum < S)
return 0;
int target = (sum + S) / 2;
return subsetSum(nums, target);
}

int subsetSum(vector<int> &nums, int target)
{
vector<int> dp(target+1, 0);
dp[0] = 1;
for (int num : nums)
for(int i = target; i >= num; --i)
dp[i]+=dp[i-num];

return dp[target];
}
};


## 300. Longest Increasing Subsequence

### Problem Description

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

### Method

#### $O(N^2)$的解法

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// return 0;
if (nums.empty())
return 0;
int len = nums.size();
vector<int> dp(len, 0);
dp[0] = 1;
for (int i = 1; i < len; ++i)
{
int max_len = 1;
for (int j = 0; j < i; ++j)
if (nums[i] > nums[j])
max_len = max(dp[j] + 1, max_len);
dp[i] = max_len;
}
int max_len = 1;
for (int len : dp)
max_len = max(len, max_len);
return max_len;

}
};


#### $O(NlogN)$解法

// Java program to find length of longest increasing subsequence
// in O(n Log n) time
import java.io.*;
import java.util.*;
import java.lang.Math;

class LIS
{
// Binary search (note boundaries in the caller)
// A[] is ceilIndex in the caller
static int CeilIndex(int A[], int l, int r, int key)
{
while (r - l > 1)
{
int m = l + (r - l)/2;
if (A[m]>=key)
r = m;
else
l = m;
}

return r;
}

static int LongestIncreasingSubsequenceLength(int A[], int size)
{
// Add boundary case, when array size is one

int[] tailTable   = new int[size];
int len; // always points empty slot

tailTable[0] = A[0];
len = 1;
for (int i = 1; i < size; i++)
{
if (A[i] < tailTable[0])
// new smallest value
tailTable[0] = A[i];

else if (A[i] > tailTable[len-1])
// A[i] wants to extend largest subsequence
tailTable[len++] = A[i];

else
// A[i] wants to be current end candidate of an existing
// subsequence. It will replace ceil value in tailTable
tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i];
}

return len;
}

// Driver program to test above function
public static void main(String[] args)
{
int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
int n = A.length;
System.out.println("Length of Longest Increasing Subsequence is "+
LongestIncreasingSubsequenceLength(A, n));
}
}
/* This code is contributed by Devesh Agrawal*/


## 386. Largest Divisible Subset

### Problem Description

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si= 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]


Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]


Result: [1,2,4,8]

### Method

class Solution
{
public:
vector<int> largestDivisibleSubset(vector<int>& nums)
{
sort(nums.begin(), nums.end());
int len = nums.size();
vector<int> dp(len, 0), son(len, 0);
// m存储最大长度，mi存储最长子序列的末尾序号
int m, mi;
for(int i =0; i < len; ++i)
{
for(int j = i; i >=0; ++j)
{
if(nums[i] % nums[j] == 0 and dp[i] < dp[j]+1)
{
dp[i] = dp[j] + 1;
son[i] = j;
}
}
if (dp[i] > m)
{
m = dp[i];
mi = i;
}
}
vector<int> res;
for (int i = 0; i < m; ++i)
{
res.insert(res.begin(), num[mi]);
mi = son[mi];
}
return res;
}
};


# dynamic programming

## 198. House Robber I

### Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Method

int i = include, int e = exclude;
include = exclude + nums[j];
exclude = max(i, e);

class Solution
{
public:
int rob(vector<int> nums)
{
int len = nums.size();
int include = 0, exclude = 0;
for (int j = 0; j < len; ++j)
{
int i = include, e = exclude;
include = exclude + nums[j];
exclude = max(i, e);
}
return max(include, exclude);
}
};


class Solution {
public:
int rob(vector<int>& nums) {
int is_odd;
vector<int> robs(2, 0);
for (int i = 0; i < nums.size(); ++i)
{
is_odd = i % 2;
robs[is_odd] = max(robs[is_odd] + nums[i], robs[1 - is_odd]);
// if (i % 2 == 0)
//     rob_even = max(rob_even + nums[i], rob_odd);
// else
//     rob_odd = max(rob_odd + nums[i], rob_even);
}
return max(robs[0], robs[1]);
}
};


## Problem Description

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Method

class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 1)
return nums[0];
return max(rob(nums, 0, len-2), rob(nums, 1, len-1));
}
int rob(vector<int>& nums, int lo, int hi)
{
int include = 0, exclude = 0;
for (int j = lo; j <= hi; ++j)
{
int i = include, e = exclude;
include = exclude + nums[j];
exclude = max(i, e);
}
return max(include, exclude);
}
};


## 337. House Robber III

### Problem Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.

### Method

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
vector<int> res = robSub(root);
return max(res[0], res[1]);

}

vector<int> robSub(TreeNode* root)
{
if (root == NULL)
return vector<int>(2, 0);

vector<int> left = robSub(root->left);
vector<int> right = robSub(root->right);

vector<int> res(2, 0);
res[1] = root->val + left[0] + right[0];
res[0] = max(left[1], left[0]) + max(right[0], right[1]);
return res;

}
};


## 516. Longest Palindromic Subsequence

### Problem Description

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

“bbbab”
Output:
4
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:

“cbbd”
Output:
2
One possible longest palindromic subsequence is “bb”.

### Method

1. 重新定义题目
将字符串切分成短的子串，通过短子串的最长回文得到包含它的长串的回文长度
2. 定义状态
dp[i][j]表示子串s[1,...,n]的最长回文长度
3. 状态转移
如果子串s[i+1, ..., j-1]两边的字符相等，则子串长度要加上这两个字符,
如果俩字符不相等，则s[i,...,j]最长回文为dp[i][j-1]dp[i+1][j]中最长的一个
因为要求dp[i][j]需要先知道dp[i+1][j-1]dp[i][j-1],dp[i+1][j],所以求解过程中，i应该减,j应该递增
class Solution {
public:
int longestPalindromeSubseq(string s) {
string::size_type len = s.length();
vector<vector<int>> dp(len, vector<int>(len, 0));
for (int i = len - 1; i >=0; --i)
{
dp[i][i] = 1;
for (int j = i+1; j < len; ++j)
{
if (s[i] == s[j])
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][len-1];

}
};


## 467. Unique Substring in Wraparound Strig

### Problem Description

Consider the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:
Input: “a”
Output: 1

Explanation: Only the substring “a” of string “a” is in the string s.
Example 2:
Input: “cac”
Output: 2
Explanation: There are two substrings “a”, “c” of string “cac” in the string s.
Example 3:
Input: “zab”
Output: 6
Explanation: There are six substrings “z”, “a”, “b”, “za”, “ab”, “zab” of string “zab” in the string s.

### Method

class Solution {
public:
int findSubstringInWraproundString(string p) {
string::size_type len = p.length();
vector<int> dp(26, 0);
int maxLen = 0;
for (int i = 0; i < len; ++i)
{
if (i > 0 and (p[i] - p[i-1] == 1 or p[i-1] - p[i] == 25))
maxLen++;
else
maxLen = 1;
int idx = p[i] - 'a';
dp[idx] = max(dp[idx], maxLen);
}
return accumulate(dp.begin(), dp.end(), 0);

}
};


## 416. Partition Equal Subset Sum

### Problem Description

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

### Method

class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0)
return false;
int target = sum / 2;
vector<bool> dp(target+1, false);
dp[0] = true;
for (int num : nums)
for (int i = target; i >= num; --i)
{
dp[i] = dp[i - num] or dp[i];
if (i == target and dp[i])
return true;
}

return dp[target];

}
};


## 413. Arithmetic Slices

### Problem Description

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

### Method

class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
if (A.size() < 3)
return 0;
int len = 2;
int d = A[1] - A[0];
int res = 0;
for (int i = 2; i < A.size(); ++i)
{
if (A[i] - A[i-1] == d)
{
++len;
res += len - 2;
}
else
{
len = 2;
d = A[i] - A[i-1];
}
}
return res;

}
};


## 139. Word Break

### Problem Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = “leetcode”,
dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

### Method

dp[i]表示子串s[i,...,n]能否通过字典拼接成。

class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
// 状态dp[i], s[i到n]是否满足条件
// dp[i] = dp[j+1] and s[i到j] $\in$ wordDict
string::size_type len = s.length();
vector<bool> dp(len+1, false);
dp[len] = true;
for (int i = len - 1; i >= 0; i--)
for (int j = i; j < len; ++j)
{
string str = s.substr(i, j-i+1);
if (dp[j+1] and find(wordDict.begin(), wordDict.end(), str) != wordDict.end())
{
dp[i] = true;
break;
}
}
return dp[0];
}
};


## 322. Coin Change

### Problem Description

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:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

### Method

class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int MAX = amount+1;
vector<int> dp(amount+1, MAX);
dp[0] = 0;
for (int coin : coins)
// 由低位向高位相加，这样一个面额的硬币就可以出现多次了
for (int i = coin; i <=amount; i++)
{
dp[i] = min(dp[i-coin]+1, dp[i]) ;
}
return dp[amount] > amount ? -1 : dp[amount];
}
};


## 304. Range Sum Query 2D-Immutable

### Problem Description

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

### Method

class NumMatrix {
private:
int row, col;
vector<vector<int>> sums;
public:
NumMatrix(vector<vector<int>> matrix) {
row = matrix.size();
col = row>0 ? matrix[0].size() : 0;
sums = vector<vector<int>>(row+1, vector<int>(col+1, 0));
for(int i=1; i<=row; i++) {
for(int j=1; j<=col; j++) {
sums[i][j] = matrix[i-1][j-1] +
sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] ;
}
}
}

int sumRegion(int row1, int col1, int row2, int col2) {
return sums[row2+1][col2+1] - sums[row2+1][col1] - sums[row1][col2+1] + sums[row1][col1];
}
};

/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/


## 279. Perfect Squares

### Problem Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

### Method

class Solution {
public:
int numSquares(int n) {
//     static vector<int> dp {0};
// int m = dp.size();
// dp.resize(max(m, n+1), INT_MAX);
// for (int i=1, i2; (i2 = i*i)<=n; ++i)
//     for (int j=max(m, i2); j<=n; ++j)
//         if (dp[j] > dp[j-i2] + 1)
//             dp[j] = dp[j-i2] + 1;
// return dp[n];
vector<int> dp(n+1, n);
dp[0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1, j2; (j2 = j*j) <= i; ++j)
if (dp[i] > dp[i-j2])
dp[i] = dp[i-j2] + 1;
// p[i] = min(dp[i], dp[i-j*j] + 1);
return dp[n];

}
};


## 486. Predict the Winner

### Problem Description

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

### Method

class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
size_t len = nums.size();
if (len % 2 == 0)
return true;
vector<vector<int>> dp(len, vector<int>(len, 0));
for (int i = len-1; i >= 0; --i)
{
dp[i][i] = nums[i];
for (int j = i + 1; j < len; ++j)
{
int a = ((i+1<len and j-1>=0) ? dp[i+1][j-1] : 0) ;
int b = ((i+2<len) ? dp[i+2][j] : 0);
int c = ((j-2>=0) ? dp[i][j-2] : 0);
dp[i][j] = max(min(a, b) + nums[i], + min(a, c) + nums[j]);
}
}
return 2*dp[0][len-1] >= accumulate(nums.begin(), nums.end(), 0);
}
};


## 523. Continuous Subarray Sum

### Problem Description

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Example 2:
Input: [23, 2, 6, 4, 7], k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
Note:
The length of the array won’t exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

### Method

class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> map;
map[0] = -1;
int runningSum = 0;
for (int i = 0; i < nums.size(); ++i)
{
runningSum += nums[i];
if (k != 0)
runningSum %= k;
if (map.find(runningSum) != map.end())
{
if (i - map[runningSum] > 1)
return true;
}
else
map[runningSum] = i;
}
return false;
}
};


## 221. Maximal Square

### Problem Description

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

### Method

i=0时，如果matrix[0][j]=='1'则该处最大正方形面积为1否则为0，当j=0时类似。

1 1
1 0


#### 方法1 空间复杂度$O(NM)$

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size();
if (rows == 0)
return 0;
int cols = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(cols, 0));
int maxSize = 0;
for (int j = 0; j < cols; j++)
{
dp[0][j] = matrix[0][j] - '0';
maxSize = max(maxSize, dp[0][j]);
}
for (int i = 1; i < rows; i++)
{
dp[i][0] = matrix[i][0] - '0';
maxSize = max(maxSize, dp[i][0]);
}

for (int i = 1; i < rows; i++)
for (int j = 1; j < cols; ++j)
{
if (matrix[i][j] == '0')
continue;
dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
if (dp[i][j] > maxSize)
maxSize = dp[i][j];
}
return maxSize * maxSize;

}
};


#### 方法二 空间复杂度O(M)

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int rows = matrix.size();
if (rows == 0)
return 0;
int cols = matrix[0].size();
vector<int> pre(cols, 0), cur(cols, 0);
int maxSize = 0;
for (int i = 0; i < cols; ++i)
{
pre[i] = matrix[0][i] - '0';
maxSize  = max(maxSize, pre[i]);
}
for (int i = 1; i < rows; ++i)
{
cur[0] = matrix[i][0] - '0';
maxSize = max(maxSize, cur[0]);
for (int j = 1; j < cols; ++j)
{
if (matrix[i][j] == '0')
continue;
cur[j] = min(pre[j], min(pre[j-1], cur[j-1])) + 1;
maxSize = max(maxSize, cur[j]);
}
swap(pre, cur);
fill(cur.begin(), cur.end(), 0);
}
return maxSize * maxSize;

}

};


#### 方法三 空间复杂度$O(M)$

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
if (matrix.empty())
return 0;
int rows = matrix.size(), cols = matrix[0].size();
vector<int> dp(cols+1, 0);
int pre = 0, maxSize=0;
for (int i = 0; i < rows; ++i)
for (int j = 1; j <= cols; ++j)
{
int tmp = dp[j];
if (matrix[i][j-1] == '1')
{
dp[j] = min(dp[j], min(dp[j-1], pre)) + 1;
maxSize = max(maxSize, dp[j]);
}
else
dp[j] = 0;
pre = tmp;
}
return maxSize*maxSize;
}
};


## 198. House Robber I

### Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Method

int i = include, int e = exclude;
include = exclude + nums[j];
exclude = max(i, e);

class Solution
{
public:
int rob(vector<int> nums)
{
int len = nums.size();
int include = 0, exclude = 0;
for (int j = 0; j < len; ++j)
{
int i = include, e = exclude;
include = exclude + nums[j];
exclude = max(i, e);
}
return max(include, exclude);
}
};


class Solution {
public:
int rob(vector<int>& nums) {
int is_odd;
vector<int> robs(2, 0);
for (int i = 0; i < nums.size(); ++i)
{
is_odd = i % 2;
robs[is_odd] = max(robs[is_odd] + nums[i], robs[1 - is_odd]);
// if (i % 2 == 0)
//     rob_even = max(rob_even + nums[i], rob_odd);
// else
//     rob_odd = max(rob_odd + nums[i], rob_even);
}
return max(robs[0], robs[1]);
}
};


## Problem Description

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Method

class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 1)
return nums[0];
return max(rob(nums, 0, len-2), rob(nums, 1, len-1));
}
int rob(vector<int>& nums, int lo, int hi)
{
int include = 0, exclude = 0;
for (int j = lo; j <= hi; ++j)
{
int i = include, e = exclude;
include = exclude + nums[j];
exclude = max(i, e);
}
return max(include, exclude);
}
};


## 337. House Robber III

### Problem Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.

### Method

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
vector<int> res = robSub(root);
return max(res[0], res[1]);

}

vector<int> robSub(TreeNode* root)
{
if (root == NULL)
return vector<int>(2, 0);

vector<int> left = robSub(root->left);
vector<int> right = robSub(root->right);

vector<int> res(2, 0);
res[1] = root->val + left[0] + right[0];
res[0] = max(left[1], left[0]) + max(right[0], right[1]);
return res;

}
};


# HashTable

## 500. KeyboardRow

### Problem Description

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

Example 1:
Note:
You may use one character in the keyboard more than once.
You may assume the input string will only contain letters of alphabet.

### METHOD

class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<int> keydict(123, 0);
vector<string> rows({"qwertyuiopQWERTYUIOP", "asdfghjklASDFGHJKL", "zxcvbnmZXCVBNM"});
for (int i = 0; i < rows.size(); ++i)
for (char ch : rows[i])
keydict[ch] = i;
vector<string> rst;
for (string word : words)
{
int i = keydict[word[0]];
bool flag = true;
for (char ch : word)
if (keydict[ch] != i)
{
flag = false;
break;
}
if (flag)
rst.push_back(word);
}
return rst;
}
};


## 221. Maximal Square

### Problem Description

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

### Method

i=0时，如果matrix[0][j]=='1'则该处最大正方形面积为1否则为0，当j=0时类似。

1 1
1 0


#### 方法1 空间复杂度$O(NM)$

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size();
if (rows == 0)
return 0;
int cols = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(cols, 0));
int maxSize = 0;
for (int j = 0; j < cols; j++)
{
dp[0][j] = matrix[0][j] - '0';
maxSize = max(maxSize, dp[0][j]);
}
for (int i = 1; i < rows; i++)
{
dp[i][0] = matrix[i][0] - '0';
maxSize = max(maxSize, dp[i][0]);
}

for (int i = 1; i < rows; i++)
for (int j = 1; j < cols; ++j)
{
if (matrix[i][j] == '0')
continue;
dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
if (dp[i][j] > maxSize)
maxSize = dp[i][j];
}
return maxSize * maxSize;

}
};


#### 方法二 空间复杂度O(M)

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int rows = matrix.size();
if (rows == 0)
return 0;
int cols = matrix[0].size();
vector<int> pre(cols, 0), cur(cols, 0);
int maxSize = 0;
for (int i = 0; i < cols; ++i)
{
pre[i] = matrix[0][i] - '0';
maxSize  = max(maxSize, pre[i]);
}
for (int i = 1; i < rows; ++i)
{
cur[0] = matrix[i][0] - '0';
maxSize = max(maxSize, cur[0]);
for (int j = 1; j < cols; ++j)
{
if (matrix[i][j] == '0')
continue;
cur[j] = min(pre[j], min(pre[j-1], cur[j-1])) + 1;
maxSize = max(maxSize, cur[j]);
}
swap(pre, cur);
fill(cur.begin(), cur.end(), 0);
}
return maxSize * maxSize;

}

};


#### 方法三 空间复杂度$O(M)$

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
if (matrix.empty())
return 0;
int rows = matrix.size(), cols = matrix[0].size();
vector<int> dp(cols+1, 0);
int pre = 0, maxSize=0;
for (int i = 0; i < rows; ++i)
for (int j = 1; j <= cols; ++j)
{
int tmp = dp[j];
if (matrix[i][j-1] == '1')
{
dp[j] = min(dp[j], min(dp[j-1], pre)) + 1;
maxSize = max(maxSize, dp[j]);
}
else
dp[j] = 0;
pre = tmp;
}
return maxSize*maxSize;
}
};


## 198. House Robber I

### Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Method

int i = include, int e = exclude;
include = exclude + nums[j];
exclude = max(i, e);

class Solution
{
public:
int rob(vector<int> nums)
{
int len = nums.size();
int include = 0, exclude = 0;
for (int j = 0; j < len; ++j)
{
int i = include, e = exclude;
include = exclude + nums[j];
exclude = max(i, e);
}
return max(include, exclude);
}
};


class Solution {
public:
int rob(vector<int>& nums) {
int is_odd;
vector<int> robs(2, 0);
for (int i = 0; i < nums.size(); ++i)
{
is_odd = i % 2;
robs[is_odd] = max(robs[is_odd] + nums[i], robs[1 - is_odd]);
// if (i % 2 == 0)
//     rob_even = max(rob_even + nums[i], rob_odd);
// else
//     rob_odd = max(rob_odd + nums[i], rob_even);
}
return max(robs[0], robs[1]);
}
};


## Problem Description

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Method

class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 1)
return nums[0];
return max(rob(nums, 0, len-2), rob(nums, 1, len-1));
}
int rob(vector<int>& nums, int lo, int hi)
{
int include = 0, exclude = 0;
for (int j = lo; j <= hi; ++j)
{
int i = include, e = exclude;
include = exclude + nums[j];
exclude = max(i, e);
}
return max(include, exclude);
}
};


## 337. House Robber III

### Problem Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.

### Method

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
vector<int> res = robSub(root);
return max(res[0], res[1]);

}

vector<int> robSub(TreeNode* root)
{
if (root == NULL)
return vector<int>(2, 0);

vector<int> left = robSub(root->left);
vector<int> right = robSub(root->right);

vector<int> res(2, 0);
res[1] = root->val + left[0] + right[0];
res[0] = max(left[1], left[0]) + max(right[0], right[1]);
return res;

}
};


# Greedy

## 406. Queue Reconstruction by Height

### Problem Description

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:

## [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

### Method

class Solution {
public:
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2 ){return ((p1.first > p2.first) || (p1.first == p2.first && p1.second < p2.second)); };
sort(people.begin(), people.end(), comp);
vector<pair<int, int>> res;
for (auto p: people)
res.insert(res.begin() + p.second, p);
return res;
}
};


## 221. Maximal Square

### Problem Description

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

### Method

i=0时，如果matrix[0][j]=='1'则该处最大正方形面积为1否则为0，当j=0时类似。

1 1
1 0


#### 方法1 空间复杂度$O(NM)$

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size();
if (rows == 0)
return 0;
int cols = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(cols, 0));
int maxSize = 0;
for (int j = 0; j < cols; j++)
{
dp[0][j] = matrix[0][j] - '0';
maxSize = max(maxSize, dp[0][j]);
}
for (int i = 1; i < rows; i++)
{
dp[i][0] = matrix[i][0] - '0';
maxSize = max(maxSize, dp[i][0]);
}

for (int i = 1; i < rows; i++)
for (int j = 1; j < cols; ++j)
{
if (matrix[i][j] == '0')
continue;
dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
if (dp[i][j] > maxSize)
maxSize = dp[i][j];
}
return maxSize * maxSize;

}
};


#### 方法二 空间复杂度O(M)

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int rows = matrix.size();
if (rows == 0)
return 0;
int cols = matrix[0].size();
vector<int> pre(cols, 0), cur(cols, 0);
int maxSize = 0;
for (int i = 0; i < cols; ++i)
{
pre[i] = matrix[0][i] - '0';
maxSize  = max(maxSize, pre[i]);
}
for (int i = 1; i < rows; ++i)
{
cur[0] = matrix[i][0] - '0';
maxSize = max(maxSize, cur[0]);
for (int j = 1; j < cols; ++j)
{
if (matrix[i][j] == '0')
continue;
cur[j] = min(pre[j], min(pre[j-1], cur[j-1])) + 1;
maxSize = max(maxSize, cur[j]);
}
swap(pre, cur);
fill(cur.begin(), cur.end(), 0);
}
return maxSize * maxSize;

}

};


#### 方法三 空间复杂度$O(M)$

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
if (matrix.empty())
return 0;
int rows = matrix.size(), cols = matrix[0].size();
vector<int> dp(cols+1, 0);
int pre = 0, maxSize=0;
for (int i = 0; i < rows; ++i)
for (int j = 1; j <= cols; ++j)
{
int tmp = dp[j];
if (matrix[i][j-1] == '1')
{
dp[j] = min(dp[j], min(dp[j-1], pre)) + 1;
maxSize = max(maxSize, dp[j]);
}
else
dp[j] = 0;
pre = tmp;
}
return maxSize*maxSize;
}
};


## 198. House Robber I

### Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Method

int i = include, int e = exclude;
include = exclude + nums[j];
exclude = max(i, e);

class Solution
{
public:
int rob(vector<int> nums)
{
int len = nums.size();
int include = 0, exclude = 0;
for (int j = 0; j < len; ++j)
{
int i = include, e = exclude;
include = exclude + nums[j];
exclude = max(i, e);
}
return max(include, exclude);
}
};


class Solution {
public:
int rob(vector<int>& nums) {
int is_odd;
vector<int> robs(2, 0);
for (int i = 0; i < nums.size(); ++i)
{
is_odd = i % 2;
robs[is_odd] = max(robs[is_odd] + nums[i], robs[1 - is_odd]);
// if (i % 2 == 0)
//     rob_even = max(rob_even + nums[i], rob_odd);
// else
//     rob_odd = max(rob_odd + nums[i], rob_even);
}
return max(robs[0], robs[1]);
}
};


## Problem Description

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Method

class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 1)
return nums[0];
return max(rob(nums, 0, len-2), rob(nums, 1, len-1));
}
int rob(vector<int>& nums, int lo, int hi)
{
int include = 0, exclude = 0;
for (int j = lo; j <= hi; ++j)
{
int i = include, e = exclude;
include = exclude + nums[j];
exclude = max(i, e);
}
return max(include, exclude);
}
};


## 337. House Robber III

### Problem Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.

### Method

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
vector<int> res = robSub(root);
return max(res[0], res[1]);

}

vector<int> robSub(TreeNode* root)
{
if (root == NULL)
return vector<int>(2, 0);

vector<int> left = robSub(root->left);
vector<int> right = robSub(root->right);

vector<int> res(2, 0);
res[1] = root->val + left[0] + right[0];
res[0] = max(left[1], left[0]) + max(right[0], right[1]);
return res;

}
};


# sort

## 506. Relative Ranks

### Problem Description

Given scores of N athletes, find their relative ranks> and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.
>

Example 1:
Input: [5, 4, 3, 2, 1]
Output: [“Gold Medal”, “Silver Medal”, “Bronze Medal”, “4”, “5”]
Explanation: The first three athletes got the top three highest scores, so they got “Gold Medal”, “Silver Medal” and “Bronze Medal”.
For the left two athletes, you just need to output their relative ranks according to their scores.
Note:
N is a positive integer and won’t exceed 10,000.
All the scores of athletes are guaranteed to be unique.

### Method

class Solution {
public:
vector<string> findRelativeRanks(vector<int>& nums) {
size_t len = nums.size();
vector<string> res(len, "");
vector<int> idx(len, 0);
for (int i = 0; i < len; ++i)
idx[i] = i;
argSort(nums, idx, 0, len - 1);
for (int i = 0; i < len; ++i)
res[idx[i]] = to_string(i+1);
for (int i = 0; i < len; ++i)
{
if (res[i] == "1")
res[i] = "Gold Medal";
else if (res[i] == "2")
res[i] = "Silver Medal";
else if (res[i] == "3")
res[i] = "Bronze Medal";
}
return res;

}

void argSort(vector<int> &nums, vector<int> &idx, int l, int r){
if (l >= r)
return;
int X = nums[l], ii = idx[l];
int i = l, j = r;
while (i < j)
{
while (i < j && nums[j] <= X)
--j;
if (i < j)
{
nums[i] = nums[j];
idx[i] = idx[j];
}
while (i < j && nums[i] > X)
++i;
if (i < j)
{
nums[j] = nums[i];
idx[j] = idx[i];
}
}
nums[i] = X;
idx[i] = ii;
argSort(nums, idx, l, i-1);
argSort(nums, idx, i+1, r);
}
};


## 461. Hanmming Distance

### Problem Description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 $\leqslant{x}$, y < $2^{31}$

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
↑   ↑


The above arrows point to positions where the corresponding bits are different.

### Method

class Solution {
public:
int hammingDistance(int x, int y) {
int res = 0;
int x_h = x, x_l = 0, y_h = y, y_l = 0;
while (x_h > 0 || y_h > 0)
{
x_l = x_h % 2;
x_h /= 2;
y_l = y_h % 2;
y_h /= 2;
if (x_l != y_l)
res++;
}
return res;
}
};


class Solution {
public:
int hammingDistance(int x, int y) {
int xxory = x^y;
int res = 0;
while (xxory)
{
res++;
xxory &= xxory - 1;
}
return res;
}
};


## 476. Number Complement

### Problem Description

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

### Method

class Solution {
public:
int findComplement(int num) {
return ~num & ((1 <<(int)log2(num))-1);
}
};


# Tree

## 419. Battleships in a Board

### Problem Description

You receive a valid board, made of only battleships or empty slots.
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 co>lumn), where N can be of any size.
At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:
X..X
…X
…X
In the above board there are 2 battleships.
Invalid Example:
…X
XXXX
…X
This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

### Method

cpp
class Solution {
public:
int countBattleships(vector>& board) {
if (board.empty())
return 0;
int m = board.size(), n = board[0].size();
int count = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
{
if (board[i][j] == ‘.’) continue;
if (i > 0 and board[i-1][j] == ‘X’) continue;
if (j > 0 and board[i][j-1] == ‘X’) continue;
++count;
}
return count;
}
};


## 513. Find Bottom Left Tree Value
### Problem Description
>Given a binary tree, find the leftmost value in the last row of the tree.
>
>Example 1:
>Input:
>
>    2
>   / \
>  1   3
>
>Output:
>1
>Example 2:
>Input:
>
>        1
>       / \
>      2   3
>     /   / \
>    4   5   6
>       /
>      7
>
>Output:
>7
>Note: You may assume the tree (i.e., the given root node) is not NULL.

### Method

cpp
class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

vector<int> rst({0, 0});

helper(root, 1, rst);

return rst[0];

}

// rst 第一元素存储当前最左值，第二个元素存储对应的深度

void helper(TreeNode* root, int deepth, vector<int>& rst)

{

if (deepth > rst[1])

{

rst[0] = root->val;

rst[1] = deepth;

}

if (root->left != NULL) helper(root->left, deepth+1, rst);

if (root->right != NULL) helper(root->right, deepth+1, rst);
}

};


# Array

## “LeetCode: 459 Repeated Substring Pattern”的几种解法

### 题目

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:
Input: "abab"

Output: True

Explanation: It's the substring "ab" twice.
Example 2:
Input: "aba"

Output: False
Example 3:
Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)


#### 解法一

bool method1(string str) {
size_t len = str.size();
for (int i = len / 2; i >=1; --i)
{
if (len % i == 0)
{
int p = len / i;
string newStr("");
string subStr = str.substr(0, i);
for (int j = 0; j < p; ++j)
newStr += subStr;
if (newStr == str)
return true;
}
}
return false;
}


#### 解法二

str是由某个子串重复构成的，那么将两个str拼接在一起，然后将拼接后的字符串去头去尾，仍然可以在这个字符串中找到str

bool method2(string str) {
string newStr = (str + str).substr(1, str.size()*2 - 2);
return newStr.find(str) != string::npos;
}


#### 解法三

vector<int> getNext(string str) {
int i = 0, j = 0;
vector<int> next(str.size(), 0);
next[0] = -1;
for (i = 1; i < str.size(); ++i)
{
j = next[i - 1];
while(str[i] != str[j + 1] && j >= 0)
j = next[j];
if (str[i] == str[j + 1])
next[i] = j  + 1;
else
next[i] = -1;
}
return next;
}

bool method3(string str) {
vector<int> next = getNext(str);
size_t len_str = str.size();
size_t len = next[len_str - 1] + 1;
return (len > 0) && (len_str%(len_str - len) == 0);

}


# [LeetCode]4:Median of Two Sorted Arrays

## 题目：

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0


Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


## 解题思路

1. 左边元素个数等于右边元素个数
2. 左边最大元素不大于右边最小元素

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if (m > n) return findMedianSortedArrays(nums2, nums1);
int i, j, imin = 0, imax = m, half = (m + n + 1) / 2;
while (imin <= imax) {
i = (imin & imax) + ((imin ^ imax) >> 1);
j = half - i;
if (i > 0 && j < n && nums1[i - 1] > nums2[j]) imax = i - 1;
else if (j > 0 && i < m && nums2[j - 1] > nums1[i]) imin = i + 1;
else break;
}
int num1;
if (!i) num1 = nums2[j - 1];
else if (!j) num1 = nums1[i - 1];
else num1 = max(nums1[i - 1], nums2[j - 1]);
if ((m + n) & 1) return num1;
int num2;
if (i == m) num2 = nums2[j];
else if (j == n) num2 = nums1[i];
else num2 = min(nums1[i], nums2[j]);
return (num1 + num2) / 2.0;
}
};

//下面这个版本[1, 3] [2]不通过，下次再修改

// class Solution {
// public:
//     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//         // 如果nums1的长度大于nums2的长度，将两者交换
//         if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
//         int m = nums1.size(), n = nums2.size();
//         // 如果m + n是偶数，j = (m + n) / 2 - i;否则j= (m + n + 1) / 2 - i;但是由于舍入规则，第一种情况和第二种情况一样
//         int i, j;
//         // i最终位置的上下边界
//         int m_left = 0, mid = (m + n + 1) / 2 ,m_right = m;
//         double left_max = 0, right_min = 0;
//         while (m_left <= m_right)
//         {
//             i = m_left + (m_right - m_left) / 2;//0
//             j = mid - i;//2
//             if (i < m && j < n && nums1[i] < nums2[j - 1])
//                 m_left = i + 1;
//             else if (i > 0 && i < m && nums1[i - 1] > nums2[j])
//                 m_right = i - 1;
//             else
//             {
//                 break;
//             }
//         }
//         // double left_max = 0;
//         if (!i) left_max = nums2[j - 1];
//         else if (!j) left_max = nums1[i - 1];
//         else left_max = max(nums1[i - 1], nums2[j - 1]);
//         if ((m + n) % 2)
//             return left_max;

//         // double right_min = 0;
//         if (i == m)
//             right_min = nums2[j];
//         else if (j == n)
//             right_min = nums1[i];
//         else
//             right_min = min(nums1[i], nums2[j]);
//         return (left_max + right_min) / 2.0;
//     }
// };


## Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)


Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.


### 解题思路

#### 状态定义

buy[i]:第i天处于已经买入股票的状态时最大资金
sell[i]:第i天处于已经卖出股票的状态时最大资金


#### 状态转移方程的定义

因为只能买卖一次，所以状态转移只能是

1. 第i-1天已经处于买入股票状态，第i天不买卖股票，维持在买入状态:

buy[i-1]->buy[i]

2. sell[i]—第i天已经处于卖出股票的状态

1. 第i-1天已经处于卖出股票状态，第i天不买卖，维持在卖出状态:

sell[i-1]->sell[i]

2. 第i-1天处于买入股票的状态，第i天将持有的股票卖出

buy[i-1]->sell[i]

sell[i]=max(buy[i-1]+prices[i], sell[i-1]);


### 实现

class Solution {
public:
int maxProfit(vector<int>& prices) {
for(int price: prices)
{
sell = max(buy + price, sell);
}
return sell;
}
};


leetcode Best Time to Buy and Sell Stock II leetcode Best Time to Buy and Sell Stock III leetcode Best Time to Buy and Sell Stock IV leetcode Best Time to Buy and Sell Stock with Cooldown

## Best Time To buy and sell stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

### 状态定义

buy[i]:第i天处于已经买入股票的状态时最大资金
sell[i]:第i天处于已经卖出股票的状态时最大资金


### 状态转移方程定义

因为只能买卖一次，所以状态转移只能是

1. 第i-1天已经处于买入股票状态，第i天不买卖股票，维持在买入状态:

buy[i-1]->buy[i]

2. 第i-1天已经处于卖出股票状态，第i天再次买入股票，进入持有股票状态

sell[i-1]->buy[i]

2. sell[i]—第i天已经处于卖出股票的状态

1. 第i-1天已经处于卖出股票状态，第i天不买卖，维持在卖出状态:

sell[i-1]->sell[i]

2. 第i-1天处于买入股票的状态，第i天将持有的股票卖出

buy[i-1]->sell[i]

sell[i]=max(buy[i-1]+prices[i], sell[i-1]);


### 实现

class Solution {
public:
int maxProfit(vector<int>& prices) {
for(int price: prices)
{
prev_sell = sell;
sell = max(buy + price, prev_sell);
}
return sell;
}
};


leetcode best Time Buy and SellStock I leetcode Best Time to Buy and Sell Stock III leetcode Best Time to Buy and Sell Stock IV leetcode Best Time to Buy and Sell Stock with Cooldown

## Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

## 解题思路

### 代码

class Solution {
public:
int maxProfit(vector<int>& prices) {
// 假设起始资金为0，
// 使用4个变量分别表示第一次买入后的资金,第一次卖出后的资金，第二次买入后的资金，第二次卖出后的资金
int buy1st = INT_MIN, sold1st = 0, buy2nd = INT_MIN, sold2nd = 0;
// 为了保证获利最大化，需要保证每次的资金量最大
for (int price : prices)
{
// 为了防止本次买入操作覆盖之前的买入操作，应该先计算卖出再计算买入；
// 同理，因为第二次的操作需要在第一次操作的基础上进行，应该先计算第二次的操作以防止覆盖
sold2nd = max(sold2nd, buy2nd + price);
sold1st = max(sold1st, buy1st + price);
}
return sold2nd;
}
};


leetcode best Time Buy and SellStock I leetcode Best Time to Buy and Sell Stock II leetcode Best Time to Buy and Sell Stock IV leetcode Best Time to Buy and Sell Stock with Cooldown

## Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

### 解题思路

class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (k < 1) return 0;

if (k > prices.size() / 2)
{
long rst = 0;
for (int i = 1; i < prices.size(); ++i)
if (prices[i] > prices[i - 1])
rst += prices[i] - prices[i - 1];
return rst;
}
for (int price : prices)
{
for (int i = buys.size() - 1; i > 0; --i)
{
solds[i] = max(solds[i], buys[i] + price);
}
solds[0] = max(solds[0], buys[0] + price);
}
return solds[k - 1];
}
};


leetcode best Time Buy and SellStock I leetcode Best Time to Buy and Sell Stock II leetcode Best Time to Buy and Sell Stock III leetcode Best Time to Buy and Sell Stock with Cooldown

## Best time to buy and sell stock with cooldown

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3


### 解题思路

#### 第一步对问题状态的定义：

buy[i]:第i天时为已经买入股票状态
sell[i]:第天时股票已经卖出股票状态
rest[i]:第i天的为休息状态，不进行买卖操作


#### 第二步对状态转移方程的定义：

第i天为买入状态有两种转移可能:

1. i-1天时已经是买入状态，第i天休息维持为买入状态:

buy[i-1]->buy[i]

2. 第i-1天为休息状态，第i天买入股票进入买入状态:

rest[i-1]->buy[i]

因为题目规定了卖出后必须冷却一天才能再次买入，所以没有第i-1天状态为卖出，在第i天再买入的情况

2. sell[i]—第i天为已经卖出状态

也有两种状态转移可能:

1. 第i-1天已经处于卖出状态，第i天休息维持为卖出状态

sell[i-1]->sell[i]

2. 第i-1天为买入状态，第i天将股票卖出而转移到卖出状态

buy[i-1]->sell[i]

3. rest[i]—第i天为休息状态

前一天是任何状态，第i天都可能转移到休息状态

buy[i-1]->rest[i]
sold[i-1]->rest[i]
rest[i-1]->rest[i]


buy[i] = max(rest[i-1]-prices[i], buy[i-1]);


#### 化简状态转移方程、缩小缓存大小

buy[i] = max(sell[i-2]-prices[i], buy[i-1]);


### 实现

class Solution {
public:
int maxProfit(vector<int>& prices){
for (int price:prices)
{
prev_sell = sell;
sell = max(prev_buy + price, sell);
}
return sell;
}
};


leetcode best Time Buy and SellStock I leetcode Best Time to Buy and Sell Stock II leetcode Best Time to Buy and Sell Stock III leetcode Best Time to Buy and Sell Stock IV

# Graph

## BFS Breadth firth traversal 广度优先遍历

1. 使用DFS获得图G的节点遍历结束时间序列f[u]
2. 计算$G^T$
3. f的降序计算DFS($G^T$)
4. 输出第三步得到的深度优先森林，即为强连通子图
#include <iostream>
#include <unordered_map>
#include <vector>
#include <list>
#include <queue>
#include <climits>

using namespace std;

class Graph {
private:
// 使用一个整数V存储图中节点数
int V;
// 邻接矩阵
public:
// 构造函数
Graph(int V);
// 添加边
void BFS(int s);
};

Graph::Graph(int V)
{
this->V = V;
}

{
}

void Graph::BFS(int s)
{
vector<int> color(V, -1), d(V, 0), pi(V, 0);
for (int i = 0; i < V; ++i)
{
d[i] = INT_MAX;
pi[i] = 0;
}
color[s] = 0;
d[s] = 0;
pi[s] = -1;
std::queue<int> queue;
queue.push(s);
while (!queue.empty())
{
int u = queue.front();
cout << u << endl;
queue.pop();
{
if (color[v] == -1)
{
color[v] = 0;
d[v] = d[u] + 1;
pi[v]  = u;
queue.push(v);
}
}
color[u] = 1;
}
}

int main()
{
Graph graph(4);
graph.BFS(2);
return 0;
}


## DFS

1. 如果遇到的节点是白色的，则当前边是树边
2. 如果遇到灰色节点，说明当前边是反向边
3. 如果遇到黑色节点，说明当前边是正向(d[u]<d[v])或交叉边(d[u]>d[v])

#include <iostream>
#include <vector>
#include <list>
#include <climits>

using namespace std;

class Graph
{
public:
Graph(int v);
void DFS();
void DFSHelper(int u);

private:
int V, time;
vector<int> color, d, f;
};

Graph::Graph(int v)
{
this->V = v;
color = vector<int>(v, -1);
d.resize(v);
f.resize(v);
}

{
}

void Graph::DFS()
{
time = 0;
for (int i = 0; i < V; ++i)
{
if (color[i] == -1)
DFSHelper(i);
}
}

void Graph::DFSHelper(int u)
{
color[u] = 0;
time++;
d[u] = time;
cout << u << ": " << time << endl;
if(color[v]==-1)
DFSHelper(v);
color[u] = 1;
f[u] = time+1;
}

int main()
{
Graph g(4);
g.DFS();
}


## 399. Evaluate Division

### Problem Description

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector> equations, vector& values, vector> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ [“a”, “b”], [“b”, “c”] ],
values = [2.0, 3.0],
queries = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].

## The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

a / b = 2.0, b / c = 3.0a/c, b/a, a/e, a/a

### Method

1. 第一种情况除号两边的数字都没有发现过
直接新建两个新节点，除数设为1，被除数设为公式的结果并将被除数的parent设为除数
2. 左边的符数字没有发现过
新建一个被除数节点，值设为除数的值乘公式结果
3. 右边的符号没有发现过
新建一个除数节点, 值设为被除数除以公式结果
4. 除数和被除数都被发现过
这种情况发生在除法链断开的情况下,比如遇到a/bc/d后又遇到a/d的情况,这时，要做的是将他们拼接起来，左边链的每个数值都按d->value * num / a->value缩放，然后将b和c连接起来。
class Solution {
// date: 2016-09-12     location: Santa Clara City Library
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
unordered_map<string, Node*> map;
vector<double> res;
for (int i = 0; i < equations.size(); i ++) {
string s1 = equations[i].first, s2 = equations[i].second;
if (map.count(s1) == 0 && map.count(s2) == 0) {
map[s1] = new Node();
map[s2] = new Node();
map[s1] -> value = values[i];
map[s2] -> value = 1;
map[s1] -> parent = map[s2];
} else if (map.count(s1) == 0) {
map[s1] = new Node();
map[s1] -> value = map[s2] -> value * values[i];
map[s1] -> parent = map[s2];
} else if (map.count(s2) == 0) {
map[s2] = new Node();
map[s2] -> value = map[s1] -> value / values[i];
map[s2] -> parent = map[s1];
} else {
unionNodes(map[s1], map[s2], values[i], map);
}
}

for (auto query : queries) {
if (map.count(query.first) == 0 || map.count(query.second) == 0 || findParent(map[query.first]) != findParent(map[query.second]))
res.push_back(-1);
else
res.push_back(map[query.first] -> value / map[query.second] -> value);
}
return res;
}

private:
struct Node {
Node* parent;
double value = 0.0;
Node()  {parent = this;}
};

void unionNodes(Node* node1, Node* node2, double num, unordered_map<string, Node*>& map) {
Node* parent1 = findParent(node1), *parent2 = findParent(node2);
double ratio = node2 -> value * num / node1 -> value;
for (auto it = map.begin(); it != map.end(); it ++)
if (findParent(it -> second) == parent1)
it -> second -> value *= ratio;
parent1 -> parent = parent2;
}

Node* findParent(Node* node) {
if (node -> parent == node)
return node;
node -> parent = findParent(node -> parent);
return node -> parent;
}
};


## 31>0

>

### Problem Description

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

   0
|
1
/ \
2   3


return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

0  1  2
\ | /
3
|
4
|
5


return [3, 4]

Hint:

How many MHTs can a graph have at most?

### Method

class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n == 1) return vector<int>({0});
this->V = n;
for (auto edge : edges)
{
}
vector<int> cur;
for (int i = 0; i < n; ++i)
cur.push_back(i);
while(!cur.empty())
{
vector<int> next;
for (int node : cur)
{
next.push_back(neighbor);
}
if (next.empty()) return cur;
swap(next, cur);
}
}
private:
int V;
};


# Stack

## 503. Next Greater Next I

### Problem Description

You are given two arrays (without duplicates) nums1 and >nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.
>

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
All elements in nums1 and nums2 are unique.

## The length of both nums1 and nums2 would not exceed 1000.

### Method

class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
if (findNums.empty() or nums.empty())
return vector<int>({});
stack<int> tmp;
unordered_map<int, int> nextmap;
tmp.push(nums[0]);

for (int i = 1; i < nums.size(); ++i)
{
while(tmp.top() < nums[i])
{
nextmap[tmp.top()] = nums[i];
tmp.pop();
if (tmp.empty())
break;
}
tmp.push(nums[i]);
}
while(!tmp.empty())
{
nextmap[tmp.top()] = -1;
tmp.pop();
}

vector<int> res;
for (int num : findNums)
res.push_back(nextmap[num]);

return res;
}
};


## Next Greater Number II

### Problem Description

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.
Note: The length of given array won't exceed 10000.


### Method

class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> next(n, -1);
stack<int> s; // index stack
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!s.empty() && nums[s.top()] < num) {
next[s.top()] = num;
s.pop();
}
if (i < n) s.push(i);
}
return next;
}
};