N Minimum Size Subarray Sum
（給一個 n 個正數(shù)的數(shù)組和一個正整數(shù) s，找到和大于等于 s 的最小長度的子數(shù)組，如果不存在，返回0）
舉例說：給一個數(shù)組 [2,3,1,2,4,3] and s=7. 返回 [4,3]
(注意：子數(shù)組征峦，是中間不能跳數(shù)的，只是整個數(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
（給一個n個整數(shù)的數(shù)組S消请，是否 S 里面有3個元素 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)在這個數(shù)字就直接跳過
            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)在這個數(shù)字就直接跳過
while(nums[right]==nums[right-1]) right--; // 在內(nèi)循環(huán)中如果之前同樣的數(shù)字已經(jīng)滿足了针饥，那么現(xiàn)在這個數(shù)字就直接跳過
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ù)需频，使整個數(shù)組形成最大的數(shù)丁眼，用字符串顯示出來最后的結(jié)果）
（這個題其實(shí)和AMCAT上的題有點(diǎn)類似）

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 個 0 在這個地方苞七。
        return res;
    }
};

Q：Longest Substring Without Repeating Characters
（給一個字符串，找出最長的不含重復(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
（在一個數(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（這個題目超級的重要蹂风，有好幾個輪子在里面）
（給一個未排序的數(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)在我知道通過這種方法可以得到135024的排序序列

5礁阁、字符串
A：Is Subsequence（子串問題）
給一個字符串s 和 t，判斷是否s 是 t 的子串：
【注意 t 可能是一個非常長的字符串族奢，s 是一個比較短的字符串】
而子串是不改變字母的相對順序姥闭，但是從母串中減去若干個字母形參的串。

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
一個 Additive Number 是一個這樣的字符串越走，在字符串里面前面的數(shù)字可以相加組成后面的數(shù)字：
"112358" 是一個 additive number棚品，因?yàn)檫@些數(shù)字可以形成一個遞增的序列：1,1,2,3,5,8
"199100199" 也是一個 additive number靠欢，因?yàn)檫@些數(shù)字可以形成一個遞增的序列：1,99,100,199
屬于 additive 的數(shù)字中，不能含有0 比如：1,2,03 or 1,02,3 都是無效的铜跑。

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; // 這個也是邊界條件
       long sum = num1 + num2, numI = stol(num);
       // long len = static_cast<long>(log10(sum)) + 1; // 這個是求一個long型的數(shù)據(jù)的長度
       long len = to_string(sum).size();
       if (numI == sum) return true;   // 這個是邊界條件
       if (numI < sum || sum != stol(num.substr(0, len))) return false; // 如果條件不符合门怪，直接截?cái)?       else return addNum(num2, sum, num.substr(len)); // 依次遞歸，檢查是否符合要求
    } 
};

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

C：Word Break
[ 給一個字符串s和一個詞典 dict锅纺，決定是否s能被拆分為 被空格分隔的一到多個序列 ]
[ 精確到每個數(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])  // 通過狀態(tài)矩陣，來判斷囤锉，如果 j 這個位置的字母及之前的字符所組合起來的字符串長度可以被檢索坦弟，再匹配后面的字符串組合。
                    {
                        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.）
（首先兩個數(shù)相乘官地，長度最大為兩個數(shù)長度相加酿傍，所以結(jié)果集的長度初始化為兩個長度的和）

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、二叉樹
A：給一棵二叉查找樹驱入，寫一個函數(shù) kthSmallest 來找到第k小的元素:
注意赤炒，如果一棵二叉查找樹被頻繁（修改/刪除），你需要找到第K小的元素
（這道題的老方法是用節(jié)點(diǎn)計(jì)數(shù)加中序遍歷亏较，但是這道題的新方法是用棧來記錄中間值）
（這個題的難點(diǎn)在于棧的基本元素是指針莺褒，而不是指針對應(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ù)組將中間的過程存起來旺罢，然后再輸出旷余；紅色部分為前序遍歷的代碼，然后 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)用抓住兩個點(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)的題目图仓，需要返回一個頭節(jié)點(diǎn)罐盔，最好重新設(shè)一個節(jié)點(diǎn)）

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head) return nullptr;
  // 相對來說救崔，最容易混淆的就是在最開始的時候
        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（這種題看上去挺簡單惶看，但是其實(shí)捏顺，應(yīng)用的場景很多）
// 對高度進(jìn)行降維，分別降到 左邊 和 右邊纬黎。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q) return root;  // 在最后判斷條件時幅骄，考慮 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;  
            // 如果左邊和右邊子樹的返回值不為空，則返回root本今，如果左子樹和右子樹兩者只有一個拆座，哪個存在就返回哪個。
        }
    }
};

E：Count Complete Tree Nodes
（給一棵完全二叉樹诈泼，統(tǒng)計(jì)完全二叉樹的結(jié)點(diǎn)）
（在一個完全二叉樹的每一層中懂拾，除了可能的最后一層外煤禽，其他的都是完全填滿的铐达，而且最后一層(h 層)的結(jié)點(diǎn)都是盡可能左移的）
（它能擁有1到2^h個結(jié)點(diǎn)）最后求有多少個結(jié)點(diǎn)
（通過二分的方法來算就好了）
（父結(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 對括弧瓮孙，寫一個功能來產(chǎn)生所有括弧的合理組合）
（不管是怎么樣的組合，只要遵循先左再右的方式就可以了选脊。同時把左右的數(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
（給一個目標(biāo)值 n杭抠，然后找到k個數(shù)字的和為n的所有組合，所有數(shù)都是從[1 2 3 4 5 6 7 8 9]）
這個題我覺得和上面這個題的解決方法很相似了恳啥，因?yàn)槎际强梢杂蒙疃冗f歸的方式去做偏灿。
（有兩種解法，一種是先入后出法钝的，入了之后翁垂，所有與它有關(guān)的解都應(yīng)該能夠被找出來，而出來了之后硝桩，的所有解將不包含它沿猜；第二種是標(biāo)記法，如果集合不大碗脊，就用一維的布爾數(shù)組進(jìn)行標(biāo)記凡是標(biāo)記過的啼肩，都不進(jìn)行遍歷，而沒有被標(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.）
（這種模式比較重要，很多的題目矢劲，只要通過這種模式赦拘，都能夠做出來）

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
（這個題目，考的比較多卧须，因?yàn)閿?shù)值題是最容易考的另绩，一組數(shù)儒陨，里面除了一個數(shù)只出現(xiàn)了1次以外，其他的數(shù)都各自出現(xiàn)了3次笋籽，找出這個數(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)行劃分時车海，一定是將真正的答案留下笛园，而不是被劃走了）

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
（給予一個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)用場景中都會出現(xiàn)棵红，給一個嵌套的數(shù)字的列表，用一個迭代器來壓扁它：
其中咧栗，每一個元素要么是一個整數(shù)逆甜，要么是一個嵌套著整數(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)該還是比較容易出）
（給一個可能包含重復(fù)整數(shù)的集合致板，返回它不包含重復(fù)子集的結(jié)合）
If nums = [1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
（思考方式：不能包含重復(fù)子集交煞，那么也就是說如果有幾個相同的數(shù)重復(fù)出現(xiàn)，那么需要跳過）

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)的方式，但是如果考慮到性能萝挤，就沒法實(shí)現(xiàn)）
（給一個整數(shù)數(shù)組御毅，返回下標(biāo)從 i 到 j 的所有元素的和）
update(i,val) 函數(shù)將下標(biāo)為 i 的元素修改為 val.

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

class TrieNode {
public:
     bool isKey;   // 這個key的意思是，這個是根節(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.
    （每加入一個單詞晚凿，就建立一條索引，或者復(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); //一個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)一個基本的計(jì)算器來計(jì)算一個簡單的字符串表達(dá)式）
（這個字符串表達(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：給你一個單項(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（有兩個不同容量的壺，然后要倒出指定容量的水出來）
**Example 1: **
Input: x = 3, y = 5, z = 4
Output: True
Example 2:
Input: x = 2, y = 6, z = 5
Output: False

兩個瓶子可能量出的水是兩個瓶子容量最大公約數(shù)的倍數(shù)谢揪。所以只要判斷z是否可以被x蕉陋，y的最大公約數(shù)整除即可。
造輪子：求兩個數(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" 字母的信息拨扶，通過以下的 mapping 方式進(jìn)行編碼）
'A' -> 1
'B' -> 2
...
'Z' -> 26
（給你一個字符串凳鬓，來判斷有多少種編碼方式）
（主要是對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)楸旧砭退阋淮位济瘢运蹙伲瑢-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ù)是迭代器
            k = k%total;
        }
        return res;
    }
};

10蚁孔、動態(tài)規(guī)劃題型

A：Triangle
【給一個三角形，找到里面從top到bottom和最小的路徑惋嚎，每一步你都可以移動到下一行的相鄰的數(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ù)組，你被初始化于一個數(shù)組頭節(jié)點(diǎn)的位置站刑，數(shù)組中的每一個元素都代表你能跳躍的最大的距離另伍，判斷是否能從頭節(jié)點(diǎn)到末節(jié)點(diǎn)】
方法就是只要判斷出能到的位置的最大值大于等于最后一個數(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)，總是相對比較難一點(diǎn)）
[圍繞著一個圓形的路徑绞旅，有N個加油站摆尝，每個加油站的油的量為gas[i]，你有一個無限制油量大小的油桶因悲，并且從站i 到 下一個站i+1堕汞，需要花費(fèi)cost[i]，你以空油量從任何一個站加油出發(fā)晃琳，問能否圍繞所有油站一次]
(首先讯检，如果能繞一個圈，那么總存量為正數(shù)卫旱，否者為負(fù)數(shù)人灼，在為正數(shù)的情況下，要去找那個起點(diǎn)顾翼，那么投放，就從0開始，然后适贸，找到單段存量為負(fù)數(shù)的位置灸芳，從下一個開始就好涝桅。

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 [這個題目比較重要]
[給你不同面額的足量硬幣以及一個錢的總額，寫一個函數(shù)來計(jì)算你需要的最少的硬幣來構(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" 字母的信息，通過以下的 mapping 方式進(jìn)行編碼）
（這個題误阻，最麻煩的是债蜜，對0的處理）
'A' -> 1
'B' -> 2
...
'Z' -> 26
（給你一個字符串，來判斷有多少種編碼方式）

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
（給兩個單詞（begin_word to end_word）和一個字典詞序列究反，找到從起點(diǎn)到終點(diǎn)轉(zhuǎn)換的最短路徑寻定，每次轉(zhuǎn)換一個單詞）
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()){  //  兩個集合都不是空的的時候
            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;
            //  針對beg_set 中的每一個單詞狼速，改變單詞的每一個字母，然后去end_set里面去找卦停，如果找到了向胡，就說明直接可以結(jié)束了，如果沒有找到惊完，那么去wordList里面找僵芹，找到后，再加入到臨時的集合中小槐。
            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); // 字符集交換，忘了寫
        }
        return 0;
    }
};