N Minimum Size Subarray Sum
（給一個(gè) n 個(gè)正數(shù)的數(shù)組和一個(gè)正整數(shù) s，找到和大于等于 s 的最小長(zhǎng)度的子數(shù)組，如果不存在，返回0）
舉例說(shuō)：給一個(gè)數(shù)組 [2,3,1,2,4,3] and s=7. 返回 [4,3]
(注意：子數(shù)組，是中間不能跳數(shù)的，只是整個(gè)數(shù)組的中間子集）

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if(nums.size()==0) return 0;
        int left=0; int sum=0; int min_value = INT_MAX;
        for(int i=0;i<nums.size();i++){
            sum =sum+ nums[i];
            while(sum>=s){
                min_value = min_value>(i-left+1)?(i-left+1):min_value;
                sum = sum - nums[left];
                left++;
            }
        }
        return min_value==INT_MAX?0:min_value;
    }
};

O 3Sum
（給一個(gè)n個(gè)整數(shù)的數(shù)組S，是否 S 里面有3個(gè)元素 a, b, c 使得 a + b+ｃ＝０，找到數(shù)組中所有唯一的三元組，使得其和為0）
這里我第一反應(yīng)還是先排序，然后，用夾逼的方法去找結(jié)果

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end()); // 排序是為了方便去重
        for(int i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1]) continue; // 如果之前同樣的數(shù)字已經(jīng)滿足了，那么現(xiàn)在這個(gè)數(shù)字就直接跳過(guò)
            int left = i+1;
            int right = nums.size()-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right]==0){
                    res.push_back(vector<int>{nums[i],nums[left],nums[right]});
                    while(nums[left]==nums[left+1]) left++; // 在內(nèi)循環(huán)中如果之前同樣的數(shù)字已經(jīng)滿足了，那么現(xiàn)在這個(gè)數(shù)字就直接跳過(guò)
while(nums[right]==nums[right-1]) right--; // 在內(nèi)循環(huán)中如果之前同樣的數(shù)字已經(jīng)滿足了，那么現(xiàn)在這個(gè)數(shù)字就直接跳過(guò)
left++,right--;
                } 
                else if(nums[i]+nums[left]+nums[right]<0) left++;
                else if(nums[i]+nums[left]+nums[right]>0) right--;
            }
        }
        return res;
    }
};

P Largest Number
（給一組正整數(shù)，排列他們中所有的數(shù)，使整個(gè)數(shù)組形成最大的數(shù)，用字符串顯示出來(lái)最后的結(jié)果）
（這個(gè)題其實(shí)和AMCAT上的題有點(diǎn)類(lèi)似）

class Solution {
public:
    bool static comp(string str1,string str2){
        return (str1+str2)>(str2+str1)?true:false;
    }

    string largestNumber(vector<int>& nums) {
        vector<string> vec;
        for(int i=0;i<nums.size();i++){
            vec.push_back(to_string(nums[i]));
        }
        sort(vec.begin(),vec.end(),comp);
        string res="";
        for(int i=0;i<vec.size();i++){
            res += vec[i];
        }
        if(res[0]=='0') return "0"; // 凡事總有意外，這就是意外。設(shè)計(jì) 2 個(gè) 0 在這個(gè)地方。
        return res;
    }
};

Q：Longest Substring Without Repeating Characters
（給一個(gè)字符串，找出最長(zhǎng)的不含重復(fù)元素的子串）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string str="";
        int left=0;
        int max_lens=0;
        for(int i=0;i<s.size();i++){
            if(str==""||str.find(s[i])==string::npos){
               str=str+s[i];
            }else if(str.find(s[i])!=string::npos){
               max_lens = max(max_lens,(int)str.size());
               str=str+s[i];
               left=str.find(s[i])+1;
               str=str.substr(left);
            } 
        }
        return max(max_lens,(int)str.size());
    }
};

R：Maximum Product Subarray
（在一個(gè)數(shù)組里面找到連續(xù)的一串子數(shù)組，使得他們相乘有最大的乘積）

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        int max =nums[0];
        int min =nums[0];
        for(int i =1;i<nums.size();i++){
            if(nums[i]>0){
                max = max*nums[i]>nums[i]?max*nums[i]:nums[i];
                min = min*nums[i]<nums[i]?min*nums[i]:nums[i];
                res = res>max?res:max;
            }else if(nums[i]==0){
                res = res>nums[i]?res:nums[i];
                if(i<nums.size()-1){
                    i++;
                    max = nums[i];
                    min = nums[i];
                    res = res>max?res:max;
                }else break;
            }else if(nums[i]<0){
                int tmp = max;
                max = nums[i]>min*nums[i]?nums[i]:min*nums[i];
                min = tmp*nums[i]<nums[i]?tmp*nums[i]:nums[i];
                res = res>max?res:max;
            }
        }
        return res;
    }
};

S：Wiggle Sort ii（這個(gè)題目超級(jí)的重要，有好幾個(gè)輪子在里面）
（給一個(gè)未排序的數(shù)組，以nums[0]<nums[1]>nums[2]<nums[3]的方式排列）
Example：
(1) Given nums = [1,5,1,1,6,4]，one possible answer is [1,4,1,5,1,6]
(2) Given nums = [1,3,2,2,3,1]，one possible answer is [2,3,1,3,1,2]

class Solution {
public:
    #define A(i) nums[(i*2+1)%(n|1)]
    
    void wiggleSort(vector<int>& nums) {
        int n =nums.size();
        auto mid = nums.begin()+n/2;
        nth_element(nums.begin(),mid,nums.end());（先根據(jù)中間值分成兩部分，左邊小，右邊大）
        int mid_val = *mid;
        int cur=0,left=0,right=n-1;
        
        while(left<=right){
            if(A(left)>mid_val){
                swap(A(left++),A(cur++));
            }else if(A(left)<mid_val){
                swap(A(left),A(right--));
            }else left++;
        }
    }
}
//  得到交叉的遍歷序列 (2*cur+1)%(n|1)
 #define A(cur) nums[(1+2*(cur)) % (n|1)] // 現(xiàn)在我知道通過(guò)這種方法可以得到135024的排序序列

5、字符串
A：Is Subsequence（子串問(wèn)題）
給一個(gè)字符串s 和 t，判斷是否s 是 t 的子串：
【注意 t 可能是一個(gè)非常長(zhǎng)的字符串，s 是一個(gè)比較短的字符串】
而子串是不改變字母的相對(duì)順序，但是從母串中減去若干個(gè)字母形參的串。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i=0,j=0;
        while(i<=j&&i<s.size()&&j<t.size()){
            while(j<t.size() && s[i]!=t[j]) j++;
            if(s[i]==t[j]){
                i++;
                j++;
            }
        }
        if(i!=s.size()&&j==t.size()) return false;
        else return true;
    }
};

B：Additive Number
一個(gè) Additive Number 是一個(gè)這樣的字符串，在字符串里面前面的數(shù)字可以相加組成后面的數(shù)字：
"112358" 是一個(gè) additive number，因?yàn)檫@些數(shù)字可以形成一個(gè)遞增的序列：1,1,2,3,5,8
"199100199" 也是一個(gè) additive number，因?yàn)檫@些數(shù)字可以形成一個(gè)遞增的序列：1,99,100,199
屬于 additive 的數(shù)字中，不能含有0 比如：1,2,03 or 1,02,3 都是無(wú)效的。

class Solution {
public:
    bool isAdditiveNumber(string num) {
      for(int i = 1; i <= num.size()/2; i++) {
       for(int j = 1; j <= (num.size()-i)/2; j++) {
         if (i >= 2 && num[0] == '0' || j >= 2 && num[i] == '0' || num[i+j] == '0') 
             continue;
         if (addNum(stol(num.substr(0,i)), stol(num.substr(i,j)), num.substr(i+j))) 
             return true;
        }
      }
      return false;
    }
    bool addNum(long num1, long num2, string num){
       if (num.size() > 1 && num[0] == '0') return false; // 這個(gè)也是邊界條件
       long sum = num1 + num2, numI = stol(num);
       // long len = static_cast<long>(log10(sum)) + 1; // 這個(gè)是求一個(gè)long型的數(shù)據(jù)的長(zhǎng)度
       long len = to_string(sum).size();
       if (numI == sum) return true;   // 這個(gè)是邊界條件
       if (numI < sum || sum != stol(num.substr(0, len))) return false; // 如果條件不符合，直接截?cái)?       else return addNum(num2, sum, num.substr(len)); // 依次遞歸，檢查是否符合要求
    } 
};

這里有幾個(gè)輪子：
a：stol：將字符串轉(zhuǎn)換為 long 型

C：Word Break
[ 給一個(gè)字符串s和一個(gè)詞典 dict，決定是否s能被拆分為 被空格分隔的一到多個(gè)序列 ]
[ 精確到每個(gè)數(shù)的下標(biāo) ]

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
            if(dict.size()==0) return false;
            vector<bool> dp(s.size()+1,false);
            dp[0]=true;  // 代表該位置之前的子串可以找的到！
            for(int i=1; i<=s.size(); i++)
            {
                for(int j=i-1; j>=0; j--)
                {
                    if(dp[j])  // 通過(guò)狀態(tài)矩陣，來(lái)判斷，如果 j 這個(gè)位置的字母及之前的字符所組合起來(lái)的字符串長(zhǎng)度可以被檢索，再匹配后面的字符串組合。
                    {
                        string word = s.substr(j,i-j);
                        if(dict.find(word)!= dict.end())
                        {
                            dp[i]=true;
                            break; //next i
                        }
                    }
                }
            }
            return dp[s.size()];
    }
};

D：Multiply Strings
（字符串相乘：Given two numbers represented as strings, return multiplication of the numbers as a string.）
（首先兩個(gè)數(shù)相乘，長(zhǎng)度最大為兩個(gè)數(shù)長(zhǎng)度相加，所以結(jié)果集的長(zhǎng)度初始化為兩個(gè)長(zhǎng)度的和）

class Solution {
public:
    string multiply(string num1, string num2) {
        string res = num1+num2;
        int next = 0;
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        // ---------------------------------
        for(int i=0;i<res.size();i++){
            int tmp=0;
            for(int j=0;j<num1.size()&&j<=i;j++)
                for(int k=0;k<num2.size()&&k<=i;k++){
                    if(j+k==i) tmp = tmp+(num1[j]-'0')*(num2[k]-'0');
                }
            res[i] = (tmp+next)%10+'0';
            next = (tmp+next)/10;
        }
        // ---------------------------------
        reverse(res.begin(),res.end());
        int index =0;
        for(;index<res.size();index++){
            if(res[index]!='0') break;
        }
        if(index == res.size()) return "0";
        return res.substr(index);
    }
};

6、二叉樹(shù)
A：給一棵二叉查找樹(shù)，寫(xiě)一個(gè)函數(shù) kthSmallest 來(lái)找到第k小的元素:
注意，如果一棵二叉查找樹(shù)被頻繁（修改/刪除），你需要找到第K小的元素
（這道題的老方法是用節(jié)點(diǎn)計(jì)數(shù)加中序遍歷，但是這道題的新方法是用棧來(lái)記錄中間值）
（這個(gè)題的難點(diǎn)在于棧的基本元素是指針，而不是指針對(duì)應(yīng)的值）

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* begin = root;
        while(begin){
            st.push(begin);
            begin=begin->left;
        }
        while(k-1){
            TreeNode* next = st.top()->right;
            st.pop();
            k--;
            while(next){
                st.push(next);
                next=next->left;
            }
        }
        int res = st.top()->val;
        return res;
    }
};

B：Flatten Binary Tree to Linked List
（給一棵二叉樹(shù)，將它原地壓扁成一棵單鏈表，這個(gè)地方是用前序遍歷的方式）
// 我暫時(shí)想到的方式是，在前序遍歷的過(guò)程中，用數(shù)組將中間的過(guò)程存起來(lái)，然后再輸出；紅色部分為前序遍歷的代碼，然后 vector 數(shù)組為記錄中間的值。

class Solution {
public:
    void flatten(TreeNode* root) {
        if(root){
        vector<TreeNode*> vec;
        stack<TreeNode*> st;  //先將 right 放進(jìn)去，再將 left 放進(jìn)去，保證
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            vec.push_back(node);
            if(node->right!=NULL) st.push(node->right);
            if(node->left!=NULL) st.push(node->left);
        }
        for(int i=0;i<vec.size()-1;i++){
            TreeNode* p;
            vec[i]->left=nullptr;
            vec[i]->right = vec[i+1];
        }
        }
    }
};

這種方法調(diào)用了額外的空間，肯定是不好的，下面是進(jìn)行原地的旋轉(zhuǎn)和遞歸調(diào)用：

class Solution {
public:
    TreeNode* help(TreeNode* root){
        // 指針的調(diào)用抓住兩個(gè)點(diǎn)，A：指針一改則全改；B：指針形態(tài)的判斷。
        if(!root->left&&!root->right) return root; // 根節(jié)點(diǎn)
        TreeNode* r = root->right;
        if(root->left){
            root->right = root->left;
            root->left = nullptr;
        }else{
            return help(root->right);
        } 
        TreeNode* next = help(root->right);
        if(r!=nullptr){
            next->right = r;
            return help(r);
        }
        return next;
    }
    void flatten(TreeNode* root) {
        if(!root) return;
        help(root);
    }
};

C：Insertion Sort List
（這里要注意，如果涉及到鏈表相關(guān)的題目，需要返回一個(gè)頭節(jié)點(diǎn)，最好重新設(shè)一個(gè)節(jié)點(diǎn)）

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head) return nullptr;
  // 相對(duì)來(lái)說(shuō)，最容易混淆的就是在最開(kāi)始的時(shí)候
        ListNode* begin = new ListNode(0);
        ListNode* rhead = begin;
 
        rhead->next=head;
        rhead = rhead->next;
        head = head->next;
        rhead->next = nullptr;
        
        while(head){
            if(head->val>=rhead->val){
                rhead->next = head;
                head=head->next;
                rhead=rhead->next;
                rhead->next = nullptr;
            }
            else{
                ListNode* find = begin;
                while(head->val>find->next->val) find=find->next;
                ListNode* tmp = head;
                head=head->next;
                tmp->next=find->next;
                find->next = tmp;
            }
        }
        return begin->next;
    }
};

D：Lowest Common Ancestor of a Binary Tree（這種題看上去挺簡(jiǎn)單，但是其實(shí)，應(yīng)用的場(chǎng)景很多）
// 對(duì)高度進(jìn)行降維，分別降到 左邊 和 右邊。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q) return root;  // 在最后判斷條件時(shí)，考慮 root 節(jié)點(diǎn).
        else{
            TreeNode * left = nullptr;
            TreeNode * right = nullptr; 
            if(root->left) left=lowestCommonAncestor(root->left,p,q);
            if(root->right) right=lowestCommonAncestor(root->right,p,q);
            return left&&right?root:left?left:right;  
            // 如果左邊和右邊子樹(shù)的返回值不為空，則返回root，如果左子樹(shù)和右子樹(shù)兩者只有一個(gè)，哪個(gè)存在就返回哪個(gè)。
        }
    }
};

E：Count Complete Tree Nodes
（給一棵完全二叉樹(shù)，統(tǒng)計(jì)完全二叉樹(shù)的結(jié)點(diǎn)）
（在一個(gè)完全二叉樹(shù)的每一層中，除了可能的最后一層外，其他的都是完全填滿的，而且最后一層(h 層)的結(jié)點(diǎn)都是盡可能左移的）
（它能擁有1到2^h個(gè)結(jié)點(diǎn)）最后求有多少個(gè)結(jié)點(diǎn)
（通過(guò)二分的方法來(lái)算就好了）
（父結(jié)點(diǎn)是第0層，依次往下數(shù)）

class Solution {
public:
    int help(TreeNode* root, int level){
        if(!root) return 0;
        while(root){
            if(root->right){
                root=root->right;
                level++;
            }else break; 
        }
        return level;
    }
    
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        else if(!root->left) return 1;
        else if(!root->right) return 2;
        int sum=0;
        while(root){
            if(!root->left&&!root->right){
                sum++;
                break;
            }
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            int num1 = help(left,1);
            int num2 = help(right,1);
            if(num1==num2){
                sum = sum + pow(2,num2);
                root = root->left;
            }else if(num1>num2){
                sum = sum + pow(2,num1);
                root = root->right;
            }
        }
        return sum;
    }
};

7、匹配題
A：Generate Parentheses
（給你 n 對(duì)括弧，寫(xiě)一個(gè)功能來(lái)產(chǎn)生所有括弧的合理組合）
（不管是怎么樣的組合，只要遵循先左再右的方式就可以了。同時(shí)把左右的數(shù)量保持一致就行）
（這種解題模式很重要）

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string s = "";
        if (n <= 0) return ret;
        recurParenthesis(n, n, ret, s);
    }

    void recurParenthesis(int leftNum, int rightNum, vector<string> &ret, string temp)
    {
        //leftNum means the number of open parenthesis available,rightNum means the number of close parenthesis available
        if (leftNum == 0 && rightNum == 0)
        {
            ret.push_back(temp);
            return;
        }

        if (leftNum > 0)
            recurParenthesis(leftNum-1, rightNum, ret, temp+'(');

        if (rightNum > 0)
        {
            if (leftNum < rightNum)
                recurParenthesis(leftNum, rightNum-1, ret, temp+')');
        }
    }
};

B：Combination Sum III
（給一個(gè)目標(biāo)值 n，然后找到k個(gè)數(shù)字的和為n的所有組合，所有數(shù)都是從[1 2 3 4 5 6 7 8 9]）
這個(gè)題我覺(jué)得和上面這個(gè)題的解決方法很相似了，因?yàn)槎际强梢杂蒙疃冗f歸的方式去做。
（有兩種解法，一種是先入后出法，入了之后，所有與它有關(guān)的解都應(yīng)該能夠被找出來(lái)，而出來(lái)了之后，的所有解將不包含它；第二種是標(biāo)記法，如果集合不大，就用一維的布爾數(shù)組進(jìn)行標(biāo)記凡是標(biāo)記過(guò)的，都不進(jìn)行遍歷，而沒(méi)有被標(biāo)記的元素，依次進(jìn)行遍歷。）

class Solution {
public:
    vector<int> rec{0,1,3,6,10,15,21,28,36,45};
    vector<vector<int>> res;
    void help(vector<int>& tmp, int k, int n,int index){
        if(n==0&&k>0) return;
        if(n==0&&k==0){
            res.push_back(tmp);
        } 
        for(int i=index+1;i<=9;i++){
            if(i>n) break;
            else{
                tmp.push_back(i);
                help(tmp,k-1,n-i,i);
                tmp.pop_back();
            } 
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        if(n<rec[k]||n>45) return res;
        if(n==rec[k]){
            vector<int> tmp;
            for(int i=1;i<=k;i++) tmp.push_back(i);
            res.push_back(tmp);
            return res;
        }else{
            vector<int> tmp;
            for(int i=1;i<=9;i++){
                if(i>n) break;
                if(i<=n){
                    tmp.push_back(i);
                    help(tmp,k-1,n-i,i);
                    tmp.pop_back();
                }
            }
            return res;
        }
    }
};

void help(vector<vector<int>>& res, vector<int>& cur, int start) {
    if (start == cur.size()) {
        res.push_back(cur);
    } else {
        for (int i = start; i < cur.size(); i++) {
            swap(cur[start], cur[i]);
            help(res, cur, start + 1);
            swap(cur[start], cur[i]);
        }
    }
}
?
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    help(res, nums, 0);
    return res;
}

Combinations
（Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.）
（這種模式比較重要，很多的題目，只要通過(guò)這種模式，都能夠做出來(lái)）

class Solution {
public:
    vector<vector<int>> res;
    int size=0;
    void help(vector<int>& cur, int n, int start) {
        if (cur.size() == size) {
            res.push_back(cur);
        } else {
            for (int i = start; i <=n; i++) {
                cur.push_back(i);
                help(cur,n, i + 1);
                cur.pop_back();
            }
        }
    }
    vector<vector<int>> combine(int n, int k) {
        size = k;
        vector<int> nums;
        help(nums,n,1);
        return res;
    }
};

C：Single Number ii
（這個(gè)題目，考的比較多，因?yàn)閿?shù)值題是最容易考的，一組數(shù)，里面除了一個(gè)數(shù)只出現(xiàn)了1次以外，其他的數(shù)都各自出現(xiàn)了3次，找出這個(gè)數(shù)）。
這道題因?yàn)椴荒苡脭?shù)組

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        for(int i=0;i<32;i++){
            int mask =1<<i;
            int count=0;
            for(auto n:nums) {
                if(n&mask) count++;
            }
            if(count%3) res|=mask;
        }
        return res;
    }
};

D：Search Insert Position
[Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.]
（二分查找的唯一準(zhǔn)則，就是進(jìn)行劃分時(shí)，一定是將真正的答案留下，而不是被劃走了）

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //方法1：直接遍歷
        // int i=0;
        // for(i=0;i<nums.size();i++) if(nums[i]>=target) break;
        // return i;
        //方法2：二分查找
        if (target > nums.back()) return nums.size();
        int left=0,right=nums.size()-1; // 注意：left在范圍內(nèi)，right在范圍外
        while(left<right){
            int mid = left+(right-left)/2; 
            if(nums[mid]==target) return mid;
            else if(nums[mid]<target) left=mid+1;
            else if(nums[mid]>target) right=mid;
        }
        return left;
    }
};

E：Maximal Square
（給予一個(gè)2D的二進(jìn)制矩陣，填滿0和1，找到包含1的最大的正方形，然后返回它的面積）

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size()==0) return 0;
        int row_num = matrix.size();
        int col_num = matrix[0].size();
        int max_value=0;
        vector<int> record(col_num,0);
        for(int i=0;i<col_num;i++) {record[i]=matrix[0][i]=='0'?0:1; max_value=max(max_value,matrix[0][i]-'0');};
        for(int i=1;i<row_num;i++){
            int tmp =record[0];
            record[0]= matrix[i][0]-'0';
            for(int j=1;j<col_num;j++){
                int mmm = record[j];
                if(matrix[i][j]=='1'){
                    record[j]=min(min(record[j],record[j-1]),tmp)+1; 
                    max_value=max(max_value,record[j]);
                }else record[j]=0;
                tmp=mmm;
            }
        }
        return max_value*max_value;
    }
};

8、新題型
A：Flatten Nested List iterator
這種題應(yīng)該在很多應(yīng)用場(chǎng)景中都會(huì)出現(xiàn)，給一個(gè)嵌套的數(shù)字的列表，用一個(gè)迭代器來(lái)壓扁它：
其中，每一個(gè)元素要么是一個(gè)整數(shù)，要么是一個(gè)嵌套著整數(shù)的列表.
Example 1：Given the list [[1,1],2,[1,1]]. 最后變?yōu)?[1,1,2,1,1]
Example 2：Given the list [1,[4,[6]]]. 最后變?yōu)?[1,[4,[6]]]

queue<int> res;    
void help(vector<NestedInteger> &nestedList){
    for(auto n:nestedList){
        if(n.isInteger()) res.push(n.getInteger());
        else help(n.getList());
    }
}

B：Subsets ii （求子集的題，應(yīng)該還是比較容易出）
（給一個(gè)可能包含重復(fù)整數(shù)的集合，返回它不包含重復(fù)子集的結(jié)合）
If nums = [1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
（思考方式：不能包含重復(fù)子集，那么也就是說(shuō)如果有幾個(gè)相同的數(shù)重復(fù)出現(xiàn)，那么需要跳過(guò)）

class Solution {
public:
    vector<vector<int>> res;
    void help(vector<int>& nums,int index,vector<int> tmp){
        for(int i=index;i<nums.size();i++){
            tmp.push_back(nums[i]);
            res.push_back(tmp);
            help(nums,i+1,tmp);
            tmp.pop_back();
            while(i<nums.size()-1&&nums[i]==nums[i+1]) i++;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end()); // sort is necessary !!
        vector<int> tmp;
        res.push_back(tmp); 
        help(nums,0,tmp);
        return res;
    }
};

C：Range Sum Query - Mutable
（這是一道設(shè)計(jì)題，設(shè)計(jì)功能的實(shí)現(xiàn)方式，雖然有很多種實(shí)現(xiàn)的方式，但是如果考慮到性能，就沒(méi)法實(shí)現(xiàn)）
（給一個(gè)整數(shù)數(shù)組，返回下標(biāo)從 i 到 j 的所有元素的和）
update(i,val) 函數(shù)將下標(biāo)為 i 的元素修改為 val.

D：Add and Search Word - Data structure design（這個(gè)題要用到前綴樹(shù)）
（這也是一道設(shè)計(jì)題，支持兩個(gè)功能：addWord（word）；search（word）；）
void addWord(word)
bool search(word)
支持通配符"."，這個(gè)通配符可以代表任何一個(gè)字母；這里與字母相關(guān)的，是前綴樹(shù)
前綴樹(shù)有個(gè)基本的節(jié)點(diǎn)：TrieNode

class TrieNode {
public:
     bool isKey;   // 這個(gè)key的意思是，這個(gè)是根節(jié)點(diǎn)。
     TrieNode* children[26];
         TrieNode(): isKey(false) {
            memset(children, NULL, sizeof(TrieNode*) * 26);  //給數(shù)組分配內(nèi)存
         }
   };
class WordDictionary {
public:
    WordDictionary() {
        root = new TrieNode();
    }
    // Adds a word into the data structure.
    （每加入一個(gè)單詞，就建立一條索引，或者復(fù)用一條索引）
    void addWord(string word) {
        TrieNode* run = root;
        for (char c : word) {
            if (!(run -> children[c - 'a'])) 
                run -> children[c - 'a'] = new TrieNode();
            run = run -> children[c - 'a'];
        }
        run -> isKey = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return query(word.c_str(), root); //一個(gè)string 怎么轉(zhuǎn) char*數(shù)組
    }
private:
    TrieNode* root;
    bool query(const char* word, TrieNode* node) {
        TrieNode* run = node;
        for (int i = 0; word[i]; i++) {
            if (run && word[i] != '.')
                run = run -> children[word[i] - 'a'];
            else if (run && word[i] == '.') { 
                TrieNode* tmp = run;
                for (int j = 0; j < 26; j++) {
                    run = tmp -> children[j];
                    if (query(word + i + 1, run)) return true;
                }
            }else break;
        }
        return run && run -> isKey; 
    }
};

E：Basic Calculator ii
（實(shí)現(xiàn)一個(gè)基本的計(jì)算器來(lái)計(jì)算一個(gè)簡(jiǎn)單的字符串表達(dá)式）
（這個(gè)字符串表達(dá)式中只包含非負(fù)的整數(shù)，+、-、*、/ 運(yùn)算符，以及空格）

class Solution {
public:
    stack<string> rec;
    void help(int& num){
        if(rec.size()==0){
              string str = to_string(num);
              rec.push(str);            
        }else if(rec.top()=="+"){
              rec.pop();
              string str = to_string(num);
              rec.push(str);
        }else if(rec.top()=="-"){
              rec.pop();
              string str = to_string(-num);
              rec.push(str);
        }else if(rec.top()=="*"){
              rec.pop();
              int num1 = stoi(rec.top());
              rec.pop();
              string str = to_string(num*num1);
              rec.push(str);
        }else if(rec.top()=="/"){
              rec.pop();
              int num1 = stoi(rec.top());
              rec.pop();
              string str = to_string(num1/num);
              rec.push(str);
        }
        num=0;
    }
    int calculate(string s) {
        int num=0;
        for(int i=0;i<s.size();i++){
            if(s[i]!=' '){
                if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){
                    help(num);
                    string tmp ="";
                    tmp = tmp +s[i];
                    rec.push(tmp);
                }else{
                    int n = s[i]-'0';
                    num = num*10+n;
                }   
            }
        }
        help(num);
        while(rec.size()){
            num+=stoi(rec.top());
            rec.pop();
        }
        return num;
    }
};

9、數(shù)學(xué)推理題
A：給你一個(gè)單項(xiàng)鏈表，然后判斷是否有環(huán)，如果有環(huán)，返回環(huán)的起點(diǎn)：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head) return nullptr;
        ListNode* slow = head->next;
        if(!slow) return nullptr;
        ListNode* fast = head->next->next;
        while(slow){
            if(fast==nullptr|| fast->next==nullptr) return NULL;
            else if(fast==slow) break;
            else{
                fast = fast->next->next;
                slow = slow->next;
            }
        }
        fast = head;
        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};

B：Water and Jug Problem（有兩個(gè)不同容量的壺，然后要倒出指定容量的水出來(lái)）
**Example 1: **
Input: x = 3, y = 5, z = 4
Output: True
Example 2:
Input: x = 2, y = 6, z = 5
Output: False

兩個(gè)瓶子可能量出的水是兩個(gè)瓶子容量最大公約數(shù)的倍數(shù)。所以只要判斷z是否可以被x，y的最大公約數(shù)整除即可。
造輪子：求兩個(gè)數(shù)的公約數(shù)

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(z>x+y) return false;
        if(z==0) return true;
        int big = max(x,y);
        int small = min(x,y);
        if(big%small==0&&z%small==0) return true;
        else{

            while(small>=1){
                int tmp =big;
                big = max(small,big-small);
                small = min(small,tmp-small);
                if(big%small==0) break;
            }

            if(z%small==0) return true;
        }
        return false;
    }
};

C：Decode Ways
（一條包含從"A~Z" 字母的信息，通過(guò)以下的 mapping 方式進(jìn)行編碼）
'A' -> 1
'B' -> 2
...
'Z' -> 26
（給你一個(gè)字符串，來(lái)判斷有多少種編碼方式）
（主要是對(duì)0的處理，以及）

// decode ways
class Solution {
public:
    int numDecodings(string s) {
        if (s.length() == 0) return 0;
        int n = s.length();
        vector<int> dp(n + 1, 0);
        dp[0] = 1; //  dp[0] = 1 is a trap
        dp[1] = 1;
        if(s[0]=='0') return 0;

        for (int i = 2; i <= n; i++) {
            if (s[i-1] != '0') 
                dp[i] += dp[i-1];

            if (stoi( s.substr(i-2, 2) ) >= 10 && stoi( s.substr(i-2, 2) ) <= 26)
                dp[i] += dp[i-2];
        }
        return dp[n];
    }
};

D：Permutation Sequence
（The set [1,2,3,…,n] contains a total of n! unique permutations.）
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3)：
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

class Solution {
public:
    string getPermutation(int n, int k) {
        int total = 1;
        string res="";
        vector<int> nums(n,0);
        for(int i=1;i<=n;i++){
            total=total*i;  
            nums[i-1]=i;
        } 
        k=k-1; // 因?yàn)楸旧砭退阋淮?，所以，將k-1，記做變化了k次
        for(int i=n;i>=1;i--){
            total = total/i;
            char c = '0'+nums[k/total];
            res=res+c;
            nums.erase(nums.begin()+k/total);  // 數(shù)組erase的時(shí)候，參數(shù)是迭代器
            k = k%total;
        }
        return res;
    }
};

10、動(dòng)態(tài)規(guī)劃題型

A：Triangle
【給一個(gè)三角形，找到里面從top到bottom和最小的路徑，每一步你都可以移動(dòng)到下一行的相鄰的數(shù)字】

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int row_num = triangle.size();
        vector<int> res = triangle[row_num-1];
        for(int i=row_num-2;i>=0;i--){
            int col_num = triangle[i].size();
            for(int j=0;j<col_num;j++){
                res[j]=min(triangle[i][j]+res[j],triangle[i][j]+res[j+1]);
            }
        }
        return res[0];
    }
};

B：Jump Game
【給一組正整數(shù)的數(shù)組，你被初始化于一個(gè)數(shù)組頭節(jié)點(diǎn)的位置，數(shù)組中的每一個(gè)元素都代表你能跳躍的最大的距離，判斷是否能從頭節(jié)點(diǎn)到末節(jié)點(diǎn)】
方法就是只要判斷出能到的位置的最大值大于等于最后一個(gè)數(shù)就行了

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int length=nums[0];
        for(int i=0;i<=length;i++){
            length = i+nums[i]>length?i+nums[i]:length;
            if(length>=nums.size()) return true;
        }
        if(length<nums.size()-1) return false;
        else return true;
    }
};

C：Gas Station
（環(huán)形的數(shù)據(jù)結(jié)構(gòu)，總是相對(duì)比較難一點(diǎn)）
[圍繞著一個(gè)圓形的路徑，有N個(gè)加油站，每個(gè)加油站的油的量為gas[i]，你有一個(gè)無(wú)限制油量大小的油桶，并且從站i 到 下一個(gè)站i+1，需要花費(fèi)cost[i]，你以空油量從任何一個(gè)站加油出發(fā)，問(wèn)能否圍繞所有油站一次]
(首先，如果能繞一個(gè)圈，那么總存量為正數(shù)，否者為負(fù)數(shù)，在為正數(shù)的情況下，要去找那個(gè)起點(diǎn)，那么，就從0開(kāi)始，然后，找到單段存量為負(fù)數(shù)的位置，從下一個(gè)開(kāi)始就好。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0;
        int index =-1;
        for(int i=0,sum=0;i<gas.size();i++){
            sum += gas[i]-cost[i];   // 單段的油量余量
            total = total+gas[i]-cost[i];    // 從全局看所有的油量
            if(sum<0){
                index = i;
                sum=0;
            }
        }
        return total>=0?index+1:-1;
    }
};

D：Coin Change [這個(gè)題目比較重要]
[給你不同面額的足量硬幣以及一個(gè)錢(qián)的總額，寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算你需要的最少的硬幣來(lái)構(gòu)成指定的面額，如果該面額數(shù)不能被任何面額的硬幣構(gòu)成，返回-1]
Example 1:
coins = [1,2,5], amount = 11
return 3（11 = 5+5+1）
Example 2:
coins = [2], amount = 3
return -1

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
         vector<int> vec(amount+1,INT_MAX);
         vec[0] = 0;
         for(int i=0;i<amount+1;i++)
            for(int j=0;j<coins.size();j++){
                if(vec[i]!=INT_MAX) if(i+coins[j]<=amount) vec[i+coins[j]]=min(vec[i+coins[j]],vec[i]+1);
            }
        return vec[amount]<INT_MAX?vec[amount]:-1;
    }
};

E：Decode Ways
（一條包含從"A~Z" 字母的信息，通過(guò)以下的 mapping 方式進(jìn)行編碼）
（這個(gè)題，最麻煩的是，對(duì)0的處理）
'A' -> 1
'B' -> 2
...
'Z' -> 26
（給你一個(gè)字符串，來(lái)判斷有多少種編碼方式）

class Solution {
public:
    int numDecodings(string s) {
        if (s.length() == 0) return 0;
        int n = s.length();
        vector<int> dp(n + 1, 0);
        dp[0] = 1; //  dp[0] = 1 is a trap
        dp[1] = 1;
        if(s[0]=='0') return 0;

        for (int i = 2; i <= n; i++) {
            if (s[i-1] != '0')  dp[i] += dp[i-1];
            if (stoi( s.substr(i-2, 2) ) >= 10 && stoi( s.substr(i-2, 2) ) <= 26)  dp[i] += dp[i-2];
        }
        return dp[n];
    }
};

F：Word Ladder
（給兩個(gè)單詞（begin_word to end_word）和一個(gè)字典詞序列，找到從起點(diǎn)到終點(diǎn)轉(zhuǎn)換的最短路徑，每次轉(zhuǎn)換一個(gè)單詞）
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
（這里 unordered_set 用的是哈希表，所以用inset都是ok的）

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        unordered_set<string> beg_set,end_set,*set1,*set2;
        int res=1;
        beg_set.insert(beginWord);
        end_set.insert(endWord);
        while(!beg_set.empty()&&!end_set.empty()){  //  兩個(gè)集合都不是空的的時(shí)候
            if(beg_set.size()<end_set.size())    {
                set1 = &beg_set;
                set2 = &end_set;
            }else{
                set2 = &beg_set;
                set1 = &end_set;
            }
            res++;   //  內(nèi)部加1，忘了加
            unordered_set<string> tmp;
            //  針對(duì)beg_set 中的每一個(gè)單詞，改變單詞的每一個(gè)字母，然后去end_set里面去找，如果找到了，就說(shuō)明直接可以結(jié)束了，如果沒(méi)有找到，那么去wordList里面找，找到后，再加入到臨時(shí)的集合中。
            for(auto i=set1->begin();i!=set1->end();i++){
                string tmp_str =*i;
                for(int j = 0;j<tmp_str.size();j++){
                    char tmp_char = tmp_str[j];
                    for(int k=0;k<26;k++){
                        tmp_str[j]='a'+k;
                        if(set2->find(tmp_str)!=set2->end()){
                            return res;  
                        }else if(wordList.find(tmp_str)!=wordList.end()){
                            auto itr = wordList.find(tmp_str);
                            tmp.insert(tmp_str);  
                            wordList.erase(itr);   // 原字符集合刪除忘了刪。
                        } 
                    }
                    tmp_str[j]=tmp_char; 
                }
            }
            swap(tmp,*set1); // 字符集交換，忘了寫(xiě)
        }
        return 0;
    }
};