# LeetCode题解整理版(二)

Leetcode开始支持Python了，本篇题解中的题目都是用Python写的。

（更新中..）

## Reverse Words in a String

`class Solution:    # @param s, a string    # @return a string    def reverseWords(self, s):        return ' '.join([word[::-1] for word in s[::-1].split()])`

## Recover Binary Search Tree

`class Solution:    # @param root, a tree node    # @return a tree node    def recoverTree(self, root):        self.pre = None        self.n1 = self.n2 = None        self.dfs(root)        self.n1.val, self.n2.val = self.n2.val, self.n1.val        return root        def dfs(self, root):        if not root:            return        self.dfs(root.left)        if self.pre and root.val < self.pre.val:            if not self.n1:                self.n1, self.n2 = self.pre, root            else:                self.n2 = root        self.pre = root        self.dfs(root.right)`

## Validate Binary Search Tree

`class Solution:    # @param root, a tree node    # @return a boolean    val = None    def isValidBST(self, root):        if root is None:             return True        res = self.isValidBST(root.left)        if self.val is None:            self.val = root.val        else:            res = res and (root.val > self.val)            self.val = root.val        res = res and self.isValidBST(root.right)        return res`

## Interleaving String

`class Solution:    # @return a boolean    def isInterleave(self, s1, s2, s3):        if len(s3) != len(s1) + len(s2):            return False        dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]        for i in range(len(s1) + 1):            for j in range(len(s2) + 1):                if i == 0 and j == 0:                    dp[i][j] = True                elif i > 0 and dp[i-1][j] and s3[i+j-1] == s1[i-1]:                    dp[i][j] = True                elif j > 0 and dp[i][j-1] and s3[i+j-1] == s2[j-1]:                    dp[i][j] = True                else:                    dp[i][j] = False        return dp[len(s1)][len(s2)]`

## Unique Binary Search Trees II

`class Solution:    # @return a list of tree node    treelist = None    def generateTrees(self, n):        return self.dfs(0, n)        def dfs(self, l, r):        ans = []        if l == r:            ans.append(None)            return ans        for i in range(l, r):            lb, rb = self.dfs(l, i), self.dfs(i + 1, r)            for lc in lb:                for rc in rb:                    node = TreeNode(i + 1)                    node.left = lc                    node.right = rc                    ans.append(node)        return ans`

`class Solution:    # @param head, a ListNode    # @param m, an integer    # @param n, an integer    # @return a ListNode    def reverseBetween(self, head, m, n):        prem, pre, next, now, nowm = None, None, None, head, None;        ind = 1;        while now is not None:            next = now.next            if ind >= m and ind <= n:                now.next = pre            if ind == m:                prem, nowm = pre, now            if ind == n:                nowm.next = next                if prem is None:                    head = now                else:                    prem.next = now            pre, now, ind = now, next, ind + 1        return head`

## Subsets II

`class Solution:    # @param num, a list of integer    # @return a list of lists of integer    def subsetsWithDup(self, S):        S.sort()        bset = []        for x in range(2**len(S)):            for i in range(1, len(S)):                if (S[i] == S[i-1] and (x>>(i-1)&0x03 == 0x01)): break            else:                bset.append(x)        return [[S[x] for x in range(len(S)) if i>>x&1] for i in bset]`

## Decode Ways

1->A..26->Z一一对应，给一个数字串，问有多少种解码方式。

`S[i] = if(S[i] ok) S[i-1] + if (S[i-1..i] ok) S[i-2]`

`class Solution:    # @param s, a string    # @return an integer    def numDecodings(self, s):        if len(s) == 0:            return 0        dp = [1] + [0] * len(s)        ok = lambda x: x[0] != '0' and  int(x) >= 1 and int(x) <= 26;        for i in range(1, len(s) + 1):            dp[i] = dp[i-1] if ok(s[i-1:i]) else 0            if i >= 2:                dp[i]+= dp[i-2] if ok(s[i-2:i]) else 0        return dp[len(s)]`

## GrayCode

`000 0001 1011 3010 2----后两位以此为对称轴110 6111 7101 5100 4`

`class Solution:    # @return a list of integers    def grayCode(self, n):        self.res = [0]        for i in [2**x for x in range(0, n)]:            self.res.append(self.res[-1] + i)            self.res.extend([i + v for v in self.res[-3:None:-1]])        return self.res;`

## Merge Sorted Array

`class Solution:    # @param A  a list of integers    # @param m  an integer, length of A    # @param B  a list of integers    # @param n  an integer, length of B    # @return nothing    def merge(self, A, m, B, n):        for i in range(m + n - 1, -1, -1):            if m == 0 or (n > 0 and B[n-1] > A[m-1]):                A[i] = B[n-1]                n -= 1            else:                A[i] = A[m-1]                m -= 1        return A`

## Scramble String

`class Solution:    # @return a boolean    def isScramble(self, s1, s2):        if len(s1) != len(s2):            return False        if len(s1) == 0:            return True        self.s1, self.s2 = s1, s2        lens = len(s1)        self.dp = [[[-1] * lens for i in range(lens)] * lens for i in range(lens)]        return self.dfs(0, 0, len(s1))        def dfs(self, lp, rp, len):        if self.dp[lp][rp][len - 1] >= 0:            return True if self.dp[lp][rp][len - 1] == 1 else False        if len == 1:            return self.s1[lp] == self.s2[rp]        for i in range(1, len):            if self.dfs(lp, rp, i) and self.dfs(lp + i, rp + i, len - i) /                    or self.dfs(lp, rp + i, len - i) and self.dfs(lp + len - i, rp, i):                self.dp[lp][rp][len - 1] = 1                return True        self.dp[lp][rp][len - 1] = 0         return False`

## Partition List

`class Solution:    # @param head, a ListNode    # @param x, an integer    # @return a ListNode    def partition(self, head, x):        if head is None:            return head        sHead, bHead = ListNode(0), ListNode(0)        sTail, bTail = sHead, bHead        while head is not None:            if head.val < x:                sTail.next = head                sTail = sTail.next            else:                bTail.next = head                bTail = bTail.next            head = head.next        bTail.next = None        sTail.next = bHead.next        return sHead.next`

## Maximal Rectangle

`class Solution:    # @param matrix, a list of lists of 1 length string    # @return an integer    def maximalRectangle(self, matrix):        if len(matrix) == 0:            return 0        ans = 0;        for i in range(len(matrix)):            stk = []            for j in range(len(matrix[0]) + 1):                if j < len(matrix[0]): matrix[i][j] = int(matrix[i][j])                if i > 0 and j < len(matrix[0]) and matrix[i][j]:                    matrix[i][j] += matrix[i-1][j]                while len(stk) and (j == len(matrix[0]) or matrix[i][stk[-1]] >= matrix[i][j]):                    top = stk.pop()                    if len(stk) == 0:                        ans = max(ans, matrix[i][top]*j)                    else:                        ans = max(ans, matrix[i][top]*(j-stk[-1]-1))                stk.append(j)        return ans`

## Largest Rectangle in Histogram

N块宽度相同，高度不同的木板连在一起，求最大矩形。

`class Solution:    # @param height, a list of integer    # @return an integer    def largestRectangleArea(self, height):        ans, lenh, stk = 0, len(height), []        for i in range(lenh + 1):            while len(stk) and (i == lenh or height[stk[-1]] >= height[i]):                top = stk.pop()                if len(stk) == 0:                    ans = max(ans, height[top] * i)                else:                    ans = max(ans, height[top] * (i - stk[-1] - 1))            stk.append(i)        return ans`

## Remove Duplicates from Sorted List II

`class Solution:    # @param head, a ListNode    # @return a ListNode    def deleteDuplicates(self, head):        if not head:            return head        nHead, flag = ListNode(0), False        nHead.next, head = head, nHead        while head:            if (head.next and head.next.next and head.next.next.val == head.next.val):                head.next = head.next.next                flag = True            elif flag == True and head.next:                head.next = head.next.next                flag = False            else:                head = head.next        return nHead.next`

## Remove Duplicates from Sorted List

`class Solution:    # @param head, a ListNode    # @return a ListNode    def deleteDuplicates(self, head):        if not head:            return head        nHead = ListNode(0)        nHead.next, head = head, nHead        while head:            if (head.next and head.next.next and head.next.next.val == head.next.val):                head.next = head.next.next            else:                head = head.next        return nHead.next`

## Search in Rotated Sorted Array II

`class Solution:    # @param A a list of integers    # @param target an integer    # @return a boolean    def search(self, A, target):        l, h = 0, len(A) - 1        while (l <= h):            m = l + ((h - l) >> 1)            if A[m] == target:                return True            if A[m] == A[l] and A[m] == A[h]:                l, h = l + 1, h - 1            elif (A[m] > A[l] and target < A[m] and target >= A[l]) or (A[m] < A[l] and not (target <= A[h] and target > A[m])):                h = m - 1            else:                l = m + 1        return False`

## Remove Duplicates from Sorted Array II

`class Solution:    # @param A a list of integers    # @return an integer    def removeDuplicates(self, A):        sz = 0        for i in range(len(A)):            if sz < 2 or A[sz - 2] != A[i]:                A[sz] = A[i]                sz = sz + 1        return sz`

## Word Search

`class Solution:    # @param board, a list of lists of 1 length string    # @param word, a string    # @return a boolean    def exist(self, board, word):        self.h = len(board)        self.w = len(board[0])        for i in range(self.h):            for j in range(self.w):                if board[i][j] == word[0]:                    t, board[i][j] = board[i][j], ' '                    if self.dfs(board, word, i, j, 1):                        return True                    board[i][j] = t        return False        def dfs(self, board, word, x, y, p):        dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]        if (p == len(word)):            return True        for i in range(4):            nx, ny = x + dx[i], y + dy[i]            if 0 <= nx and nx < self.h and 0 <= ny and ny < self.w and board[nx][ny] == word[p]:                t, board[nx][ny] = board[nx][ny], ' '                if self.dfs(board, word, nx, ny, p + 1):                    return True                board[nx][ny] = t        return False`

## Subsets

`class Solution:    # @param S, a list of integer    # @return a list of lists of integer    def subsets(self, S):        S.sort()        return [[S[x] for x in range(len(S)) if i>>x&1] for i in range(2**len(S))]`

## Combinations

`class Solution:    # @return a list of lists of integers    def combine(self, n, k):        self.res = []        tmp = []        self.dfs(n, k, 1, 0, tmp)        return self.res    def dfs(self, n, k, m, p, tmp):        if k == p:            self.res.append(tmp[:])            return        for i in range(m, n+1):            tmp.append(i)            self.dfs(n, k, i+1, p+1, tmp)            tmp.pop()`

## Minimum Window Substring

`class Solution:    # @return a string    def minWindow(self, S, T):        d, dt = {}, dict.fromkeys(T, 0)        for c in T: d[c] = d.get(c, 0) + 1        pi, pj, cont = 0, 0, 0        ans = ""        while pj < len(S):            if S[pj] in dt:                if dt[S[pj]] < d[S[pj]]:                    cont += 1                dt[S[pj]] += 1;            if cont == len(T):                while pi < pj:                    if S[pi] in dt:                        if dt[S[pi]] == d[S[pi]]:                            break;                        dt[S[pi]] -= 1;                    pi+= 1                if ans == '' or pj - pi < len(ans):                    ans = S[pi:pj+1]                dt[S[pi]] -= 1                pi += 1                cont -= 1            pj += 1        return ans`

## Sort Colors

`class Solution:    # @param A a list of integers    # @return nothing, sort in place    def sortColors(self, A):        s, t, e = 0, 0, len(A) - 1        while s <= e:            if A[s] == 0:                if s != t:                    A[s], A[t] = A[t], A[s]                s, t = s + 1, t + 1            elif A[s] == 1:                s = s + 1            elif A[s] == 2:                if s != e:                    A[s], A[e] = A[e], A[s]                e = e - 1        return A`

## Search a 2D Matrix

`class Solution:    # @param matrix, a list of lists of integers    # @param target, an integer    # @return a boolean    def searchMatrix(self, matrix, target):        l, h = 0, len(matrix) * len(matrix[0]) - 1        while (l <= h):            m = l + ((h-l) >> 2)            v =  matrix[m/len(matrix[0])][m%len(matrix[0])]            if v < target:                l = m + 1            elif v > target:                h = m - 1            else:                return True        return False`

## Set Matrix Zeroes

`class Solution:    # @param matrix, a list of lists of integers    # RETURN NOTHING, MODIFY matrix IN PLACE.    def setZeroes(self, matrix):        if len(matrix) == 0:            return        lenn, lenm = len(matrix), len(matrix[0])        x, y = None, None        for i in range(lenn):            for j in range(lenm):                if matrix[i][j] != 0:                    continue                if x is not None:                    matrix[x][j] = matrix[i][y] = 0                else:                    x, y = i, j        if x is None:            return        for i in range(lenn):            for j in range(lenm):                if i == x or j == y:                    continue                if matrix[x][j] == 0 or matrix[i][y] == 0:                    matrix[i][j] = 0        for i in range(lenn):            matrix[i][y] = 0        for i in range(lenm):            matrix[x][i] = 0`

## Edit Distance

`class Solution:    # @return an integer    def minDistance(self, word1, word2):        dp = [[0] * (len(word2) + 1) for i in range(len(word1) + 1)]        for i in range(1, len(word1) + 1):             dp[i][0] = i        for i in range(1, len(word2) + 1):             dp[0][i] = i        for i in range(1, len(word1) + 1):            for j in range(1, len(word2) + 1):                dp[i][j] = dp[i - 1][j - 1] + 1                if word1[i - 1] == word2[j - 1]:                    dp[i][j] = dp[i - 1][j - 1]                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)        return dp[len(word1)][len(word2)]`

## Climbing Stairs

`class Solution:    # @param n, an integer    # @return an integer    def climbStairs(self, n):        f = [1, 1]        while len(f) <= n:            f.append(f[-1] + f[-2])        return f[n]`

## Sqrt(x)

`class Solution:    # @param x, an integer    # @return an integer    def sqrt(self, x):        y0, y1 = 0, 1        while int(y0) != int(y1):            y0 = y1            y1 = 1.0/2.0 * (y0 + x / y0)        return int(y0)`

## Text Justification

`'''words: ["This", "is", "an", "example", "of", "text", "justification."]L: 16.Return the formatted lines as:[   "This    is    an",   "example  of text",   "justification.  "]'''class Solution:    # @param words, a list of strings    # @param L, an integer    # @return a list of strings    def fullJustify(self, words, L):        ans, p, plen = [], 0, 0        for i in range(len(words)):            if plen + len(words[i]) + i - p - 1 >= L:                spc = (L - plen) // (i - p - 1) if i - p > 1 else 0                sps = (L - plen - spc * (i - p - 1))                str = words[p]                for j in range(p + 1, i):                    if sps > 0:                        str += ' '                        sps -= 1                    str += ' ' * spc + words[j]                 ans.append(str + ' ' * (L - plen))                plen, p = 0, i            if i < len(words):                plen += len(words[i])        str = ''        while p < len(words):            str += words[p]            if len(str) < L:                str += ' '            p = p + 1        ans.append(str + ' ' * (L - len(str)))         return ans`

## Plus One

`class Solution:    # @param digits, a list of integer digits    # @return a list of integer digits    def plusOne(self, digits):        for i in range(len(digits)-1, -1, -1):            digits[i] = (digits[i] + 1) % 10            if digits[i]:                break;        else:            digits.insert(0, 1)        return digits`

## Valid Number

`class Solution:    # @param s, a string    # @return a boolean    def isNumber(self, s):        s = s.strip();        # dfa status         err = -1 # error        srt = 0  # start        sgd = 1  # integer part sign         did = 2  # integer part number        ddp = 3  # xx. (there are some numbers before '.')        dnp = 3  # .        dii = 5  # decimal part number        exe = 6  # e        sge = 7  # exp part sign        die = 8  # exp part number        end = 9 # end        # construct a dfa        dfa = [[err] * 128 for i in range(9)]        dfa[srt][ord('+')] = dfa[srt][ord('-')] = sgd        dfa[srt][ord('.')] = dfa[sgd][ord('.')] = dnp        dfa[did][ord('.')] = ddp        dfa[did][ord('e')] = dfa[ddp][ord('e')] = dfa[dii][ord('e')] = exe        dfa[exe][ord('+')] = dfa[exe][ord('-')] = sge        dfa[dii][0] = dfa[ddp][0] = dfa[did][0] = dfa[die][0] = end        for i in range(10):            t =  ord('0') + i            dfa[srt][t] = dfa[sgd][t] = dfa[did][t] = did            dfa[ddp][t] = dfa[dnp][t] = dfa[dii][t] = dii            dfa[exe][t] = dfa[sge][t] = dfa[die][t] = die        # run dfa with s        s = s.strip()        status = srt        for c in s:            status = dfa[status][ord(c)]            #print status            if (status == err):                return False        return True if dfa[status][0] == end else False`

`class Solution:    # @param a, a string    # @param b, a string    # @return a string    def addBinary(self, a, b):        a = [ord(c) - ord('0') for c in a][::-1]        b = [ord(c) - ord('0') for c in b][::-1]        if (len(a) < len(b)):            a, b = b, a        flag = 0        for i in range(len(a)):            if (i < len(b)):                a[i] += b[i]            a[i] += flag            flag = a[i] // 2            a[i] %= 2        if flag:            a.append(1)        return ''.join([chr(c + ord('0')) for c in a][::-1])`

## Merge Two Sorted Lists

`class Solution:    # @param two ListNodes    # @return a ListNode    def mergeTwoLists(self, l1, l2):        nHead = ListNode(0)        lt, rt, backHead = l1, l2, nHead        while lt or rt:            if lt is None:                nHead.next, rt = rt, rt.next            elif rt is None:                nHead.next, lt = lt, lt.next            elif lt.val < rt.val:                nHead.next, lt = lt, lt.next            else:                nHead.next, rt = rt, rt.next            nHead = nHead.next        return backHead.next`

## Minimum Path Sum

`class Solution:    # @param grid, a list of lists of integers    # @return an integer    def minPathSum(self, grid):        for i in range(len(grid)):            for j in range(len(grid[0])):                if i == 0 and j > 0:                    grid[i][j] += grid[i][j-1]                elif j == 0 and i > 0:                    grid[i][j] += grid[i-1][j]                elif i > 0 and j > 0:                    grid[i][j] += min(grid[i-1][j], grid[i][j-1])        return grid[len(grid) - 1][len(grid[0]) - 1]`

## Unique Paths II

`class Solution:    # @param obstacleGrid, a list of lists of integers    # @return an integer    def uniquePathsWithObstacles(self, obstacleGrid):        ans = [[0] * len(obstacleGrid[0]) for i in range(len(obstacleGrid))]        for i in range(len(obstacleGrid)):            if obstacleGrid[i][0] == 1: break            else: ans[i][0] = 1        for i in range(len(obstacleGrid[0])):            if obstacleGrid[0][i] == 1: break            else: ans[0][i] = 1        for i in range(1, len(obstacleGrid)):            for j in range(1, len(obstacleGrid[0])):                if obstacleGrid[i][j] == 1:                    ans[i][j] = 0                else:                    ans[i][j] = ans[i][j-1] + ans[i-1][j]        return ans[len(ans)-1][len(ans[0])-1]`

## Unique Paths

`class Solution:    # @return an integer    def uniquePaths(self, m, n):        g = [[0] * n for i in range(m)]        for i in range(m): g[i][0] = 1        for j in range(n): g[0][j] = 1        for i in range(1, m):            for j in range(1, n):                g[i][j] = g[i][j-1] + g[i-1][j]        return g[m-1][n-1]`

## Rotate List

`class Solution:    # @param head, a ListNode    # @param k, an integer    # @return a ListNode    def rotateRight(self, head, k):        if not head:            return head        p, len = head, 1        while p.next:            p, len = p.next, len + 1        k = len - k % len        if k == len:            return head        pp, len = head, 1        while len < k:            pp, len = pp.next, len + 1        p.next, head, pp.next = head, pp.next, None        return head`

## Permutation Sequence

`class Solution:    # @return a string    def getPermutation(self, n, k):        d, ans, use = [0, 1], [], ['0'] * n        for i in range(2, 10) : d.append( i * d[-1])        for i in range(n):            ans.append(0)            for j in range(n):                if use[j] == 1:                    continue;                ans[i] = chr(ord('0') + j + 1)                if k <= d[n-i-1]:                    use[j] = 1                    break                k -= d[n-i-1]        return ''.join(ans)`

## Spiral Matrix II

`[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]class Solution:    # @return a list of lists of integer    def generateMatrix(self, n):        a = [[0] * n for i in range(n)]        sx, sy = 0, 0        dx, dy, dn = [0, 1, 0, -1], [1, 0, -1, 0], 0        for i in range(n * n):            a[sx][sy] = i + 1            nx, ny = sx + dx[dn], sy + dy[dn]            if nx < 0 or nx < 0 or nx >= n or ny >= n or a[nx][ny]:                dn = (dn + 1) % 4                nx, ny = sx + dx[dn], sy + dy[dn]            sx, sy = nx, ny        return a`

## Length of Last Word

`class Solution:    # @param s, a string    # @return an integer    def lengthOfLastWord(self, s):        i = len(s) - 1        while i >= 0 and s[i] == ' ': i -= 1        j = i - 1        while j >= 0 and s[j] != ' ': j -= 1        return 0 if i < 0 else i - j`

## Insert Interval

`class Solution:    # @param intervals, a list of Intervals    # @param newInterval, a Interval    # @return a list of Interval    def insert(self, intervals, newInterval):        ans, inserted = [], False        for i in range(len(intervals)):            if intervals[i].end < newInterval.start:                ans.append(intervals[i])            elif intervals[i].start > newInterval.end:                if not inserted:                    inserted = True                    ans.append(newInterval)                ans.append(intervals[i])            else:                newInterval.start = min(newInterval.start, intervals[i].start)                newInterval.end = max(newInterval.end, intervals[i].end)        if len(ans) == 0 or newInterval.start > ans[-1].end:            ans.append(newInterval)        return ans`

## Merge Intervals

`class Solution:    # @param intervals, a list of Interval    # @return a list of Interval    def merge(self, intervals):        intervals.sort(cmp = lambda x, y: cmp(x.start, y.start) or (x.start == y.start and cmp(x.end,y.end)))        ans, p, maxr = [], 0, 0        for i in range(len(intervals) + 1):            if i > 0 and (i == len(intervals) or intervals[i].start > maxr):                ans.append(Interval(intervals[p].start, maxr))                p = i            if i < len(intervals):                maxr = max(maxr, intervals[i].end)        return ans`

## Jump Game

x表示从当前位置最多还能走几步， 每走一步都将x-1和当前格子的值的较大值作为x的值。

`class Solution:    # @param A, a list of integers    # @return a boolean    def canJump(self, A):        if len(A) == 0:            return False        maxj = A[0]        for i in range(1, len(A)):            maxj -= 1            if (maxj < 0):                return False            maxj = max(maxj, A[i])        return True`

## Spiral Matrix

`[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]return [1,2,3,6,9,8,7,4,5]class Solution:    # @param matrix, a list of lists of integers    # @return a list of integers    def spiralOrder(self, matrix):        if len(matrix) == 0:            return []        a, ans, m, n = matrix, [], len(matrix), len(matrix[0])        x = [[0] * n for i in range(m)]        sx, sy = 0, 0        dx, dy, dn = [0, 1, 0, -1], [1, 0, -1, 0], 0        for i in range(m * n):            ans.append(a[sx][sy])            x[sx][sy] = 1            nx, ny = sx + dx[dn], sy + dy[dn]            if nx < 0 or nx < 0 or nx >= m or ny >= n or x[nx][ny]:                dn = (dn + 1) % 4                nx, ny = sx + dx[dn], sy + dy[dn]            sx, sy = nx, ny        return ans`

## Maximum Subarray

`class Solution:    # @param A, a list of integers    # @return an integer    def maxSubArray(self, A):        ans, sum = A[0], A[0]        for i in range(1, len(A)):            if (sum < 0):                sum = A[i]            else:                sum += A[i]            ans = max(ans, sum)        return ans`

## N-Queens II

`class Solution:    # @return an integer    def totalNQueens(self, n):        self.ans = 0        self.full = ((1 << n) - 1)        self.dfs(n, 0, 0, 0, 0)        return self.ans            def dfs(self, n, p, lt, rt, nt):        if n == p:            self.ans += 1            return        can = (~(lt | rt | nt) & self.full)        while can:           now = can&-can           self.dfs(n, p+1, (lt|now)>>1, (rt|now)<<1, nt|now)           can -= now`

## N-Queens

`class Solution:    # @return a list of lists of string    def solveNQueens(self, n):        self.ans, self.dt = [], {}        self.full = ((1 << n) - 1)        for i in range(n): self.dt[1<<i] = i        tmp = [['.'] * n for i in range(n)]        self.dfs(n, 0, 0, 0, 0, tmp)        return self.ans    def dfs(self, n, p, lt, rt, nt, tmp):        if n == p:            self.ans.append([''.join(s) for s in tmp])            return        can = (~(lt | rt | nt) & self.full)        while can:           now = can&-can           tmp[p][self.dt[now]] = 'Q'           self.dfs(n, p+1, (lt|now)>>1, (rt|now)<<1, nt|now, tmp)           tmp[p][self.dt[now]] = '.'           can -= now`

## Pow(x, n)

`class Solution:    # @param x, a float    # @param n, a integer    # @return a float    def pow(self, x, n):        if n == 0:            return 1        xx = pow(x, n >> 1)        xx *= xx        if n & 1: xx *= x        return xx`

## Anagrams

`class Solution:    # @param strs, a list of strings    # @return a list of strings    def anagrams(self, strs):        ans, dt = [], {}        for i in range(len(strs)):            lt = list(strs[i])            lt.sort()            s = ''.join(lt)            d = dt.get(s, -2)            if d == -2:                dt[s] = i            elif d == -1:                ans.append(strs[i])            else:                ans.append(strs[i])                ans.append(strs[d])                dt[s] = -1        return ans`

## Rotate Image

`class Solution:    # @param matrix, a list of lists of integers    # @return a list of lists of integers    def rotate(self, matrix):        L = len(matrix)        R = (L + 1) // 2        for x in range(0, R):            for y in range(0, L - R):                #(x,y)->(y,l-1-x)->(l-1-x,l-1-y)->(l-1-y,x)                matrix[x][y], matrix[y][L-1-x], matrix[L-1-x][L-1-y], matrix[L-1-y][x] /                = matrix[L-1-y][x], matrix[x][y], matrix[y][L-1-x], matrix[L-1-x][L-1-y]        return matrix`

## Permutations

next_permutation先从后向前找到第一个d[i]

d[i]的数，最后swap(d[i],d[j])并且reverse(d[i+1…n])就得到了下一个排列。

`class Solution:    # @param num, a list of integer    # @return a list of lists of integers    def permuteUnique(self, num):        num.sort()        ans = [num[:]]        while self.next_permutation(num):            ans.append(num[:])        return ans    def next_permutation(self, num):        for i in range(len(num)-2, -1, -1):            if num[i] < num[i+1]:                break        else:            return False        for j in range(len(num)-1, i, -1):            if num[j] > num[i]:                num[i], num[j] = num[j], num[i]                break        for j in range(0, (len(num) - i)//2):            num[i+j+1], num[len(num)-j-1] = num[len(num)-j-1], num[i+j+1]         return True`

## Jump Game II

`class Solution:    # @param A, a list of integers    # @return an integer    def jump(self, A):        maxj, maxn, tms = 0, 0, 0        for i in range(len(A) - 1):            maxn = max(maxn, A[i] + i)            if i == maxj:                maxj, tms = maxn, tms + 1        return tms`

## Wildcard Matching

`class Solution:    # @param s, an input string    # @param p, a pattern string    # @return a boolean    def isMatch(self, s, p):        ps, pp, lastp, lasts = 0, 0, -1, -1        while ps < len(s):            if pp < len(p) and (s[ps] == p[pp] or p[pp] == '?'):                ps, pp = ps + 1, pp + 1            elif pp < len(p) and p[pp] == '*':                pp = pp + 1                lastp, lasts = pp, ps            elif lastp != -1:                lasts = lasts + 1                pp, ps = lastp, lasts            else:                return False        while pp < len(p) and p[pp] == '*':            pp = pp + 1        return ps == len(s) and pp == len(p)`

## Multiply Strings

`class Solution:    # @param num1, a string    # @param num2, a string    # @return a string    def multiply(self, num1, num2):        num1 = [ord(i) - ord('0') for i in num1][::-1]        num2 = [ord(i) - ord('0') for i in num2][::-1]        ans = [0] * (len(num1) + len(num2) + 1)        for i in range(len(num1)):            for j in range(len(num2)):                ans[i + j] += num1[i] * num2[j]                ans[i + j + 1] += ans[i + j]                #ans[i + j]        while len(ans) > 1 and ans[len(ans) - 1] == 0:            ans.pop()        return ''.join([chr(i + ord('0')) for i in ans][::-1])`

## Trapping Rain Water

`class Solution:    # @param A, a list of integers    # @return an integer    def trap(self, A):        maxl, maxr, maxv, ans = [], [], 0, 0        for i in range(len(A)):            if A[i] > maxv: maxv = A[i]            maxl.append(maxv)        maxv = 0        for i in range(len(A)-1, -1, -1):            if A[i] > maxv: maxv = A[i]            maxr.append(maxv)        for i in range(len(A)):            minh = min(maxl[i], maxr[len(A) - i - 1]) - A[i]            ans += minh if minh > 0 else 0        return ans`

## First Missing Positive

`class Solution:    # @param A, a list of integers    # @return an integer    def firstMissingPositive(self, A):        L = len(A)        for i in range(L):            while A[i] > 0 and A[i] <= L and A[i] != A[A[i] - 1] and i != A[i] - 1:                A[A[i] - 1], A[i] = A[i], A[A[i] - 1]                #A[i], A[A[i] - 1] = A[A[i] - 1], A[i]  dosen't work        for i in range(L):            if i != A[i] - 1:                return i + 1        return L + 1`

## Combination Sum II

`class Solution:    # @param candidates, a list of integers    # @param target, integer    # @return a list of lists of integers    def combinationSum2(self, candidates, target):        candidates.sort()        self.ans, tmp, use = [], [], [0] * len(candidates)        self.dfs(candidates, target, 0, 0, tmp, use)        return self.ans    def dfs(self, can, target, p, now, tmp, use):        if now == target:            self.ans.append(tmp[:])            return        for i in range(p, len(can)):            if now + can[i] <= target and (i == 0 or can[i] != can[i-1] or use[i-1] == 1):                tmp.append(can[i]);                use[i] = 1                self.dfs(can, target, i+1, now + can[i], tmp, use)                tmp.pop()                use[i] = 0`

## Combination Sum

`class Solution:    # @param candidates, a list of integers    # @param target, integer    # @return a list of lists of integers    def combinationSum(self, candidates, target):        candidates.sort()        self.ans, tmp = [], []        self.dfs(candidates, target, 0, 0, tmp)        return self.ans    def dfs(self, candidates, target, p, now, tmp):        if now == target:            self.ans.append(tmp[:])            return        for i in range(p, len(candidates)):            if now + candidates[i] <= target:                tmp.append(candidates[i])                self.dfs(candidates, target, i, now+candidates[i], tmp)                tmp.pop()`

## Count and Say

`1, 11, 21, 1211, 111221, ...1 is read off as "one 1" or 11.11 is read off as "two 1s" or 21.21 is read off as "one 2, then one 1" or 1211.class Solution:    # @return a string    def countAndSay(self, n):        s, now = [str(1), ''], 0        for i in range(1, n):            now, pre, tot = now^1, now, 0            s[now], p = "", 0            while p  < len(s[pre]):                tot, v, p = 1, s[pre][p], p + 1                while p < len(s[pre]) and v == s[pre][p]:                    p += 1                    tot += 1                s[now] += str(tot) +  v        return s[now]`

## Sudoku Solver

`class Solution:    # @param board, a 9x9 2D array    # Solve the Sudoku by modifying the input board in-place.    # Do not return any value.    def solveSudoku(self, board):        lt, rt, bt = [0] * 9, [0] * 9, [0] * 9        self.dt = {}        for i in range(9): self.dt[1<<i] = chr(ord('1')+i)        for i in range(9):            board[i] = list(board[i])            for j in range(9):                if (board[i][j] == '.'):                    continue;                num = ord(board[i][j]) - ord('1')                lt[i] |= 1 << num                rt[j] |= 1 << num                bt[j//3*3+i//3] |= 1 << num        self.dfs(board, 0, lt, rt, bt)        board = [''.join(s) for s in board]        def dfs(self, board, p, lt, rt, bt):        while p < 81 and board[p/9][p%9] != '.':            p += 1        if p == 81:            return True        i, j, k = p//9, p%9, p%9//3*3+p//9//3        if board[i][j] != '.':            self.dfs(board, p + 1, lt, rt, bt)            return True        can = (~(lt[i]|rt[j]|bt[k])) & (0x1ff)        pre = board[i]        while can:            num = can&-can            board[i][j] = self.dt[num]            lt[i] |= num            rt[j] |= num            bt[k] |= num            if self.dfs(board, p + 1, lt, rt , bt):                return True            board[i][j] = '.'            lt[i] &= ~num            rt[j] &= ~num            bt[k] &= ~num            can -= num        return False`

## Valid Sudoku

`class Solution:    # @param board, a 9x9 2D array    # @return a boolean    def isValidSudoku(self, board):        lt, rt, bt = [0] * 9, [0] * 9, [0] * 9        for i in range(9):            for j in range(9):                print i, j                if (board[i][j] == '.'):                    continue;                num = ord(board[i][j]) - ord('1')                if 0 == (~(lt[i]|rt[j]|bt[j/3*3+i/3]) & (1<<num)):                    return False                lt[i] |= 1 << num                rt[j] |= 1 << num                bt[j/3*3+i/3] |= 1 << num        return True`

## Search Insert Position

`class Solution:    # @param A, a list of integers    # @param target, an integer to be inserted    # @return integer    def searchInsert(self, A, target):        l, h = 0, len(A)         while l < h:            m = (l + h) // 2            if A[m] < target:                l = m + 1            else:                h = m        return l`

## Search for a Range

`class Solution:    # @param A, a list of integers    # @param target, an integer to be searched    # @return a list of length 2, [index1, index2]    def searchRange(self, A, target):        return [self.lower_bound(A, target), self.upper_bound(A, target)]    def lower_bound(self, A, target):        l, h, m = 0, len(A), 0        while l < h:            m = (l + h) >> 1            if A[m] < target:                l = m + 1            else:                h = m        return l if l < len(A) and A[l] == target else -1    def upper_bound(self, A, target):        l, h, m = 0, len(A),  0        while l < h:            m = (l + h) >> 1            if A[m] <= target:                l = m + 1            else:                h = m        return l-1 if l-1 < len(A) and A[l-1] == target else -1`

## Search in Rotated Sorted Array

`class Solution:    # @param A, a list of integers    # @param target, an integer to be searched    # @return an integer    def search(self, A, target):        l, h = 0, len(A) - 1        while (l <= h):            m = l + ((h - l) >> 1)            if A[m] == target:                return m            elif (A[m] > A[l] and target < A[m] and target >= A[l]) or (A[m] < A[l] and not (target <= A[h] and target > A[m])):                h = m - 1            else:                l = m + 1        return -1`

## Longest Valid Parentheses

`class Solution:    # @param s, a string    # @return an integer    def longestValidParentheses(self, s):        stk, p ,ans = [], [0] * len(s), 0        for i in range(len(s)):            if s[i] == '(':                stk.append(i)            elif s[i] == ')':                if len(stk) > 0:                    p[i] = i - stk[-1] + 1                    if i >= p[i] and p[i - p[i]]:                        p[i] += p[i-p[i]]                    ans = max(ans, p[i])                    stk.pop()        return ans`

## Next Permutation

`class Solution:    # @param num, a list of integer    # @return a list of integer    def nextPermutation(self, num):        for i in range(len(num)-2, -1, -1):            if num[i] < num[i+1]:                break        else:            num.reverse()            return num        for j in range(len(num)-1, i, -1):            if num[j] > num[i]:                num[i], num[j] = num[j], num[i]                break        for j in range(0, (len(num) - i)//2):            num[i+j+1], num[len(num)-j-1] = num[len(num)-j-1], num[i+j+1]        return num`

## Substring with Concatenation of All Words

`class Solution:    # @param S, a string    # @param L, a list of string    # @return a list of integer    def findSubstring(self, S, L):        LS, LL, LL0 = len(S), len(L), len(L[0])        did, ids, dl = {}, 0, {}        for s in L:             id = did.get(s, -1)            if id == -1:                 ids = ids + 1                 id = ids                 did[s] = id            dl[id] = dl.get(id, 0) + 1                pos, ans = [0] * LS, []        for k, v in did.items():            f = S.find(k)            while f != -1:                pos[f] = v                f = S.find(k, f + 1)                        for sp in range(LL0):            np, pp, tot, dt = sp, sp, 0, {}            while np < LS:                t = pos[np]                if t == 0:                    tot, dt = 0, {}                    pp, np = np + LL0, np + LL0                elif dt.get(t, 0) < dl[t]:                    dt[t] = dt.get(t, 0) + 1                    tot = tot + 1                    if tot == LL:                        ans.append(pp)                    np = np + LL0                else:                    while pos[pp] != t:                        tot = tot - 1                        dt[pos[pp]] -= 1                        pp = pp + LL0                    pp = pp + LL0                    dt[t] -= 1                    tot = tot - 1        return ans`

## Divide Two Integers

`class Solution:    # @return an integer    def divide(self, dividend, divisor):        flag, ans = 0, 0        if dividend < 0:            flag, dividend = flag^1, -dividend        if divisor < 0:            flag, divisor = flag^1, -divisor        while dividend >= divisor:            count, newDivisor = 1, divisor            while newDivisor + newDivisor <= dividend:                newDivisor = newDivisor + newDivisor                count = count + count            dividend -= newDivisor            ans += count        return ans if flag == 0 else -ans`

## Implement strStr()

KMP了，好久不写真的写不出来了。。。

`class Solution:    # @param haystack, a string    # @param needle, a string    # @return a string or None    def strStr(self, haystack, needle):        lenh, lenn = len(haystack), len(needle)        if lenn == 0:            return haystack        next, p = [-1] * (lenn), -1        for i in range(1, lenn):            while p >= 0 and needle[i] != needle[p + 1]:                p = next[p]            if needle[i] == needle[p + 1]:                p  = p + 1            next[i] = p        p = -1        for i in range(lenh):            while p >= 0 and haystack[i] != needle[p + 1]:                p = next[p]            if haystack[i] == needle[p + 1]:                p = p + 1            if p + 1 == lenn:                return haystack[i - p:]         return None`

## Remove Element

`class Solution:    # @param    A       a list of integers    # @param    elem    an integer, value need to be removed    # @return an integer    def removeElement(self, A, elem):        sz = 0        for i in range(0, len(A)):            if A[i] != elem:                A[sz] = A[i]                sz += 1        return sz`

## Remove Duplicates from Sorted Array

`class Solution:    # @param a list of integers    # @return an integer    def removeDuplicates(self, A):        if len(A) == 0:            return 0        sz = 1        for i in range(1, len(A)):            if A[i] != A[i-1]:                A[sz] = A[i]                sz += 1        return sz`

## Reverse Nodes in k-Group

`class Solution:    # @param head, a ListNode    # @param k, an integer    # @return a ListNode    def reverseKGroup(self, head, k):        nHead = ListNode(0)        nHead.next = head        p2, lenl = head, 0        while p2: p2, lenl = p2.next, lenl + 1        now, pre, ind = head, nHead, 1        preHead, preHeadNext = nHead, head        while now:            if lenl - ind < lenl % k:                break            next = now.next            now.next = pre            if ind % k == 0:                preHead.next = now                preHeadNext.next = next                preHead = preHeadNext                pre = preHead                preHeadNext = next            else:                pre = now            now, ind = next, ind + 1        return nHead.next`

## Swap Nodes in Pairs

`class Solution:    # @param a ListNode    # @return a ListNode    def swapPairs(self, head):        if head is None or head.next is None:            return head        nHead = ListNode(0)        nHead.next = head        p1, p2 = nHead, head        while p2 and p2.next:            p2 = p2.next.next            p1.next.next.next = p1.next            p1.next = p1.next.next            p1.next.next.next = p2            p1 = p1.next.next        return nHead.next`

## Merge k Sorted Lists

`class Solution:    # @param a list of ListNode    # @return a ListNode    def mergeKLists(self, lists):        self.heap = [[i, lists[i].val] for i in range(len(lists)) if lists[i] != None]        self.hsize = len(self.heap)        for i in range(self.hsize - 1, -1, -1):            self.adjustdown(i)                    nHead = ListNode(0)        head = nHead        while self.hsize > 0:            ind, val = self.heap[0][0], self.heap[0][1]            head.next = lists[ind]            head = head.next            lists[ind] = lists[ind].next            if lists[ind] is None:                self.heap[0] = self.heap[self.hsize-1]                self.hsize = self.hsize - 1            else:                self.heap[0] = [ind, lists[ind].val]            self.adjustdown(0)        return nHead.next                def adjustdown(self, p):        lc = lambda x: (x + 1) * 2 - 1        rc = lambda x: (x + 1) * 2        while True:            np, pv = p, self.heap[p][1]            if lc(p) < self.hsize and self.heap[lc(p)][1] < pv:                np, pv = lc(p), self.heap[lc(p)][1]            if rc(p) < self.hsize and self.heap[rc(p)][1] < pv:                np = rc(p)            if np == p:                break            else:                self.heap[np], self.heap[p] = self.heap[p], self.heap[np]                p = np`

## Generate Parentheses

DFS搜索了，注意右括号不能比左括号多即可

`class Solution:    # @param an integer    # @return a list of string    def generateParenthesis(self, n):        self.ans, tmp = [], []        lb = 0        self.dfs(lb, 0, n, tmp)        return self.ans        def dfs(self, lb, p, n, tmp):        if p == n * 2:            self.ans.append(''.join(tmp))            return        if lb < n:            tmp.append('(')            self.dfs(lb + 1, p + 1, n, tmp)            tmp.pop()        if p - lb < lb:            tmp.append(')')            self.dfs(lb, p + 1, n, tmp)            tmp.pop()`

## Valid Parentheses

`class Solution:    # @return a boolean    def isValid(self, s):        dct = {'(':')', '[':']', '{':'}'}        stk = []        for c in s:            if dct.get(c, None):                stk.append(c)            elif len(stk) == 0 or dct[stk[-1]] != c:                return False            else:                stk.pop()        return True if len(stk) == 0 else False`

## Remove Nth Node From End of List

`class Solution:    # @return a ListNode    def removeNthFromEnd(self, head, n):        nHead = ListNode(0)        nHead.next = head        p, t = 0, head        while p < n:            t = t.next            p += 1        pre = nHead        while t:            t, pre = t.next, pre.next        pre.next = pre.next.next        return nHead.next`

## Letter Combinations of a Phone Number

DFS

`class Solution:    # @return a list of strings, [s1, s2]    def letterCombinations(self, digits):        if len(digits) == 0:            return [""]        self.dglist = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]        self.ans, tmp = [], []        self.dfs(digits, 0, tmp)        return self.ans        def dfs(self, digits, p, tmp):        if (p == len(digits)):            self.ans.append(''.join(tmp))            return        for c in self.dglist[ord(digits[p]) - ord('0')]:            tmp.append(c)            self.dfs(digits, p + 1, tmp)            tmp.pop()`

## 4Sum

`class Solution {public:    vector<vector<int> > fourSum(vector<int> &num, int target) {        vector<vector<int> > ans;        sort(num.begin(), num.end());        for (int i = 0; i < num.size(); i++) {            if (i > 0 && num[i] == num[i-1]) continue;            for (int j = i + 1; j < num.size(); j++) {                if (j > i + 1 && num[j] == num[j - 1]) continue;                int l = j + 1, r = num.size() - 1;                while (l < r) {                    int sum = num[i] + num[j] + num[l] + num[r];                    if (sum == target) {                        ans.push_back({num[i], num[j], num[l], num[r]});                        while (l < r && num[l] == num[l + 1]) l++; l++;                        while (l < r && num[r] == num[r - 1]) r--; r--;                    } else if (sum < target) {                        l++;                    } else {                        r--;                    }                }             }        }        return ans;    }};`

## 3Sum Closest

`class Solution:    # @return an integer    def threeSumClosest(self, num, target):        num.sort()        ans = None        for i in range(len(num)):            l, r = i + 1, len(num) - 1            while (l < r):                                    sum = num[l] + num[r] + num[i]                if ans is None or abs(sum- target) < abs(ans - target):                    ans = sum                if sum <= target:                    l = l + 1                else:                    r = r - 1        return ans`

## 3Sum

`class Solution:    # @return a list of lists of length 3, [[val1,val2,val3]]    def threeSum(self, num):        num.sort()        dct, ans = {}, []        for i in range(0, len(num)):            if (i > 0 and num[i] == num[i-1]):                continue            l, r = i + 1, len(num) - 1            while l < r:                sum = num[l] + num[r] + num[i]                if sum == 0:                    ans.append([num[i], num[l], num[r]])                    while l < r and num[l] == num[l + 1]: l = l + 1                    while l < r and num[r] == num[r - 1]: r = r - 1                    l, r = l + 1, r - 1                elif sum < 0:                    l = l + 1                else:                    r = r - 1           return ans`

## Longest Common Prefix

`class Solution:    # @return a string    def longestCommonPrefix(self, strs):        if len(strs) <= 1:            return strs[0] if len(strs) == 1 else ""        end, minl = 0, min([len(s) for s in strs])        while end < minl:            for i in range(1, len(strs)):                if strs[i][end] != strs[i-1][end]:                    return strs[0][:end]            end = end + 1        return strs[0][:end]`

## Roman to Integer

`class Solution:    # @return an integer    def romanToInt(self, s):        roval = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}        ans = 0        for i in range(len(s)):            if i + 1 < len(s) and roval[s[i]] < roval[s[i+1]]:                ans -= roval[s[i]]            else:                ans += roval[s[i]]        return ans`

## Integer to Roman

`class Solution:    # @return a string    def intToRoman(self, num):        ronum  = [['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'],                  ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'],                  ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'],                  ['', 'M', 'MM', 'MMM', '  ', ' ', '  ', '   ', '    ', '  ']]        ans, ind = '', 0        while num:            ans = ronum[ind][num%10] + ans            num, ind = num / 10, ind + 1        return ans`

## Container With Most Water

`class Solution:    # @return an integer    def maxArea(self, height):        l, r, ans = 0, len(height) - 1, 0        while l <= r:            ans = max(ans, (r - l) * min(height[r], height[l]))            if height[l] < height[r]:                l = l + 1            else:                r = r - 1        return ans`

## Regular Expression Matching

DP做的，dp[i][j]表示s[1..i]和p[1..j]匹配，需要考虑的情况还是比较复杂的，搜索应该也可行。

`class Solution:    # @return a boolean    def isMatch(self, s, p):        s, p = ' ' + s, ' ' + p        dp = [[False] * (len(p)) for i in range(len(s))]        dp[0][0] = True        ind = 2        while ind < len(p) and p[ind] == '*':            dp[0][ind], ind = True, ind + 2        for i in range(1, len(s)):            for j in range(1, len(p)):                if (s[i] == p[j] or p[j] == '.') and dp[i-1][j-1]:                    dp[i][j] = True                if p[j] == '*' and (dp[i][j-2] or ((p[j-1] == '.' or p[j-1] == s[i]) and (dp[i-1][j-2] or dp[i-1][j]))):                    dp[i][j] = True        return dp[len(s) - 1][len(p) - 1]s = Solution()print s.isMatch("aa", "a")              # Falseprint s.isMatch("aa", "aa")             # Trueprint s.isMatch("aaa","aa")             # Falseprint s.isMatch("aa", "a*")             # Trueprint s.isMatch("aa", ".*")             # Trueprint s.isMatch("ab", ".*")             # Trueprint s.isMatch("aab", "c*a*b")         # Trueprint s.isMatch("aaa", "ab*a")          # Fasleprint s.isMatch("aaba", "ab*a*c*a")     # Falseprint s.isMatch("", ".*")               # Trueprint s.isMatch("bbab", "b*a*")         # Falseprint s.isMatch("aab", "b.*")           # False`

## Palindrome Number

`class Solution:    # @return a boolean    def isPalindrome(self, x):        if x <= 0:            return False if x < 0 else True        a, b = x, 0        while a:            b, a = b * 10 + a % 10, a / 10        return b == x`

## String to Integer (atoi)

1.前面有空格；

2.遇到非法字符就不再分析后面的；

3.有可能越界。

`class Solution:    # @return an integer    def atoi(self, str):        if len(str) == 0:            return 0        sgn, num, p = 0, 0, 0        imin, imax = -1<<31, (1<<31)-1        while str[p] == ' ':            p  = p + 1        if str[p] == '-' or str[p] == '+':            sgn = 1 if str[p] == '-' else 0            p = p + 1        while p < len(str) and str[p] >= '0' and str[p] <= '9':            num = num * 10 + ord(str[p]) - ord('0')            x = -num if sgn else num            if x < imin: return imin            if x > imax: return imax            p = p + 1        return -num if sgn else num`

## Reverse Integer

`class Solution:    # @return an integer    def reverse(self, x):        a = 0        b = x if x > 0 else -x        while b:            a, b = a * 10 + b % 10, b / 10         return a if x > 0 else -a`

## ZigZag Conversion

`'''P   A   H   N   1   5   ...A P L S I I G   2 4 6 8 ...Y   I   R       3   7   ...convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".'''class Solution:    # @return a string    def convert(self, s, nRows):        if nRows == 1 or len(s) == 0:            return s        res, lens = [], len(s)        add, now = [nRows * 2 - 2, 0], 0        for i in range(nRows):            if i < lens:                res.append(i)            while res[-1] + add[now] < lens:                if add[now] > 0:                    res.append(res[-1] + add[now])                now ^= 1            add, now = [add[0] - 2, add[1] + 2], 0        return ''.join([s[i] for i in res])s = Solution()print s.convert("A", 2)`

## Longest Palindromic Substring

`class Solution:    # @return a string    def longestPalindrome(self, s):        arr = ['\$', '#']        for i in range(len(s)):            arr.append(s[i])            arr.append('#')        p = [0] * len(arr)        mx, pos, ansp = 0, 0, 0        for i in range(1, len(arr)):            p[i] = min(mx - i, p[2 * pos - i]) if mx > i else 1             while p[i] + i < len(arr) and arr[i + p[i]] == arr[i - p[i]]:                 p[i] += 1            if p[i] + i > mx:                mx, pos = p[i] + i, i            if p[i] > p[ansp]:                ansp = i        st = (ansp - p[ansp] + 1) // 2        return s[st:st + p[ansp] - 1]`

`class Solution:    # @return a ListNode    def addTwoNumbers(self, l1, l2):        nHead, flag = ListNode(0), 0        head = nHead        while flag or l1 or l2:            node = ListNode(flag)            if l1:                 node.val += l1.val                l1 = l1.next            if l2:                 node.val += l2.val                l2 = l2.next            flag = node.val // 10            node.val %= 10            head.next, head = node, node        return nHead.next`

## Longest Substring Without Repeating Characters

`class Solution:    # @return an integer    def lengthOfLongestSubstring(self, s):        dict, ans, p1, p2 = {}, 0, 0, 0        while p2 < len(s):            p = dict.get(s[p2], None)            if p == None:                dict[s[p2]] = p2                p2 += 1                ans = max(ans, p2 - p1)            else:                while p1 <= p:                    dict.pop(s[p1])                    p1 += 1                p1 = p + 1        return ans`

## Median of Two Sorted Arrays

`class Solution:    # @return a float    def findMedianSortedArrays(self, A, B):        totlen = len(A) + len(B)        if (1 & totlen):            return self.findK(A, B, (totlen + 1) / 2)        else:            return (self.findK(A, B, totlen / 2) + self.findK(A, B, totlen / 2 + 1)) / 2.0            def findK(self, A, B, K):        la, lb, pa, pb = len(A), len(B), min(K/2, len(A)), K - min(K/2, len(A))        if (la > lb):            return self.findK(B, A, K)        if (la == 0):            return B[K-1]        if (K == 1):            return min(A[0], B[0])        if A[pa - 1] < B[pb - 1]:            return self.findK(A[pa:], B, K - pa)        elif A[pa - 1] > B[pb - 1]:            return self.findK(A, B[pb:], K- pb)        else:            return A[pa - 1]`

## Two Sum

`class Solution:    # @return a tuple, (index1, index2)    def twoSum(self, num, target):        dict = {}        for i in range(len(num)):            if dict.get(target-num[i], None) == None:                dict[num[i]] = i            else:                return (dict[target-num[i]] + 1, i + 1)`