所有總結(jié)題目 http://www.itdecent.cn/p/55b90cfcb406

這里總結(jié)了頻率3的題目：

4. Median of Two Sorted Arrays

描述
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
代碼

//合并數(shù)組，然后快速確定中間值
/*解題思路：
（1）第一步將兩個(gè)有序數(shù)組合并成一個(gè)有序的數(shù)組（或者向量）（類似于兩個(gè)有序鏈表的合并）
（2）得到最終的數(shù)組（或者向量）長度為m+n，然后判斷是有奇數(shù)個(gè)值，還是有偶數(shù)個(gè)值
（3）如果有奇數(shù)個(gè)值，那么只有一個(gè)中間值，對應(yīng)的編號為 （數(shù)組（或者向量）長度 -1）/2，取出值，直接返回
（4）如果有偶數(shù)個(gè)值，那么有兩個(gè)中間值，對應(yīng)編號為：
    1）數(shù)組（或者向量）長度 /2 2）數(shù)組（或者向量）長度 /2 - 1
（5）取出對應(yīng)的值，然后求平均，得到最終結(jié)果 */

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int C[m+n];
        memset(C,0,(m+n)*sizeof(int));
        int k=0;
        int i=0,j=0;//定義下標(biāo)，其中i是向量1的下標(biāo)，j是向量2的下標(biāo)
        while(i<m&&j<n)
        {
             
            if(A[i]<=B[j])
                C[k++]=A[i++];
            else
                C[k++]=B[j++];
 
        }
         //數(shù)組B還有剩余部分，將數(shù)組B剩余部分依次插入
        if(i==m)
        {
            while(j<n)
                C[k++]=B[j++];
        }    
        else if(j==n)//數(shù)組A還有剩余部分，將數(shù)組A剩余部分依次插入
        {
            while(i<m)
                C[k++]=A[i++];
        }
        if((m+n)&1)//有奇數(shù)個(gè)值（一個(gè)中間值）
            return C[(m+n)>>1]*1.0;
        else////有偶數(shù)個(gè)值（兩個(gè)中間值，求平均值）
            return (C[(m+n)>>1]+C[((m+n)>>1)-1])*0.5;   ////-號優(yōu)先級比>>高
    }
};

7. Reverse Integer

描述
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you
have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10,

Did you notice that the reversed integer might overflow? Assume the input is a 32-
bit integer, then the reverse of 1000000003 overflows. How should you handle
such cases?
Throw an exception? Good, but what if throwing an exception is not an option?
You would then have to re-design the function (ie, add an extra parameter).

分析
短小精悍的題，代碼也可以寫的很短小。
代碼
// Reverse Integer
// 時(shí)間復(fù)雜度O(logn)，空間復(fù)雜度O(1)
// 考慮 1.負(fù)數(shù)的情況 2. 溢出的情況(正溢出&&負(fù)溢出，比如 x = -2147483648(即-2^31) )

class Solution {
public:
    int reverse (int x) {
        long long r = 0;
        long long t = x;
        t = t > 0 ? t : -t;
        for (; t; t /= 10)
            r = r * 10 + t % 10;
        
        bool sign = x > 0 ? false: true;
        if (r > 2147483647 || (sign && r > 2147483648)) {
            return 0;
        } else {
            if (sign) {
                return -r;
            } else {
                return r;
            }
        }
    }
};

10. Regular Expression Matching

描述
Implement regular expression matching with support for '.' and ''.
'.' Matches any single character. '' Matches zero or more of the
preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a") → true
isMatch("aa", ".") → true
isMatch("ab", ".") → true
isMatch("aab", "ca*b") → true

分析
這是一道很有挑戰(zhàn)的題。
遞歸版
// Regular Expression Matching
// 遞歸版，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

class Solution {
public:
    bool isMatch(const string& s, const string& p) {
        return isMatch(s.c_str(), p.c_str());
    }

private:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') return *s == '\0';

        // next char is not '*', then must match current character
        if (*(p + 1) != '*') {
            if (*s != '\0' && (*p == *s || *p == '.'))
                return isMatch(s + 1, p + 1);
            else
                return false;
        } else { // next char is '*'
            while (*s != '\0' && (*p == *s || *p == '.')) {
                if (isMatch(s, p + 2))
                    return true;
                s++;
            } 
            return isMatch(s, p + 2);
        }
    }
};

19. Remove Nth Node From End of List

描述
Given a linked list, remove the n -th node from the end of list and return its head.
For example, Given linked list: 1->2->3->4->5 , and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3-

5 .
Note:
Given n will always be valid.
Try to do this in one pass.

分析
設(shè)兩個(gè)指針 p , q ，讓 q 先走 n 步，然后 p 和 q 一起走，直到 q 走到尾節(jié)
點(diǎn)，刪除 p->next 即可。
代碼
// Remove Nth Node From End of List
// 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode dummy{-1, head};
        ListNode *p = &dummy, *q = &dummy;

        for (int i = 0; i < n; i++) // q先走n步
            q = q->next;
        
        while(q->next != nullptr) { // 一起走
            p = p->next;
            q = q->next;
        } 
        ListNode *tmp = p->next;
        p->next = p->next->next;
        delete tmp;
        return dummy.next;
    }
};

26. Remove Duplicates from Sorted Array

描述
Given a sorted array, remove the duplicates in place such that each element
appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with
constant memory.
For example, Given input array A = [1,1,2] ,
Your function should return length = 2, and A is now [1,2] .

代碼
// Remove Duplicates from Sorted Array
// 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int index = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[index - 1])
                nums[index++] = nums[i];
        } 
        return index;
    }
};

29. Divide Two Integers

描述
Divide two integers without using multiplication, division and mod operator.

分析
不能用乘、除和取模，那剩下的，還有加、減和位運(yùn)算。
最簡單的方法，是不斷減去被除數(shù)。在這個(gè)基礎(chǔ)上，可以做一點(diǎn)優(yōu)化，每次把被除
數(shù)翻倍，從而加速。
注意，寫代碼的時(shí)候，禁止使用 long.
代碼
// Divide Two Integers
// 時(shí)間復(fù)雜度O(logn)，空間復(fù)雜度O(1)
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 0) return INT_MAX;

        // 當(dāng) dividend = INT_MIN，divisor = -1時(shí)，結(jié)果會(huì)溢出
        if (dividend == INT_MIN) {
            if (divisor == -1) return INT_MAX;
            else if (divisor < 0)
                return 1 + divide(dividend - divisor, divisor);
            else
                return - 1 + divide((dividend + divisor), divisor);
        }
        if(divisor == INT_MIN){
            return dividend == divisor ? 1 : 0;
        }
        int a = dividend > 0 ? dividend : -dividend;
        int b = divisor > 0 ? divisor : -divisor;
        
        int result = 0;
        while (a >= b) {
            int c = b;
            for (int i = 0; a >= c;) {
                a -= c;
                result += 1 << i;
                if (c < INT_MAX / 2) { // prevent overflow
                    ++i;
                    c <<= 1;
                }
            }
        } 
        return ((dividend^divisor) >> 31) ? (-result): (result);
    }
};

33. Search in Rotated Sorted Array

描述
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index,
otherwise return -1.
You may assume no duplicate exists in the array.
分析
一個(gè)有序數(shù)組被循環(huán)右移，只可能有一下兩種情況：
7 │
6 │
─────┼───────────
│ 5
│ 4
│ 3
│ 2
│ 1
7 │
6 │
5 │
4 │
3 │
──────────┼───────────
│ 2
│ 1

本題依舊可以用二分查找，難度主要在于左右邊界的確定。仔細(xì)觀察上面兩幅圖，
我們可以得出如下結(jié)論： 如果 A[left] <= A[mid] ,那么 [left,mid] 一定為單調(diào)遞增序列。

代碼
// Time Complexity: O(log n)，Space Complexity: O(1)
class Solution {
public:
    int search(const vector<int>& nums, int target) {
        int first = 0, last = nums.size();
        while (first != last) {
            const int mid = first + (last - first) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[first] <= nums[mid]) {
                if (nums[first] <= target && target < nums[mid])
                    last = mid;
                else
                    first = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[last-1])
                    first = mid + 1;
                else
                    last = mid;
            }
        } 
        return -1;
    }
};

34. Search for a Range

描述
Given a sorted array of integers, find the starting and ending position of a given
target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

分析
已經(jīng)排好了序，用二分查找。
重新實(shí)現(xiàn) lower_bound 和 upper_bound
// Search for a Range
// 重新實(shí)現(xiàn) lower_bound 和 upper_bound
// 時(shí)間復(fù)雜度O(logn)，空間復(fù)雜度O(1)
class Solution {
public:
    vector<int> searchRange (vector<int>& nums, int target) {
        auto lower = lower_bound(nums.begin(), nums.end(), target);
        auto uppper = upper_bound(lower, nums.end(), target);
        if (lower == nums.end() || *lower != target)
            return vector<int> { -1, -1 };
        else
            return vector<int> {distance(nums.begin(), lower), distance(nums
        } 
    
    template<typename ForwardIterator, typename T>
    ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, T value) {
        while (first != last) {
            auto mid = next(first, distance(first, last) / 2);
            
            if (value > *mid) 
                first = ++mid;
            else 
                last = mid;
            } 
        return first;
    }

    template<typename ForwardIterator, typename T>
    ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, T value) {
        while (first != last) {
            auto mid = next(first, distance (first, last) / 2);

            if (value >= *mid)
                first = ++mid; // 與 lower_bound 僅此不同
            else
                last = mid;
        }
        return first;
    }
};

39. Combination Sum

描述
Given a set of candidate numbers ( C ) and a target number ( T ), find all unique
combinations in C where the candidate numbers sums to T .
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a , a , ..., a ) must be in non-descending order. (ie, a ≤ a ≤ ... ≤ a ).
The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7 , A solution set is:
[7]
[2, 2, 3]

代碼
// Combination Sum
// 時(shí)間復(fù)雜度O(n!)，空間復(fù)雜度O(n)
class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int> > result; // 最終結(jié)果
        vector<int> path; // 中間結(jié)果
        dfs(nums, path, result, target, 0);
        return result;
}

private:
    void dfs(vector<int>& nums, vector<int>& path, vector<vector<int
            int gap, int start) {
        if (gap == 0) { // 找到一個(gè)合法解
            result.push_back(path);
            return;
        } 
        for (size_t i = start; i < nums.size(); i++) { // 擴(kuò)展?fàn)顟B(tài)
            if (gap < nums[i]) return; // 剪枝
            
            path.push_back(nums[i]); // 執(zhí)行擴(kuò)展動(dòng)作
            dfs(nums, path, result, gap - nums[i], i);
            path.pop_back(); // 撤銷動(dòng)作
        }
    }
};