LeetCode里有特色的问题存档

002* 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)).

class Solution:
    def findKth(self, A, A_start, B, B_start, k):
        if A_start >= len(A):
            return B[B_start + k - 1]
        if B_start >= len(B):
            return A[A_start + k - 1]
        if k == 1:
            return min(A[A_start], B[B_start])
        A_key = 0x3f3f3f3f
        if A_start + k / 2 - 1 < len(A):
            A_key = A[A_start + k / 2 - 1]
        B_key = 0x3f3f3f3f
        if B_start + k / 2 - 1 < len(B):
            B_key = B[B_start + k / 2 - 1]
        if A_key < B_key:
            return self.findKth(A, A_start + k / 2, B, B_start, k - k / 2)
        else:
            return self.findKth(A, A_start, B, B_start + k / 2, k - k / 2)
    # @return a float
    def findMedianSortedArrays(self, A, B):
        n = len(A) + len(B)
        if n % 2 == 0:
            return (self.findKth(A, 0, B, 0, n / 2) + self.findKth(A, 0, B, 0, n / 2 + 1)) / 2.0
        else:
            return self.findKth(A, 0, B, 0, n / 2 + 1)

出自算法导论9.3-8，设X[1..n]和Y[1..n]为两个数组，每个都包含n个已排好序的数。给出一个求数组X和Y中所有2n个元素的中位数的、O(lgn)时间算法。

int findMedian(int A[],int B[],int n,int low,int high) {  
    if (low > high) return NOT_FOUND;  
    else {  
        int k = (low+high)/2;  
        if (k==n && A[n]<=B[1]) return A[n];  
        else if (k<n && B[n-k]<=A[k] && A[k]<=B[n-k+1]) return A[k];  
        else if (A[k] > B[n-k+1]) return findMedian(A,B,n,low,k-1);  
        else return findMedian(A,B,n,k+1,high);  
    }  
}  
int twoArrayMedian(int X[],int Y[],int n) {  
    int median = findMedian(X,Y,n,1,n);  
    if (median==NOT_FOUND) median = findMedian(Y,X,n,1,n);  
    return median;  
}  

我们要取下中位数，注意到一个数x是中位数，当且仅当有n-1个数比x小，有n个数比x大，我们首先假设中位数在数组A中，二分中位数可能在的位置。
假设中位数所在区间为[L,R]，k为(L+R)/2。若A[k]是中位数，数组A中有k-1个数比A[k]小，n-k个数比A[k]大。若B中有n-k个数比A[k]小，有k个数比A[k]大，则A[k]是中位数。
由于B是已排序的，因此B[n-k]<=A[k]<=B[n-k+1]。
若A[k]>B[n-k+1]，则比A[k]小的数至少有n个，所以中位数小于A[k]，因此在区间[L,k-1]中。
反之则在区间[k+1,R]中。
若L>R，则中位数不在A中，对B数组进行同样的二分操作即可。

010* 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", "c*a*b") → true

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*p == 0) return *s == 0;
        if (*(p + 1) != '*') {
            if (*s != 0 && (*p == *s || *p == '.')) return isMatch(s + 1, p + 1);
            else return false;
        }
        else {
            while (*s != 0 && (*s == *p || *p == '.')) {
                if (isMatch(s, p + 2)) return true;
                s++;
            }
            return (isMatch(s, p + 2));
        }
    }
};

显然暴搜就可以了，但是同样的方法python却超时了。所以python有风险，提交需谨慎。

011* Container With Most Water  

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

class Solution:
    # @return an integer
    def maxArea(self, height):
        n = len(height)
        L = 0
        R = n - 1
        ans = 0
        while L < R:
            tmp = (R - L) * min(height[L], height[R])
            if tmp > ans:
                ans = tmp
            if height[L] < height[R]:
                b = height[L]
                while L < n and height[L] <= b:
                    L += 1
            else:
                b = height[R]
                while R >= 0 and height[R] <= b:
                    R -= 1
        return ans

关键在于如果已经计算过[L,R]，如果h[L+1....]<h[L]，那肯定不更优，同理如果h[R-1....]<h[R]，那肯定不是更优解。

所以要找h[L']>h[L]以及h[R']>h[R]。

012* Integer to Roman   

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

class Solution:
    # @return a string
    def intToRoman(self, num):
        s = ""
        if num >= 1000:
            i = num / 1000
            for j in range(i):
                s = s + "M"
            num -= 1000 * i
        if num >= 900:
            s = s + "CM"
            num -= 900
        if num >= 500:
            s = s + "D"
            num -= 500
        if num >= 400:
            s = s + "CD"
            num -= 400
        if num >= 100:
            i = num / 100
            for j in range(i):
                s = s + "C"
            num -= 100 * i
        if num >= 90:
            s = s + "XC"
            num -= 90
        if num >= 50:
            s = s + "L"
            num -= 50
        if num >= 40:
            s = s + "XL"
            num -= 40
        if num >= 10:
            i = num / 10
            for j in range(i):
                s = s + "X"
            num -= 10 * i
        if num >= 9:
            s = s + "IX"
            num -= 9
        if num >= 5:
            s = s + "V"
            num -= 5
        if num >= 4:
            s = s + "IV"
            num -= 4
        for j in range(num):
            s = s + "I"
        return s

问题在于我根本不知道罗马字母什么原理。。。

013* Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

class Solution:
    # @return an integer
    def romanToInt(self, s):
        n = len(s)
        p = 0
        num = 0
        cnt = 0
        while p < n:
            if s[p] == 'M':
                cnt = 0
                while p < n and s[p] == 'M':
                    cnt += 1
                    p += 1
                num += 1000 * cnt
            elif p + 1 < n and s[p:p+2] == 'CM':
                num += 900
                p += 2
            elif s[p] == 'D':
                num += 500
                p += 1
            elif p + 1 < n and s[p:p+2] == 'CD':
                num += 400
                p += 2
            elif s[p] == 'C':
                cnt = 0
                while p < n and s[p] == 'C':
                    cnt += 1
                    p += 1
                num += 100 * cnt
            elif p + 1 < n and s[p:p+2] == 'XC':
                num += 90
                p += 2
            elif s[p] == 'L':
                num += 50
                p += 1
            elif p + 1 < n and s[p:p+2] == 'XL':
                num += 40
                p += 2
            elif s[p] == 'X':
                cnt = 0
                while p < n and s[p] == 'X':
                    cnt += 1
                    p += 1
                num += 10 * cnt
            elif p + 1 < n and s[p:p+2] == 'IX':
                num += 9
                p += 2
            elif s[p] == 'V':
                num += 5
                p += 1
            elif p + 1 < n and s[p:p+2] == 'IV':
                num += 4
                p += 2
            elif s[p] == 'I':
                cnt = 0
                while p < n and s[p] == 'I':
                    cnt += 1
                    p += 1
                num += cnt
        return num

倒着搞一遍

016* 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        int n = num.size();
        int ans = 0x3f3f3f3f;
        int res = 0;
        for (int p = 0; p < n; p++) {
            int L = 0;
            int R = n - 1;
            while (L < R) {
                if (L == p) {
                    L++;
                    continue;
                }
                if (R == p) {
                    R--;
                    continue;
                }
                int sum = num[L] + num[R] + num[p];
                if (abs(sum - target) < ans) {
                    ans = abs(sum - target);
                    res = sum;
                }
                if (sum < target) {
                    L++;
                }
                else if (sum > target) {
                    R--;
                }
                else {
                    ans = 0;
                    res = sum;
                    break;
                }
            }
        }
        return res;
    }
};

python依然TLE，所以python有风险。。

枚举一个数，线性探查另外另个数。

017* 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        set<long long> st;
        sort(num.begin(), num.end());
        vector<vector<int> > res;
        int n = num.size();
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++) {
                int L = j + 1;
                int R = n - 1;
                while (L < R) {
                    int sum = num[i] + num[j] + num[L] + num[R];
                    if (sum < target) {
                        while (L + 1 < R && num[L + 1] == num[L]) L++;
                        L++;
                    }
                    else if (sum > target) {
                        while (L < R - 1 && num[R - 1] == num[R]) R--;
                        R--;
                    }
                    else {
                        vector<int> v = { num[i], num[j], num[L], num[R] };
                        res.push_back(v);
                        while (L + 1 < R && num[L + 1] == num[L]) L++;
                        L++;
                        while (L < R - 1 && num[R - 1] == num[R]) R--;
                        R--;
                    }
                }
                while (j + 1 < n && num[j + 1] == num[j]) j++;
            }
            while (i + 1 < n && num[i + 1] == num[i]) i++;
        }
        return res;
    }
};

同样是先枚举前两个数，然后线性找后两个数。多了一个判重。

018* Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

class Solution:
    def gao(self, dep):
        if dep == self.n:
            s = ""
            for c in self.s:
                s+=c
            self.ans.append(s)
            return
        idx = int(self.digits[dep])
        for i in range(len(self.phone[idx])):   
            self.s.append(self.phone[idx][i])
            self.gao(dep+1)
            self.s.pop()
    # @return a list of strings, [s1, s2]
    def letterCombinations(self, digits):
        self.phone = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        self.ans = []
        self.n = len(digits)
        self.s = []
        self.digits = digits
        self.gao(0)
        return self.ans

021* Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

class Solution:
    def gao(self, pl, pr):
        if pl == self.n and pr == self.n:
            gen = ""
            for c in self.gen:
                gen+=c
            self.ans.append(gen)
            return
        if pl < self.n:
            self.stack.append('(')
            self.gen.append('(')
            self.gao(pl + 1, pr)
            self.gen.pop()
            self.stack.pop()
        if len(self.stack) > 0 and pr < self.n:
            self.stack.pop()
            self.gen.append(')')
            self.gao(pl, pr + 1)
            self.gen.pop()
            self.stack.append('(')
    # @param an integer
    # @return a list of string
    def generateParenthesis(self, n):
        self.n = n
        self.ans = []
        self.stack = []
        self.gen = []
        self.gao(0, 0)
        return self.ans

括号匹配，直接搜

023* Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        cur = tmp = pre = None
        cur = head
        if cur != None and cur.next != None:
            head = cur.next
        while cur != None:
            if cur.next == None:
                return head
            next = cur.next
            if pre != None:
                pre.next = next
            tmp = next.next
            next.next = cur
            cur.next = tmp
            pre = cur
            cur = cur.next
        return head

024* Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

class Solution:
    def gao(self, head, k):
        cnt = 0
        p = head
        while p != None:
            p = p.next
            cnt += 1
        if cnt < k:
            return head, None
        p = head
        pre = p
        next = None
        tmp = None
        while k > 1 and p.next != None:
            tmp = next = p.next
            p.next = next.next
            next.next = pre
            pre = tmp
            k -= 1
        head = pre
        return head, p
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def reverseKGroup(self, head, k):
        head, p = self.gao(head, k)
        while p != None:
            lst = p
            p = p.next
            tmp, p = self.gao(p, k)
            lst.next = tmp
        return head

为什么会有这么多链表操作题呢

029* Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

class Solution:
    def check(self, p):
        #print "-------------------
", p
        L = R = p
        cnt = 0
        maxcnt = len(self.L)
        while L + self.len <= len(self.S) and R + self.len <= len(self.S):
            word = self.S[R:R+self.len]
            #print L,R,cnt,word
            if self.dict.has_key(word) == False:
                L = R = R + self.len
                cnt = 0
                self.book = {}
                continue
            if self.book.has_key(word) == False:
                self.book[word] = 0
            self.book[word] += 1
            cnt += 1
            R += self.len
            while self.book[word] > self.dict[word]:
                pre = self.S[L:L+self.len]
                self.book[pre] -= 1
                cnt -= 1
                L += self.len
            if cnt == maxcnt:
                self.ans.append(L)

    # @param S, a string
    # @param L, a list of string
    # @return a list of integer
    def findSubstring(self, S, L):
        self.L = L
        self.S = S
        self.ans = []
        self.dict = {}
        self.len = len(L[0])
        for c in L:
            if self.dict.has_key(c) == False:
                self.dict[c] = 0
            self.dict[c] += 1
        for i in xrange(self.len):
            self.book = {}
            self.check(i)
        return self.ans

 单词长度一致，尺取。

033* 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.

class Solution {
public:
    int normalSearch(int A[], int L, int R, int target) {
        while (L<=R) {
            int mid=(L+R)/2;
            if (A[mid]==target) return mid;
            else if (A[mid]<target) L=mid+1;
            else R=mid-1;
        }
        return -1;
    }
    int search(int A[], int n, int target) {
        int L=0,R=n-1;
        while (L<=R) {
            int mid=(L+R)/2;
            if (A[mid]==target) return mid;
            if (L==mid) {
                L+=1;
                continue;
            }
            if (R==mid) {
                R-=1;
                continue;
            }
            if (A[mid]>A[L]) {
                if (A[L]<=target&&A[mid]>target) return normalSearch(A, L, mid-1, target);
                else L=mid+1;
            }
            else {
                if (A[R]>=target&&A[mid]<target) return normalSearch(A, mid+1, R, target);
                else R=mid-1;
            } 
        }
        return -1;
    }
};

046* Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

class Solution {
private:
    bool next(vector<int> &a, int n) {
        if (n==0||n==1) return false;
        for (int i=n-2;i>=0;i--) {
            if (a[i]<a[i+1]) {
                for (int j=n-1;j>=0;j--) {
                    if (a[j]>a[i]) {
                        swap(a[i],a[j]);
                        int L=i+1,R=n-1;
                        while (L<R) {
                            swap(a[L],a[R]);
                            L++,R--;
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > ans;
        sort(num.begin(),num.end());
        ans.push_back(num);
        while (next(num, num.size())) {
            ans.push_back(num);
        }
        return ans;
    }
};

084* Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

class Solution {
public:
    int largestRectangleArea(vector<int> &h) {
        int n = h.size();
        vector<int> f(n), g(n);
        for (int i=0;i<n;i++) {
            f[i]=i;
            g[i]=i;
        }
        for (int i=0;i<n;i++) {
            while (f[i]-1 >= 0 && h[f[i]-1] >= h[i]) {
                f[i]=f[f[i]-1];
            }
        }
        for (int i=n-1;i>=0;i--) {
            while (g[i]+1 < n && h[g[i]+1] >= h[i]) {
                g[i]=g[g[i]+1];
            }
        }
        int ans = 0;
        for (int i=0;i<n;i++) {
            ans = max(ans, (g[i]-f[i]+1)*h[i]);
        }
        return ans;
    }
};

091* Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();
        if (n==0) return 0;
        vector<int> f(n+1);
        f[0]=1;
        if (s[0]=='0') f[1]=0;
        else f[1]=1;
        for (int i=2;i<=n;i++) {
            if (s[i-1]!='0') f[i]+=f[i-1];
            if (s[i-2]=='1') f[i]+=f[i-2];
            if (s[i-2]=='2'&&s[i-1]>='0'&&s[i-1]<='6') f[i]+=f[i-2];
        }
        return f[n];
    }
};

092* Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (head == NULL) return head;
        ListNode *pp=head, *pprev=NULL;
        for (int i=0;i<m-1;i++) {
            pprev=pp;
            pp=pp->next;
        }
        ListNode *prev=pp, *next=NULL, *p;
        p=pp->next;
        ListNode *last=pp;
        for (int i=m;i<n;i++) {
            next=p->next;
            p->next = prev;
            prev=p;
            p=next;
        }
        last->next=p;
        if (pprev) {
            pprev->next=prev;
        }
        else {
            head=prev;    
        }
        return head;
        
    }
};

097* Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size();
        int m = s2.size();
        int len = s3.size();
        if (n==0&&m==0) {
            if (len==0) return true;
            else return false;
        }
        if (n==0) {
            if (s2==s3) return true;
            else return false;
        }
        if (m==0) {
            if (s1==s3) return true;
            else return false;
        }
        if (n+m!=len) return false;
        vector<vector<bool> > f;
        f.resize(n+1);
        for (int i=0;i<=n;i++) {
            f[i].resize(m+1);
        }
        f[0][0]=true;
        for (int i=0;i<=n;i++) {
            for (int j=0;j<=m;j++) {
                if (i>0 && s1[i-1]==s3[i+j-1] && f[i-1][j]) f[i][j]=true;
                if (j>0 && s2[j-1]==s3[i+j-1] && f[i][j-1]) f[i][j]=true;
            }
        }
        if (f[n][m]) return true;
        return false;
    }
};

099* Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / 
 2   3
    /
   4
    
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode *mis1, *mis2, *pre;
public:
    void dfs(TreeNode *root) {
        if (root->left != NULL) dfs(root->left);
        if (pre!=NULL && root->val < pre->val) {
            if (mis1 == NULL) {
                mis1 = pre;
                mis2 = root;
            }
            else {
                mis2 = root;
            }
        }
        pre = root;
        if (root->right != NULL) dfs(root->right);
    }
    void recoverTree(TreeNode *root) {
        if (root == NULL) return;
        mis1 = mis2 = pre = NULL;
        dfs(root);
        if (mis1!=NULL && mis2!=NULL) {
            int tmp = mis1->val;
            mis1->val = mis2->val;
            mis2->val = tmp;
        }
    }
};