N Minimum Size Subarray Sum
（给一个 n 个正数的数组和一个正整数 s，找到和大于等于 s 的最小长度的子数组，如果不存在，返回0）
举例说：给一个数组 [2,3,1,2,4,3] and s=7. 返回 [4,3]
(注意：子数组，是中间不能跳数的，只是整个数组的中间子集）

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个整数的数组S，是否 S 里面有3个元素 a, b, c 使得 a + b+ｃ＝０，找到数组中所有唯一的三元组，使得其和为0）
这里我第一反应还是先排序，然后，用夹逼的方法去找结果

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; // 如果之前同样的数字已经满足了，那么现在这个数字就直接跳过
            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++; // 在内循环中如果之前同样的数字已经满足了，那么现在这个数字就直接跳过
while(nums[right]==nums[right-1]) right--; // 在内循环中如果之前同样的数字已经满足了，那么现在这个数字就直接跳过
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
（给一组正整数，排列他们中所有的数，使整个数组形成最大的数，用字符串显示出来最后的结果）
（这个题其实和AMCAT上的题有点类似）

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"; // 凡事总有意外，这就是意外。设计 2 个 0 在这个地方。
        return res;
    }
};

Q：Longest Substring Without Repeating Characters
（给一个字符串，找出最长的不含重复元素的子串）

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
（在一个数组里面找到连续的一串子数组，使得他们相乘有最大的乘积）

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（这个题目超级的重要，有好几个轮子在里面）
（给一个未排序的数组，以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());（先根据中间值分成两部分，左边小，右边大）
        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)] // 现在我知道通过这种方法可以得到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 是一个这样的字符串，在字符串里面前面的数字可以相加组成后面的数字：
"112358" 是一个 additive number，因为这些数字可以形成一个递增的序列：1,1,2,3,5,8
"199100199" 也是一个 additive number，因为这些数字可以形成一个递增的序列：1,99,100,199
属于 additive 的数字中，不能含有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型的数据的长度
       long len = to_string(sum).size();
       if (numI == sum) return true;   // 这个是边界条件
       if (numI < sum || sum != stol(num.substr(0, len))) return false; // 如果条件不符合，直接截断
       else return addNum(num2, sum, num.substr(len)); // 依次递归，检查是否符合要求
    } 
};

这里有几个轮子：
a：stol：将字符串转换为 long 型

C：Word Break
[ 给一个字符串s和一个词典 dict，决定是否s能被拆分为 被空格分隔的一到多个序列 ]
[ 精确到每个数的下标 ]

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])  // 通过状态矩阵，来判断，如果 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.）
（首先两个数相乘，长度最大为两个数长度相加，所以结果集的长度初始化为两个长度的和）

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：给一棵二叉查找树，写一个函数 kthSmallest 来找到第k小的元素:
注意，如果一棵二叉查找树被频繁（修改/删除），你需要找到第K小的元素
（这道题的老方法是用节点计数加中序遍历，但是这道题的新方法是用栈来记录中间值）
（这个题的难点在于栈的基本元素是指针，而不是指针对应的值）

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
（给一棵二叉树，将它原地压扁成一棵单链表，这个地方是用前序遍历的方式）
// 我暂时想到的方式是，在前序遍历的过程中，用数组将中间的过程存起来，然后再输出；红色部分为前序遍历的代码，然后 vector 数组为记录中间的值。

class Solution {
public:
    void flatten(TreeNode* root) {
        if(root){
        vector<TreeNode*> vec;
        stack<TreeNode*> st;  //先将 right 放进去，再将 left 放进去，保证
        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];
        }
        }
    }
};

这种方法调用了额外的空间，肯定是不好的，下面是进行原地的旋转和递归调用：

class Solution {
public:
    TreeNode* help(TreeNode* root){
        // 指针的调用抓住两个点，A：指针一改则全改；B：指针形态的判断。
        if(!root->left&&!root->right) return root; // 根节点
        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
（这里要注意，如果涉及到链表相关的题目，需要返回一个头节点，最好重新设一个节点）

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（这种题看上去挺简单，但是其实，应用的场景很多）
// 对高度进行降维，分别降到 左边 和 右边。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q) return root;  // 在最后判断条件时，考虑 root 节点.
        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
（给一棵完全二叉树，统计完全二叉树的结点）
（在一个完全二叉树的每一层中，除了可能的最后一层外，其他的都是完全填满的，而且最后一层(h 层)的结点都是尽可能左移的）
（它能拥有1到2^h个结点）最后求有多少个结点
（通过二分的方法来算就好了）
（父结点是第0层，依次往下数）

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 对括弧，写一个功能来产生所有括弧的合理组合）
（不管是怎么样的组合，只要遵循先左再右的方式就可以了。同时把左右的数量保持一致就行）
（这种解题模式很重要）

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
（给一个目标值 n，然后找到k个数字的和为n的所有组合，所有数都是从[1 2 3 4 5 6 7 8 9]）
这个题我觉得和上面这个题的解决方法很相似了，因为都是可以用深度递归的方式去做。
（有两种解法，一种是先入后出法，入了之后，所有与它有关的解都应该能够被找出来，而出来了之后，的所有解将不包含它；第二种是标记法，如果集合不大，就用一维的布尔数组进行标记凡是标记过的，都不进行遍历，而没有被标记的元素，依次进行遍历。）

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
（这个题目，考的比较多，因为数值题是最容易考的，一组数，里面除了一个数只出现了1次以外，其他的数都各自出现了3次，找出这个数）。
这道题因为不能用数组

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.]
（二分查找的唯一准则，就是进行划分时，一定是将真正的答案留下，而不是被划走了）

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在范围内，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的二进制矩阵，填满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
这种题应该在很多应用场景中都会出现，给一个嵌套的数字的列表，用一个迭代器来压扁它：
其中，每一个元素要么是一个整数，要么是一个嵌套着整数的列表.
Example 1：Given the list [[1,1],2,[1,1]]. 最后变为 [1,1,2,1,1]
Example 2：Given the list [1,[4,[6]]]. 最后变为 [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 （求子集的题，应该还是比较容易出）
（给一个可能包含重复整数的集合，返回它不包含重复子集的结合）
If nums = [1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
（思考方式：不能包含重复子集，那么也就是说如果有几个相同的数重复出现，那么需要跳过）

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
（这是一道设计题，设计功能的实现方式，虽然有很多种实现的方式，但是如果考虑到性能，就没法实现）
（给一个整数数组，返回下标从 i 到 j 的所有元素的和）
update(i,val) 函数将下标为 i 的元素修改为 val.

D：Add and Search Word - Data structure design（这个题要用到前缀树）
（这也是一道设计题，支持两个功能：addWord（word）；search（word）；）
void addWord(word)
bool search(word)
支持通配符"."，这个通配符可以代表任何一个字母；这里与字母相关的，是前缀树
前缀树有个基本的节点：TrieNode

class TrieNode {
public:
     bool isKey;   // 这个key的意思是，这个是根节点。
     TrieNode* children[26];
         TrieNode(): isKey(false) {
            memset(children, NULL, sizeof(TrieNode*) * 26);  //给数组分配内存
         }
   };
class WordDictionary {
public:
    WordDictionary() {
        root = new TrieNode();
    }
    // Adds a word into the data structure.
    （每加入一个单词，就建立一条索引，或者复用一条索引）
    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 怎么转 char*数组
    }
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
（实现一个基本的计算器来计算一个简单的字符串表达式）
（这个字符串表达式中只包含非负的整数，+、-、*、/ 运算符，以及空格）

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、数学推理题
A：给你一个单项链表，然后判断是否有环，如果有环，返回环的起点：

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

两个瓶子可能量出的水是两个瓶子容量最大公约数的倍数。所以只要判断z是否可以被x，y的最大公约数整除即可。
造轮子：求两个数的公约数

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 方式进行编码）
'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; // 因为本身就算一次，所以，将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);  // 数组erase的时候，参数是迭代器
            k = k%total;
        }
        return res;
    }
};

10、动态规划题型

A：Triangle
【给一个三角形，找到里面从top到bottom和最小的路径，每一步你都可以移动到下一行的相邻的数字】

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
【给一组正整数的数组，你被初始化于一个数组头节点的位置，数组中的每一个元素都代表你能跳跃的最大的距离，判断是否能从头节点到末节点】
方法就是只要判断出能到的位置的最大值大于等于最后一个数就行了

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
（环形的数据结构，总是相对比较难一点）
[围绕着一个圆形的路径，有N个加油站，每个加油站的油的量为gas[i]，你有一个无限制油量大小的油桶，并且从站i 到 下一个站i+1，需要花费cost[i]，你以空油量从任何一个站加油出发，问能否围绕所有油站一次]
(首先，如果能绕一个圈，那么总存量为正数，否者为负数，在为正数的情况下，要去找那个起点，那么，就从0开始，然后，找到单段存量为负数的位置，从下一个开始就好。

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 [这个题目比较重要]
[给你不同面额的足量硬币以及一个钱的总额，写一个函数来计算你需要的最少的硬币来构成指定的面额，如果该面额数不能被任何面额的硬币构成，返回-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 方式进行编码）
（这个题，最麻烦的是，对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）和一个字典词序列，找到从起点到终点转换的最短路径，每次转换一个单词）
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++;   //  内部加1，忘了加
            unordered_set<string> tmp;
            //  针对beg_set 中的每一个单词，改变单词的每一个字母，然后去end_set里面去找，如果找到了，就说明直接可以结束了，如果没有找到，那么去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;
    }
};