Leecode经典题目（频率3）

所有总结题目 http://www.jianshu.com/p/55b90cfcb406

这里总结了频率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)).
代码

//合并数组，然后快速确定中间值
/*解题思路：
（1）第一步将两个有序数组合并成一个有序的数组（或者向量）（类似于两个有序链表的合并）
（2）得到最终的数组（或者向量）长度为m+n，然后判断是有奇数个值，还是有偶数个值
（3）如果有奇数个值，那么只有一个中间值，对应的编号为 （数组（或者向量）长度 -1）/2，取出值，直接返回
（4）如果有偶数个值，那么有两个中间值，对应编号为：
    1）数组（或者向量）长度 /2 2）数组（或者向量）长度 /2 - 1
（5）取出对应的值，然后求平均，得到最终结果 */

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;//定义下标，其中i是向量1的下标，j是向量2的下标
        while(i<m&&j<n)
        {
             
            if(A[i]<=B[j])
                C[k++]=A[i++];
            else
                C[k++]=B[j++];
 
        }
         //数组B还有剩余部分，将数组B剩余部分依次插入
        if(i==m)
        {
            while(j<n)
                C[k++]=B[j++];
        }    
        else if(j==n)//数组A还有剩余部分，将数组A剩余部分依次插入
        {
            while(i<m)
                C[k++]=A[i++];
        }
        if((m+n)&1)//有奇数个值（一个中间值）
            return C[(m+n)>>1]*1.0;
        else////有偶数个值（两个中间值，求平均值）
            return (C[(m+n)>>1]+C[((m+n)>>1)-1])*0.5;   ////-号优先级比>>高
    }
};

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
// 时间复杂度O(logn)，空间复杂度O(1)
// 考虑 1.负数的情况 2. 溢出的情况(正溢出&&负溢出，比如 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

分析
这是一道很有挑战的题。
递归版
// Regular Expression Matching
// 递归版，时间复杂度O(n)，空间复杂度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.

分析
设两个指针 p , q ，让 q 先走 n 步，然后 p 和 q 一起走，直到 q 走到尾节
点，删除 p->next 即可。
代码
// Remove Nth Node From End of List
// 时间复杂度O(n)，空间复杂度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
// 时间复杂度O(n)，空间复杂度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.

分析
不能用乘、除和取模，那剩下的，还有加、减和位运算。
最简单的方法，是不断减去被除数。在这个基础上，可以做一点优化，每次把被除
数翻倍，从而加速。
注意，写代码的时候，禁止使用 long.
代码
// Divide Two Integers
// 时间复杂度O(logn)，空间复杂度O(1)
class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 0) return INT_MAX;

        // 当 dividend = INT_MIN，divisor = -1时，结果会溢出
        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.
分析
一个有序数组被循环右移，只可能有一下两种情况：
7 │
6 │
─────┼───────────
│ 5
│ 4
│ 3
│ 2
│ 1
7 │
6 │
5 │
4 │
3 │
──────────┼───────────
│ 2
│ 1

本题依旧可以用二分查找，难度主要在于左右边界的确定。仔细观察上面两幅图，
我们可以得出如下结论： 如果 A[left] <= A[mid] ,那么 [left,mid] 一定为单调递增序列。

代码
// 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].

分析
已经排好了序，用二分查找。
重新实现 lower_bound 和 upper_bound
// Search for a Range
// 重新实现 lower_bound 和 upper_bound
// 时间复杂度O(logn)，空间复杂度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
// 时间复杂度O(n!)，空间复杂度O(n)
class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int> > result; // 最终结果
        vector<int> path; // 中间结果
        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) { // 找到一个合法解
            result.push_back(path);
            return;
        } 
        for (size_t i = start; i < nums.size(); i++) { // 扩展状态
            if (gap < nums[i]) return; // 剪枝
            
            path.push_back(nums[i]); // 执行扩展动作
            dfs(nums, path, result, gap - nums[i], i);
            path.pop_back(); // 撤销动作
        }
    }
};