point the sword to offer

11 、1的个数

~-9的计算步骤：
转二进制：1 1001
计算补码：1 0111
按位取反：0 1000

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        if n >= 0:
            while n:
                count += (n & 1)
                n = (n >> 1)
        else:
            n = ~n
            while n:
                count += (n & 1)
                n = (n >> 1)
            count = 32 - count
        return count

class Solution:
    def NumberOf1(self, num):
        # write code here
        count = 0
        if num < 0:
            return 32 - self.NumberOf1(~num)
        while num:
            num = num & (num-1)
            count += 1
        return count

12、power(x, y)

class Solution:
    def Power(self, base, exponent):
        # write code here
        if exponent == 0:
            return 1
        if exponent < 0:
            temp = self.Power(base, -exponent)
            return 1.0 / temp
        temp = self.Power(base, exponent / 2)
        if temp % 2:
            return temp * temp * base
        else:
            return temp * temp

13、奇数位于偶数前面

基础

class Solution:
    def reOrderArray(self, array):
        # write code here
        even, odd = [], []
        for item in array:
            if item % 2:
                odd.append(item)
            else:
                even.append(item)
        return odd + even

深入：
冒泡排序：

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        for i in range(0, len(array)):
            for j in range(len(array)-1, i, -1):
                if array[j-1] % 2 == 0 and array[j] % 2 == 1:
                    array[j], array[j-1] = array[j-1], array[j]
        return array

14、链表倒数第k个值

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head == None:
            return None
        dummy = ListNode(-1)
        dummy.next = head
        fast, slow = dummy, dummy
        for _ in xrange(k):
            fast = fast.next
            if fast is None:
                return None
        while fast:
            fast, slow = fast.next, slow.next
        return slow

15、反转链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead is None or pHead.next is None:
            return pHead
        p, q = pHead, pHead.next
        p.next = None
        while q:
            temp = q.next
            q.next = p
            p, q = q, temp
        return p

16、合并两个排序链表

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        dummy = ListNode(-1)
        head = dummy
        while pHead1 or pHead2:
            if pHead1 is None:
                dummy.next = ListNode(pHead2.val)
                pHead2, dummy = pHead2.next, dummy.next
                continue
            if pHead2 is None:
                dummy.next = ListNode(pHead1.val)
                pHead1, dummy = pHead1.next, dummy.next
                continue
            if pHead1.val < pHead2.val:
                dummy.next = ListNode(pHead1.val)
                pHead1, dummy = pHead1.next, dummy.next
            else:
                dummy.next = ListNode(pHead2.val)
                pHead2, dummy = pHead2.next, dummy.next
        return head.next

17、判断B树是不是A的子树

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot2 is None or pRoot1 is None:
            return False
        if pRoot2.val == pRoot1.val:
            if self.issubtree(pRoot1,pRoot2):
                return True
        return self.HasSubtree(pRoot1.left, pRoot2) or \
        self.HasSubtree(pRoot1.right, pRoot2)



    def issubtree(self, root1, root2):
        if root2 is None:
            return True
        if root1 is None and root2 is not None:
            return False
        if root1.val == root2.val:
            return self.issubtree(root1.left, root2.left) and \
                   self.issubtree(root1.right, root2.right)

18、二叉树的镜像

class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if root is None:
            return None
        mirroot = TreeNode(root.val)
        self.helper(root, mirroot)
        return mirroot

    def helper(self, root1, root2):
        if root1.right:
            root2.left = TreeNode(root1.right.val)
            self.helper(root1.right, root2.left)
        if root1.left:
            root2.right = TreeNode(root1.left.val)
            self.helper(root1.left, root2.right)

上面的方法一直不通过，题意是要在树本身的基础上进行修改。

class Solution1:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if root is None:
            return None
        root.left, root.right = root.right, root.left
        if root.right:
            self.Mirror(root.right)
        if root.left:
            self.Mirror(root.left)

19、顺时针打印数组

20、包含min函数的栈

class Solution:
    def __init__(self):
        self.stack = []
        self.stack2 = []
        self.minim = float("inf")
    def push(self, node):
        # write code here
        self.stack.append(node)
        if node < self.minim:
            self.minim = node
        self.stack2.append(self.minim)
    def pop(self):
        # write code here
        temp = self.stack.pop()
        self.stack2.pop()
        self.minim = self.stack2[len(self.stack2) - 1]
        return temp
    def top(self):
        # write code here
        return self.stack[len(self.stack)-1]
    def min(self):
        # write code here
        return self.minim

21 栈的压入弹出序列

class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        i = 0
        for item in pushV:
            stack.append(item)
            while stack and stack[-1] == popV[i]:
                stack.pop()
                i += 1
        return stack == []

很容易绕到自己的小思维中，可以设置一个辅助栈，模拟入栈出栈过程。

22 从上往下打印二叉树

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if root is None:
            return []
        current = [root]
        res = []
        while current:
            nextlevel = []
            for node in current:
                res.append(node.val)
                if node.left:
                    nextlevel.append(node.left)
                if node.right:
                    nextlevel.append(node.right)
            current = nextlevel
        return res

23 是否是二叉搜索树的后序遍历

class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence) == 0:
            return False
        return self.helper(sequence)

    def helper(self,sequence):
        if len(sequence) == 0:
            return True
        point = sequence[-1]
        i = 0
        while sequence[i] < point:
            i += 1
        less, more = sequence[:i], sequence[i:-1]
        if any(item < point for item in more):
            return False
        else:
            return self.helper(less) and self.helper(more)

能独立写出来也是比较高兴，后序遍历的特点是最后一个元素是根节点，而二叉搜索树的特点是对于每一棵子树，左节点小于根节点，右节点大于根节点。因此，对一个序列，取出根节点（最后一个元素），则比根节点小的必定是左子树。然后递归遍历每一个子树。需要注意的是右子树序列是sequence[i:-1]，需要去掉根节点。

24 二叉搜索树中和为某一值得路径

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if root is None:
            return []
        self.res = []
        self.helper(root, [], expectNumber)
        return self.res

    def helper(self, root, subres, number):
        if number == root.val and root.left is None and root.right is None:
            subres.append(root.val)
            self.res.append(subres[:])
            subres.pop()
            return 
        if number < 0:
            return
        if root.left:
            subres.append(root.val)
            self.helper(root.left, subres, number-root.val)
            subres.pop()
        if root.right:
            subres.append(root.val)
            self.helper(root.right, subres, number - root.val)
            subres.pop()

这个题用的回溯解，复杂度和内存肯定比较高，较好的解法是

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if not root: return []
        if root.left is None and root.right is None:
            if sum == root.val:
                return [[root.val]]
            else:
                return []
        a = self.pathSum(root.left, sum - root.val) + \
            self.pathSum(root.right, sum - root.val)
        return [[root.val] + i for i in a]

但这种解法比较难想。具体对比分析在 总结中。

25 复杂链表的复制

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        lookup = {}
        current, dummy = pHead, RandomListNode(-1)
        cHead = dummy
        # 复制链表，只复制next
        while current:
            node = RandomListNode(current.label)
            lookup[current] = node
            cHead.next = node
            cHead, current = node, current.next

        # 复制random指针
        cHead, current = dummy.next, pHead
        while current:
            # cHead.random = lookup[current.random]
            cHead.random = lookup.get(current.random）
            cHead, current = cHead.next, current.next
        return dummy.next

上面cHead.random = lookup[current.random]是容易出现键值错误的，而get方法就可以实现安全操作，当不存在或为None会返回空。
可以进一步简化：

class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
    dic = collections.defaultdict(lambda: RandomListNode(0))
    dic[None] = None
    n = head
    while n:
        dic[n].label = n.label
        dic[n].next = dic[n.next]
        dic[n].random = dic[n.random]
        n = n.next
    return dic[head]

26 二叉搜索树与双向链表

将一棵二叉搜索树转换为双向链表，自然而然想到的是中序遍历（递归），中序遍历比较简单，需要注意的是如何保存好第一个元素以供返回以及保存好上一个元素。

class Solution:
    flag = 0
    first = None
    pre = None
    def Convert(self, pRootOfTree):
        # write code here
        if pRootOfTree:
            root = pRootOfTree
            self.Convert(pRootOfTree.left)
            if not self.flag:
                self.first = root
                self.pre = self.first
                self.flag = 1
            else:
                self.pre.right = root
                root.left = self.pre
                self.pre = root
            self.Convert(root.right)
        return self.first

27、字符串的全排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        if ss == '':
            return []
        self.res = set()
        self.helper(list(ss), 0, len(ss))
        return sorted(self.res)

    def helper(self, s, start, end):
        if start > end:
            return
        if start == end:
            self.res.add(''.join(s))
        else:
            for i in range(start, end):
                s[start], s[i] = s[i], s[start]
                self.helper(s, start + 1, end)
                s[start], s[i] = s[i], s[start]



import itertools
class Solution2:
    def Permutation(self, ss):
        # write code here
        result = []
        if not ss:
            return []
        else:
            res = itertools.permutations(ss)
            for i in res:
                if "".join(i) not in result:
                    result.append("".join(i))
        return result

28 、超过一半的数字

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        lookup = {}
        length = len(numbers) / 2
        for item in numbers:
            if lookup.get(item):
                lookup[item] += 1
                if lookup[item] > length:
                    return item
            else:
                lookup[item] = 1
        return 0

简化：

import collections
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        tmp = collections.Counter(numbers)
        x = len(numbers)/2
        for k, v in tmp.items():
            if v > x:
                return k
        return 0

上面的空间复杂度是o(n)，也可以有o（1）的方案，维持两个变量，
https://blog.csdn.net/derrantcm/article/details/46736859

29、最小的k个数

这个题需要结合排序算法进一步总结。涉及到堆排序等知识。
http://www.cnblogs.com/felixfang/articles/3533890.html

30、连续子数组的最大和

动态规划求解，但只需要保存两个参数，一个是前一个元素位置的最大值，另一个是全局的最大值。

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        maxsum, pre_max = float('-inf'), 0
        for item in array:
            if pre_max <= 0:
                pre_max = item
            else:
                pre_max += item
            maxsum = max(pre_max, maxsum)
        return maxsum

31、整数中1出现的次数

参考思路：https://blog.csdn.net/yi_afly/article/details/52012593
对一个数，如 523，首先判断个位上1出现的次数，52 + 1 = 53次，十位上是 5 * 10 + 10 = 60，（注意如果是 513，则是5 * 10 + 3 + 1 = 54)，百位上则是 100，如果是 123则是 23 + 1 = 24。总结下来，逐位判断，还要注意当前位是否是1。

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        res = 0
        base = 1
        temp = n

        while n:
            weight = n % 10
            n /= 10
            res += n * base
            if weight > 1:
                res += base
            elif weight == 1:
                res += temp % base + 1
            base *= 10

        return res

32、把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

一开始肯定就是想到全排列，然后逐个寻找，全排列需要好好理解。回溯算法的理解。

class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if numbers == []:
            return ''
        numbers = map(str, numbers)
        self.minnum = '9'
        self.helper(numbers,  0)
        return int(self.minnum)

    def helper(self, numbers, index):
        if index == len(numbers):
            temp = ''.join(numbers)
            if temp < self.minnum:
                self.minnum = temp
            return
        for i in range(index, len(numbers)):
            numbers[index], numbers[i] = numbers[i], numbers[index]
            self.helper(numbers, index + 1)
            numbers[index], numbers[i] = numbers[i], numbers[index]

上面的方法肯定不是最优，因为全部搜索了一遍。

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ""
        lmb = lambda n1, n2:int(str(n1)+str(n2))-int(str(n2)+str(n1))
        array = sorted(numbers, cmp=lmb)
        return ''.join([str(i) for i in array])

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ""
        num=map(str,numbers)
        num.sort(lambda x,y:cmp(x+y,y+x))
        return ''.join(num)

33、丑数

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index == 0:
            return 0
        res = [1 for _ in range(index)]
        k2 = k3 = k5 = 0
        for i in range(1, index):
            res[i] = min(res[k2] * 2, res[k3] * 3, res[k5] * 5)
            if res[i] == res[k2] * 2:
                k2 += 1
            if res[i] == res[k3] * 3:
                k3 += 1
            if res[i] == res[k5] * 5:
                k5 += 1
        return res[-1]

一开始写时不是三个if，容易写成if elif else结构，这种写法是错误的，因为会出现两个6， 23 = 32 = 6，为了避免这种情况，需要用三个if。

34、第一个出现一次的字符

class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        count = [0 for _ in range(256)]
        for char in s:
            count[ord(char)] += 1
        for i, char in enumerate(s):
            if count[ord(char)] == 1:
                return i
        return -1

方法比较朴素，还没看别人的求解思路。上面的方法也是书中推荐的方法。

35、数组中逆序对

class Solution:
    def InversePairs(self, data):
        # write code here
        self.count = 0
        self.merge_sorted(data)
        return self.count

    def merge_sorted(self,nums):
        if len(nums) == 1:
            return nums
        mid = len(nums) / 2
        left = self.merge_sorted(nums[:mid])
        right = self.merge_sorted(nums[mid:])
        return self.sort(left, right)

    def sort(self, left, right):
        global count
        m, n = len(left), len(right)
        array = []
        i, j = 0, 0
        while i < m and j < n:
            if left[i] <= right[j]:
                array.append(left[i])
                i += 1
            else:
                array.append(right[j])
                j += 1
                self.count += len(left) - i
        array.extend(left[i:])
        array.extend(right[j:])
        return array

leetcode 315

36 两个链表的第一个公共节点

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        length1, length2 = 0, 0
        p1, p2 = pHead1, pHead2
        while p1:
            length1 += 1
            p1 = p1.next
        while p2:
            length2 += 1
            p2 = p2.next
        if length1 > length2:
            while length2 < length1:
                pHead1 = pHead1.next
                length1 -= 1
        else:
            while length1 < length2:
                pHead2 = pHead2.next
                length2 -= 1
        while  pHead1 is not pHead2:
            pHead1, pHead2 = pHead1.next, pHead2.next
        return pHead1

主要思路是先统计数组长度，因为如果有公共节点，则公共节点之后的元素是相同的，如下图

image.png

上面链表长度是5，下面链表长度是4，则如果长度相同，即上面从2开始遍历，下面从4开始遍历，则就会同节奏找到公共节点6.

37、数字在排序数组中出现的次数

# -*- coding:utf-8 -*-

class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if data == []:
            return 0
        first = self.getfirst(data,k)
        last = self.getlast(data, k)
        if first == -1 and last == -1:
            return 0
        if first == -1 or last == -1:
            return 1
        else:
            return last - first + 1

    def getfirst(self,data,k):
        start, end = 0, len(data) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if data[mid] < k:
                start = mid + 1
            else:
                end = mid
        if data[start] == k:
            return start
        if data[end] == k:
            return end
        return -1

    def getlast(self,data, k):
        start, end = 0, len(data) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if data[mid] > k:
                end = mid - 1
            else:
                start = mid
        if data[end] == k:
            return end
        if data[start] == k:
            return start
        return -1

s = Solution()
print s.GetNumberOfK([1,2,3,5,5,5,7], 5)

40、数组中只出现一次的元素

一个数组，除了两个元素以外，其他元素都出现两次，求这两个元素。

class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        sum = 0
        for item in array:
            sum ^= item
        bitset = 1
        while (sum & bitset) == 0:
            bitset = (bitset << 1)
        array1, array2 = [], []
        for item in array:
            if (item & bitset) == 0:
                array1.append(item)
            else:
                array2.append(item)
        num1, num2 = 0, 0
        for a in array1:
            num1 ^= a
        for b in array2:
            num2 ^= b
        return num1, num2

如果说求只出现一次的单个元素，很好求，直接所有元素相异或，但是有两个不同，自然而然会想到如何分成两个不同数组，每个数组中包含一个不同，其他的都出现两次。

41、和为s的连续正整数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

这道题也算比较重要，两个指针的应用，不是很难，但是很多细节需要理清楚。

class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        res = []
        plow, phigh = 1, 2
        while plow < phigh:
            sum = (plow + phigh) * (phigh - plow + 1) >> 1
            if sum < tsum:
                phigh += 1
            elif sum > tsum:
                plow += 1
            else:
                temp = [item for item in range(plow,phigh+1)]
                res.append(temp)
                plow += 1
        return res

42、和为s的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        start, end = 0, len(array) - 1
        min_produce = float('inf')
        num1, num2 = 0, 0
        while start < end:
            if array[start] + array[end] > tsum:
                end -= 1
            elif array[start] + array[end] < tsum:
                start += 1
            else:
                if array[start] * array[end] < min_produce:
                    min_produce = array[start] * array[end]
                    num1, num2 = array[start], array[end]
                end, start = end - 1, start + 1
        return [] if num1 == num2 else [num1, num2]

43、左旋转字符串

class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        if s == '':
            return ''
        length = len(s)
        n %= length
        return s[n:] + s[:n]

48、不用加减乘除做加法

class Solution:
    def Add(self, num1, num2):
        # write code here
        sum = num1 ^ num2
        carry = (num1 & num2) << 1
        while carry:
            carry, sum = ((sum & carry) << 1), sum ^ carry
        return sum

上面的方法超时了，但是思路没有问题，首先用异或，表示两数相加，不考虑进位。两数相与再左移一位，表示进位；上面两步的结果再相加，表示加上进位，但是可能还有进位，因此需要循环，直到进位为0，表示完成。

49、字符串转换为整数

class Solution:
    def StrToInt(self, s):
        # write code here
        if s == '':
            return 0
        i, flag = 0, 1
        while s[i] == ' ':
            i += 1
        if s[i] == '-':
            flag = -1
            i += 1
        elif s[i] == '+':
            i += 1
        res = 0
        for j in range(i,len(s)):
            if s[j] not in '0123456789':
                return 0
            else:
                res = res * 10 + ord(s[j]) - ord('0')
        return flag * res

这道题leetcode上也有，算是比较熟悉了，要注意的地方有，1、去空格；2、注意正负号；3、考虑异常，主要有两个，一是输入为空，二是输入只有’-‘，所以用 if elif。

50、数组中重复的值

class Solution1:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        lookup = {}
        for item in numbers:
            if lookup.get(item):
                duplication[0] = item
                return True
            else:
                lookup[item] = 1
        return False

51、构建乘积数组

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。

image.png

这道题比较关键的一点在于 不要重复计算，如果每行都从左到右计算，中间很多过程都是浪费的。
可以分为两个部分，分别为上三角和下三角计算。

class Solution:
    def multiply(self, A):
        # write code here
        if len(A) < 2:
            return A
        length = len(A)
        B = [1 for _ in range(length)]
        tempB = [1 for _ in range(length)]
        for i in xrange(1, length):
            B[i] = B[i-1] * A[i-1]
        for j in xrange(length-2, -1, -1):
            tempB[j] = tempB[j+1] * A[j+1]
        for i in xrange(length):
            B[i] *= tempB[i]
        return B

52、正则表达式匹配

请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
 在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        if s is None:
            return
        return self.isMatch(s, 0, pattern, 0)

    def isMatch(self, s, sp, pattern, pp):
        if sp == len(s) and pp == len(pattern):
            return True
        if pp >= len(pattern):
            return False

        if pp < len(pattern) - 1 and pattern[pp+1] == '*':
            if (sp < len(s) and s[sp] == pattern[pp]) or pattern[pp] == '.':
                return self.isMatch(s, sp, pattern, pp+2) or \
                       self.isMatch(s, sp+1, pattern, pp+2) or \
                       self.isMatch(s, sp+1, pattern, pp)
            else:
                return self.isMatch(s, sp, pattern, pp + 2)
        if sp >= len(s):
            return False

        if s[sp] == pattern[pp] or pattern[pp] == '.':
            return self.isMatch(s, sp + 1, pattern, pp + 1)
        return False
s = Solution()
print s.match('bcbbabab', '.*a*a')

上面大部分没有问题，但是会出现递归深度超出的限制，如上面的测试用例。

class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        if len(s) == 0 and len(pattern) == 0:
            return True
        if len(s) > 0 and len(pattern) == 0:
            return False
        if len(pattern) > 1 and pattern[1] == '*':
            if len(s) > 0 and (s[0] == pattern[0] or pattern[0] == '.'):
                return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern)
            else:
                return self.match(s, pattern[2:])
        if len(s) > 0 and (pattern[0] == '.' or pattern[0] == s[0]):
            return self.match(s[1:], pattern[1:])
        return False

上面两个解法思路差不多，为什么性能相差这么多。

53、表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

class Solution1:
    # s字符串
    def isNumeric(self, s):
        # write code here
        self.flag1, self.flag2 = 0, 0
        start = 0
        if s[0] in '+-':
            start += 1
        while start < len(s):
            if s[start] in '+-' and s[start-1] in 'eE':
                start += 1
            if s[start] in '1234567890':
                start += 1
            elif s[start] in 'eE':
                if self.flag1 == 1:
                    return False
                else:
                    self.flag1 = 1
                    start += 1
            elif s[start] == '.' and start > 0 and s[start-1] in '+-1234567890':
                if self.flag2 == 1 or self.flag1 == 1:
                    return False
                else:
                    self.flag2 = 1
                    start += 1
            else:
                return False
        if s[-1] in 'eE.+-':
            return False
        return True

调用内置函数：

class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        try :
            p = float(s)
            return True
        except:
            return False

54、删除链表中重复的节点

class Solution1:
    def deleteDuplication(self, pHead):
        # write code here
        if pHead is None or pHead.next is None:
            return pHead
        dummy = ListNode(-1)
        dummy.next = pHead
        pre, head = dummy, dummy
        while pHead and pHead.next:
            if pHead.val != pHead.next.val:
                pHead = pHead.next
                pre = pre.next
            else:
                while pHead and pHead.next and pHead.val == pHead.next.val:
                    pHead = pHead.next
                pHead = pHead.next
                pre.next = pHead
        return dummy.next

这个题要注意的是重复的元素都删除，不用保留一个。

55、二叉树的下一个节点

寻找二叉树的下一个节点。

class Solution:
    def GetNext(self, pNode):
        # write code here
        if pNode is None:
            return None
        if pNode.right:
            temp = pNode.right
            while temp.left:
                temp = temp.left
            return temp
        temp = pNode
        while temp.next and temp != temp.next.left:
            temp = temp.next
        return temp.next

class Solution1:
    def GetNext(self, pNode):
        # write code here
        if pNode is None:
            return None
        if pNode.right:
            temp = pNode.right
            while temp.left:
                temp = temp.left
            return temp
        temp = pNode
        while temp.next:
            if temp is temp.next.left:
                   return temp.next
            temp = temp.next
        return temp.next

56、对称二叉树

class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if pRoot is None:
            return True
        return self.helper(pRoot.left, pRoot.right)

    def helper(self, root1, root2):
        if root1 is None and root2 is None:
            return True
        if root1 is None or root2 is None:
            return False
        return root1.val == root2.val and self.helper(root1.left, root2.right) and \
               self.helper(root1.right, root2.left)

57、之字形打印二叉树

class Solution:
    def Print(self, pRoot):
        # write code here
        if pRoot is None:
            return []
        current = [pRoot]
        flag = 1
        res = []
        while current:
            nextlevel, subres = [], []
            for node in current:
                subres.append(node.val)
                if node.left:
                    nextlevel.append(node.left)
                if node.right:
                    nextlevel.append(node.right)
            current = nextlevel
            res.append(subres if flag else subres[::-1])
            flag = 1 if flag == 0 else 0
        return res

58、二叉树打印多行

class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot is None:
            return []
        current = [pRoot]
        res = []
        while current:
            nextlevel, subres = [], []
            for node in current:
                subres.append(node.val)
                if node.left:
                    nextlevel.append(node.left)
                if node.right:
                    nextlevel.append(node.right)
            current = nextlevel
            res.append(subres)
        return res

59、序列化和反序列化二叉树

class Solution:
    def Serialize(self, root):
        # write code here
        self.pre = []
        self.inorder = []
        self.preFunc(root)
        self.inorderFunc(root)
        return (self.pre, self.inorder)
        
    def preFunc(self,root):
        if root:
            self.pre.append(root.val)
            self.preFunc(root.left)
            self.preFunc(root.right)
            
    def inorderFunc(self, root):
        if root:
            self.inorderFunc(root.left)
            self.inorder.append(root.val)
            self.inorderFunc(root.right)
    
    def Deserialize(self, s):
        # write code here
        preorder, inorder = s[0], s[1]
        return self.buildTree(preorder, inorder)
    
    def buildTree(self,preorder, inorder):
        if inorder:
            index = inorder.index(preorder[0])
            del preorder[0]
            node = TreeNode(inorder[index])
            node.left = self.buildTree(preorder, inorder[:index])
            node.right = self.buildTree(preorder, inorder[index+1:])
            return node

最先想到的是最简单的由中序和前序遍历构造二叉树，其实还可以用自己特有的方式。

60、二叉搜索树的第k个节点

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        if k <= 0:
            return
        self.pre = []
        self.preorder(pRoot)
        if k > len(self.pre):
            return
        return self.pre[k-1]

    def preorder(self, root):
        if root:
            self.preorder(root.left)
            self.pre.append(root)
            self.preorder(root.right)

上面是最基本的方法，先中序遍历，然后取第k个元素。但其实有很多操作都是无用。

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        if k <= 0:
            return
        self.count, self.node = k, None
        self.preorder(pRoot)
        return self.node
                
    def preorder(self, root):
        if root and self.count:
            self.preorder(root.left)
            self.count -= 1
            if self.count == 0:
                self.node = root
            self.preorder(root.right)

上面的方法则不用全部遍历，但最终运行时间和空间消耗都不如第一种方法。可能大数据集适用。

61、数据流中的中位数

class Solution:
    sort_list = []
    length = 0

    def Insert(self, num):
        self.sort_list.append(num)
        self.sort_list.sort()
        self.length += 1

    def GetMedian(self,data):
        # write code here
        if self.length % 2:
            return self.sort_list[self.length//2]
        else:
            return self.sort_list[self.length//2] * 0.5 + self.sort_list[self.length//2-1] * 0.5

s = Solution()
for item in [3, 4, 5, 72, 6, 2]:
    s.Insert1(item)
    print s.sort_list

备注：
如何往一个有序的列表中插入数值。

    def Insert1(self, num):
        # write code here
        start, end = 0, self.length - 1
        while start < end:
            mid = start + (end - start) >> 1
            if self.sort_list[mid] > num:
                end = mid
            else:
                start = mid + 1
        self.sort_list.insert(start, num)
        self.length += 1