A：數(shù)組類
53 Maximum Subarray
從一個數(shù)組中找到連續(xù)的一個子數(shù)組，使得相加的和最大

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int i=0;
        int max =INT_MIN;
        int sum = 0;
        while(i<nums.size()&&nums[i]<0){
            max = max>nums[i]?max:nums[i];  
            sum = (sum+nums[i])>nums[i]?(sum+nums[i]):nums[i];
            i++;
        } 
        for(;i<nums.size();i++){
            if(nums[i]>=0){
                if(sum<0) sum = nums[i];
                else sum = sum + nums[i];
                max =max>sum?max:sum;
            }else{
                sum = sum + nums[i];
                if(sum<0) sum = nums[i];
            }
        }
        return max =max>sum?max:sum;
    }
};

300. Longest Increasing Subsequence
(Given an unsorted array of integers, find the length of longest increasing subsequence)
[10, 9, 2, 5, 3, 7, 101, 18]，The longest increasing subsequence is [2, 3, 7, 101]

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    vector<int> res;
    for(int i=0; i<nums.size(); i++) {
        auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
        if(it==res.end()) res.push_back(nums[i]);
        else *it = nums[i];
    }
    return res.size();
}

81. Search in Rotated Sorted Array II

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left =0,right = nums.size()-1;
        int tmp_left =0,tmp_right=0;
    // 這里相對上一道問題，多了個過濾的過程，過濾后，重新設定了左右兩個端點的位置
        while(left+1<=right&&nums[left+1]==nums[left]) left++;
        while(right-1>=left&&nums[right-1]==nums[right]) right--;
        tmp_left =left;tmp_right=right;
        
        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid]>nums[right]) left=mid+1;
            else right = mid;
        }
        
        int pivot = left;
        if(target<nums[tmp_left]){
            left = pivot;
            right = tmp_right;
        }else if(target>nums[tmp_left]){
            left = tmp_left;
            right = pivot==tmp_left?tmp_right:pivot-1;
        }else if(target==nums[tmp_left]) return true;

        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid]==target) return true;
            if(nums[mid]>target) right=mid-1;
            if(nums[mid]<target) left=mid+1;
        }
        if(left<nums.size()&&nums[left]==target) return true;
        return false;
    }
};

C：二叉樹類型
199. Binary Tree Right Side View
(給一棵二叉樹，想像你站在右邊看這課樹，返回你從頭結點到尾結點所能看到的所有結點的值）

class Solution {
public:
    queue<TreeNode*> q1;
    vector<int> res;
    void help(){
        while(!q1.empty()){
            int size = q1.size();
            for(int i=0;i<size;i++){
                TreeNode* tmp = q1.front();
                q1.pop();
                if(tmp->left) q1.push(tmp->left);
                if(tmp->right) q1.push(tmp->right);
            }
            if(!q1.empty()) res.push_back(q1.back()->val);
        }
    }   
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return res;
        q1.push(root);
        res.push_back(q1.back()->val);
        help();
        return res;
    }
};

108. Convert Sorted Array to Binary Search Tree
（給你一個升序的數(shù)組，將它轉換為一個高度平衡的二叉查找樹）

class Solution {
public:
    TreeNode* help(int left, int right, vector<int>& nums){
        if(left<=right){
            int mid = (left+right)/2;
            TreeNode* node = new TreeNode(nums[mid]);
            node->left = help(left,mid-1,nums);
            node->right = help(mid+1,right,nums);    
            return node;
        }else return nullptr;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0) return nullptr;
        return help(0,nums.size()-1,nums);
    }
};

109. Convert Sorted List to Binary Search Tree
（給你一個排序好的鏈表，將它轉換為一個高度平衡的二叉查找樹）
（都是找中點，只不過，鏈表，用的是快慢指針來找中點）

class Solution {
public:
    ListNode* findCenter(ListNode* head, ListNode* tail)
    {
        if(head==tail || head->next==tail) return head;
        ListNode* slow = head;
        ListNode* fast = head->next->next;
        while(fast != tail)
        {
            slow = slow->next;
            fast = fast->next;
            if(fast != tail) fast = fast->next;
        }
        return slow;
    }
    TreeNode* helper(ListNode* head, ListNode*tail)
    {
        if(head == tail) return NULL;
        if(head->next == tail) return new TreeNode(head->val);
        ListNode* center = findCenter(head, tail);
        TreeNode* t1 = helper(head, center);
        TreeNode* t2 = helper(center->next, tail);
        TreeNode* tree = new TreeNode(center->val);
        tree->left = t1;
        tree->right = t2;
        return tree;
    }
    TreeNode* sortedListToBST(ListNode* head) 
    {
        return helper(head, NULL);
    }
};

95. Unique Binary Search Trees II
(給一個數(shù)字n，產(chǎn)生所有結構上唯一的二叉查找樹，使得能夠存儲1到n的數(shù))
(這個題要做一個動態(tài)規(guī)劃，因為，當 n 相同的時候，能夠產(chǎn)生的二叉查找樹的數(shù)量也是固定的)

241. Different Ways to Add Parentheses
（給一個包含數(shù)字和操作符的字符串，返回所有通過數(shù)字和操作符所組合的可能的結果）

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        if(input.size() ==0) return {};
        vector<int> result;
        for(int i = 0; i < input.size(); i++)
        {
            if(input[i]!='+' &&input[i]!= '-' &&input[i]!= '*') continue;
            auto vec1 = diffWaysToCompute(input.substr(0, i));
            auto vec2 = diffWaysToCompute(input.substr(i+1));
            for(auto val1: vec1)
            {
                for(auto val2: vec2)
                {
                    if(input[i]=='+') result.push_back(val1+ val2);
                    else if(input[i]=='-') result.push_back(val1 - val2);
                    else if(input[i]== '*') result.push_back(val1 * val2);
                }
            }
        }
        return result.empty()?vector<int>{stoi(input)}:result;
    }
};

6. ZigZag Conversion

clipboard1.png

class Solution {
public:
    string convert(string s, int numRows) {
        string res="";
        if(s=="") return res;
        if(numRows==1||s.size()<=numRows) return s;  // 單行和單列的時候都是返回原來原有的字符串。

        for(int i=0;i<numRows;i++){
            if(i==0||i==numRows-1){
                for(int j=i;j<s.size();){
                    res= res + s[j];
                    j=j+(numRows-1)*2; 
                }
            }else if(i!=numRows-1){
                for(int j=i;j<s.size();){
                    res= res + s[j];
                    j=j+(numRows-i-1)*2;
                    if(j<s.size()){
                        res= res + s[j];
                        j=j+i*2;
                    }
                }
            }
        }
        return res;
    }
};

119 Pascal's Triangle II
(給一個索引k，返回第k行的楊輝三角的數(shù)組)

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result(rowIndex+1, 0);
        result[0]=1;
        for(int i=1; i<=rowIndex; i++) for(int j=i; j>=1; j--) result[j]=result[j]+result[j-1];
        return result;
    }
};

89. Gray Code
（格雷碼是這么一組數(shù)，前后的兩個數(shù)的的二進制位只相差1）
比如：n=2，return [0,1,3,2]

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res={0};
        for(int i=0;i<n;i++){
            int size = res.size();
            for(int j=size-1;j>=0;j--) res.push_back(res[j]+(1<<i));
        }
        return res;
    }
};

274. H-Index
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
（在一維數(shù)組中進行統(tǒng)計，可以看出很多關系出來，比如下面的方法，通過統(tǒng)計的方法，可以知道，比3大的數(shù)有多少個）
[3, 0, 6, 1, 5] -> [1,1,0,1,0,2] (對于下標為3的時候，可以得出有多少個數(shù)大于等于3)

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        if (n == 0) return 0;
        
        vector<int> hindex(n+1);
        
        for(int val: citations){
            if(val >= n) hindex[n]++;
            else hindex[val]++;
        }

        int sum = 0;
        int i = n;
        while (i > 0) {
            sum += hindex[i];
            if (i <= sum) return i;
            i--;
        }
        return 0;
    }
};

275. H-Index II
（What if the citations array is sorted in ascending order? Could you optimize your algorithm?）
（基本上，一談到排序的數(shù)組，就想到用二分的方法，找到( size()-i） == nums[i]）；

class Solution {
public:
    int hIndex(vector<int>& citations) {
        if(citations.size()==0) return 0;
        if(citations.size()==1) return 1<citations[0]?1:citations[0];
        else{
            int size = citations.size();
            int left = 0,right = citations.size()-1;
            while(left<right){
                int mid = left + (right-left)/2;
                if(citations[mid]==(size-mid)) return citations[mid];
                else if(citations[mid]>(size-mid)) right = mid;
                else left = mid+1;
            }
            return min(citations[left],(size-left));
        }
    }
};

289. Game of Life
（給一個 m*n 的矩陣，每一個單元格為 1 or 0 每一個單元格都會根據(jù)下面的四條規(guī)則被它的8個鄰居所影響）
1、任何一個活著的單元格周圍的8個單元格中活著的單元格小于2個，那么該單元格也會死掉。
2、任何一個活著的單元格周圍有兩個或者三個單元格活著，那么該單元格下一輪也會活著。
3、任何一個活著的單元格周圍的8個單元格中有超過三個單元格或者，那么該單元格也會死掉
4、任何一個死掉的單元格周圍的8個單元格中有剛好三個活著的鄰居，則會變成活的單元格。
這種矩陣的變幻，又要求在原地變幻，其實就是說找到那些需要是活著的單元格就好：

void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = m ? board[0].size() : 0;
    for (int i=0; i<m; ++i) {
        for (int j=0; j<n; ++j) {
            int count = 0;
        // 將與自己在內(nèi)的所有的數(shù)都統(tǒng)計一遍，然后只把需要將0變?yōu)?的case 選出來。
            for (int I=max(i-1, 0); I<min(i+2, m); ++I)
                for (int J=max(j-1, 0); J<min(j+2, n); ++J)
                    count += board[I][J] & 1;
            if (count == 3 || count - board[i][j] == 3)
                board[i][j] |= 2;
        }
    }
    for (int i=0; i<m; ++i)
        for (int j=0; j<n; ++j)
            board[i][j] >>= 1;
}

69、Sqrt(x)

class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        int left=1,right=x;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(mid>x/mid) right=mid;
            else{
                if(mid+1>x/(mid+1)) return mid;
                left = mid+1;
            }
        }
        return left;
    }
};

332. Reconstruct Itinerary

class Solution {
public:
    vector<string> vec;
    stack<string> st;
    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        unordered_map<string,multiset<string>> record;
        for(auto p: tickets){
            record[p.first].insert(p.second);
        }
        // -----begin from "JFK"-----------
        string str = "JFK";
        while(str!=""){
            st.push(str);
            if(!record[str].empty()){
                string str_ = *record[str].begin();
                record[str].erase(record[str].begin());  // 需要注意的是，這個erase 最好是刪除迭代器，因為里面是multiset，可以有多個相同的值
                str = str_;
            }else str="";
        }
        str = st.top();
        while(str!=""){
            if(record[str].empty()){
                vec.push_back(str);
                st.pop();
            }else{
                st.push(*record[str].begin());
                record[str].erase(record[str].begin());
            }
            if(st.size()>0) str = st.top();
            else str = "";
        }
        reverse(vec.begin(),vec.end());
        return vec;
    }
};

313. Super Ugly Number（這道題算是比較難的題）
寫一個函數(shù)去找到第n個 super ugly number
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        // 弄明白，如何去構造一個候選項集
        int lens  = primes.size();
        vector<int> pos(lens,0); //候選項集的下標
        vector<int> res(n,0);
        res[0]=1;
        for(int i=1;i<n;i++){
            int tmp=INT_MAX;
            for(int j=0;j<lens;j++) tmp = min(tmp,res[pos[j]]*primes[j]);    
            for(int j=0;j<lens;j++) if(tmp==res[pos[j]]*primes[j]) pos[j]++;
            res[i] = tmp;
        }
        return res[n-1];
    }
};