剑指offer python版本

左手的ㄟ右手 2022-05-20 03:54 187阅读 0赞

1.  二叉树的镜像
2.  链表中环的入口结点
3.  删除链表中重复的结点
4.  从尾到头打印链表
5.  斐波那契数列
6.  跳台阶
7.  变态跳台阶
8.  矩形覆盖
9.  把字符串转换成整数
10. 平衡二叉树
11. 和为S的连续正数序列
12. 左旋转字符串
13. 数字在排序数组中出现的次数
14. 数组中只出现一次的数字
15. 翻转单词顺序列
16. 二叉树的深度
17. 和为S的两个数字
18. 顺时针打印矩阵
19. 二叉树的下一个结点
20. 对称的二叉树
21. 把二叉树打印成多行
22. 按之字形顺序打印二叉树
23. 序列化二叉树
24. 二叉搜索树的第k个结点
25. 数据流中的中位数
26. 重建二叉树
27. 滑动窗口的最大值
28. 用两个栈实现队列
29. 旋转数组的最小数字
30. 丑数
31. 两个链表的第一个公共结点
32. 第一个只出现一次的字符位置
33. 数组中的逆序对
34. 连续子数组的最大和
35. 最小的K个数
36. 数组中出现次数超过一半的数字
37. 整数中1出现的次数（从1到n整数中1出现的次数）
38. 把数组排成最小的数
39. 数组中重复的数字
40. 构建乘积数组
41. 二维数组中的查找
42. 扑克牌顺子
43. 孩子们的游戏(圆圈中最后剩下的数)
44. 正则表达式匹配
45. 表示数值的字符串
46. 字符流中第一个不重复的字符
47. 替换空格
48. 矩阵中的路径
49. 机器人的运动范围
50. 求1+2+3+…+n
51. 不用加减乘除做加法
52. 二叉搜索树与双向链表
53. 复杂链表的复制
54. 字符串的排列
55. 二进制中1的个数
56. 链表中倒数第k个结点
57. 合并两个排序的链表
58. 反转链表
59. 树的子结构
60. 数值的整数次方
61. 调整数组顺序使奇数位于偶数前面
62. 包含min函数的栈
63. 二叉树中和为某一值的路径
64. 从上往下打印二叉树
65. 二叉搜索树的后序遍历序列
66. 栈的压入、弹出序列

(1) 二叉树的镜像（Symmetric Tree）  
[牛客网链接][Link 1]  
[Leetcode链接][Leetcode]

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

（2）[链表中环的入口结点][Link 2]  
[Leetcode 142. Linked List Cycle II][]  
寻找环的入口结点  
这题是[Leetcode 141. Linked List Cycle][]的扩展。  
判断是否存在环用fast和slow两个指针，从head开始，一个走一步，一个走两步，如果最终到达同一个结点，则说明存在环。

class Solution(object):
        def hasCycle(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            if head == None or head.next == None:
                return False
            slow = fast = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    return True
            return False

而寻找环的入口，假设入口结点距离头结点a个单位，fast和slow相遇在距离入口结点b个单位的位置，环剩下的长度为c，则有a+b+c+b = 2\*(a+b) -> a = c  
因此，在重合时候，将fast置为head，再一步一步地走，当与slow重合时的结点即为入口结点

class Solution:
        def EntryNodeOfLoop(self, pHead):
            # write code here
            if pHead== None or pHead.next == None:
                return None
            fast = slow = pHead
            while(fast and fast.next):
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    fast = pHead
                    while(fast!=slow):
                        fast = fast.next
                        slow = slow.next
                    return fast
            return None

（3） 删除链表中重复的结点  
[删除链表中重复的结点][Link 3]  
[Leetcode. 82. Remove Duplicates from Sorted List II][]  
用flag来标记当前的结点是否为重复结点

class Solution:
        def deleteDuplication(self, pHead):
            # write code here
            pos = pHead
            ret = ListNode(-1)
            tmp = ret
            flag = False
            while(pos and pos.next):
                if pos.val == pos.next.val:
                    flag = True
                    pos.next = pos.next.next
                else:
                    if flag:
                        flag = False
                    else:
                        tmp.next = ListNode(pos.val)
                        tmp = tmp.next
                    pos = pos.next
            if pos and flag==False:
                tmp.next = ListNode(pos.val)
            return ret.next

（4）从头到尾打印链表  
[从头到尾打印链表][Link 4]

class Solution:
        # 返回从尾部到头部的列表值序列，例如[1,2,3]
        def printListFromTailToHead(self, listNode):
            # write code here
            ret = []
            head = listNode
            while(head):
                ret.append(head.val)
                head = head.next
            ret.reverse()
            return ret

（5）求斐波那契数列的第n项  
[斐波那契数列][Link 5]

# -*- coding:utf-8 -*-
    class Solution:
        def Fibonacci(self, n):
            if n == 0:
                return 0
            if n==1 or n==2:
                return 1
            memories = [1,1]
            for i in range(n-2):
                memories.append(memories[-1]+memories[-2])
            return memories[-1]

（6）[跳台阶][Link 6]  
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。  
dp\[n\]=dp\[n−1\]\+dp\[n−2\]dp\[n\]=dp\[n−1\]+dp\[n−2\]

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloor(self, number):
            # write code here
            '''
            n = 1 : 1 
            n = 2 : 1+1 = 2
            n = 3 : dp[n-2]+dp[n-1]
            '''
            if number == 1 or number == 2:
                return number
            dp = [1,2]
            for i in range(number-2):
                dp.append(dp[-1]+dp[-2])
            return dp[-1]

（7）[变态跳台阶][Link 7]  
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。  
思考：在dp\[n\] = dp\[n-1\] + dp\[n-2\] + .. + dp\[1\] + 1(直接跳n)步骤  
即dp\[n\]=∑n−1i=1dp\[i\]\+1dp\[n\]=∑i=1n−1dp\[i\]+1

class Solution:
        def jumpFloorII(self, number):
            # write code here
            if number == 1 or number == 2:
                return number
            ret = sum_ = 3
            for i in range(number-2):
                ret = sum_+1
                sum_+=ret
            return ret

（8）[矩形覆盖][Link 8]  
我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？  
思考： 2\*1 1 种； 2\*2 2种 2\*3 3种 2\*4 5种  
dp\[n\]=dp\[n−1\]\+dp\[n−2\]dp\[n\]=dp\[n−1\]+dp\[n−2\]

# -*- coding:utf-8 -*-
    class Solution:
        def rectCover(self, number):
            # write code here
    
            if number<=2:
                return number
            dp = [1,2]
            for i in range(number-2):
                dp.append(dp[-1]+dp[-2])
            return dp[-1]

（9）把字符串转换成整数  
[把字符串转换成整数][Link 9]  
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0  
思考：如果有正负号，需要在数字之前，出现其他字符或者字符串为空都非法返回0

class Solution:
        def StrToInt(self, s):
            # write code here
            flag = True
            pos = 1
            ret = None
            if s=='':
                return 0
            for i in s:
                if i=='+' or i=='-':
                    if flag:
                        pos = -1 if i=='-' else 1
                        flag = False
                    else:
                        return 0
                elif i>='0' and i<='9':
                    flag = False
                    if ret == None:
                        ret = int(i)
                    else:
                        ret = ret*10+int(i)
                else:
                    return 0
            return pos*ret if ret else 0

（10）[平衡二叉树的判断][Link 10]  
思考：BST的定义为|height(lefttree)−height(righttree)|<=1|height(lefttree)−height(righttree)|<=1，原问题拆分为计算树高度和判断高度差

class Solution:
        def Treeheight(self,pRoot):
            if pRoot == None:
                return 0
            if pRoot.left == None and pRoot.right == None:
                return 1
            lh = self.Treeheight(pRoot.left)
            rh = self.Treeheight(pRoot.right)
            return max(rh,lh)+1
    
        def IsBalanced_Solution(self, pRoot):
            # write code here
            if pRoot == None:
                return True
            return abs(self.Treeheight(pRoot.left)-self.Treeheight(pRoot.right))<=1

（11）[和为S的连续正数序列][S]  
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序  
思考：S%奇数==0 或者S%偶数==偶数／2 就说明有这个连续序列，但是注意是正数序列，可能会出现越界情况

class Solution:
        def FindContinuousSequence(self, tsum):
            # write code here
            k = 2
            ret = []
            for k in range(2,tsum):
                if k%2==1 and tsum%k==0:
                    tmp = []
                    mid = tsum/k
                    if mid-k/2>0:
                        for i in range(mid-k/2,mid+k/2+1):
                            tmp.append(i)
                        ret.append(tmp[:])
                elif k%2==0 and (tsum%k)*2==k:
                    mid = tsum/k
                    tmp = []
                    if mid-k/2+1>0:
                        for i in range(mid-k/2+1,mid+k/2+1):
                            tmp.append(i)
                        ret.append(tmp[:])
            ret.sort()
            return ret

（12）[左旋转字符串][Link 11]  
对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。  
思考：需要先K= K%len(S)

# -*- coding:utf-8 -*-
    class Solution:
        def LeftRotateString(self, s, n):
            # write code here
            if s == '':
                return s
            n = n%len(s)
            return s[n:]+s[0:n]

（13）数字在排序数组中出现的次数  
[数字在排序数组中出现的次数][Link 12]  
思考：原来是可以用hash做的，但是因为是排序数组，所以可以用二分查找

# -*- coding:utf-8 -*-
    class Solution:
        def GetNumberOfK(self, data, k):
            # write code here
            start = 0
            end = len(data)-1
            while(start<=end):
                mid = (start+end)/2
                if data[mid]==k:
                    cnt = 0
                    tmp = mid
                    while(tmp>=0 and data[tmp]==k):
                        cnt+=1
                        tmp-=1
                    tmp = mid+1
                    while(tmp<len(data) and data[tmp]==k):
                        cnt+=1
                        tmp+=1
                    return cnt
                elif data[mid]>k:
                    end = mid-1
                else:
                    start = mid+1
            return 0

（14）[数组中只出现一次的数字][Link 13]  
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字  
思考：用hash；或者位运算  
首先利用0 ^ a = a; a^a = 0的性质  
两个不相等的元素在位级表示上必定会有一位存在不同，  
将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果，  
据异或的结果1所在的最低位，把数字分成两半，每一半里都还有一个出现一次的数据和其他成对出现的数据,  
问题就转化为了两个独立的子问题“数组中只有一个数出现一次，其他数都出现了2次，找出这个数字”。

class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here
            ans,a1,a2,flag= 0,0,0,1
            for num in array:
                ans = ans ^ num
            while(ans):
                if ans%2 == 0:
                    ans = ans >>1 
                    flag = flag <<1
                else:
                    break
            for num in array:
                if num & flag:
                    a1 = a1 ^ num
                else:
                    a2 = a2 ^ num
            return a1,a2

（15）[翻转单词顺序列][Link 14]

# -*- coding:utf-8 -*-
    class Solution:
        def ReverseSentence(self, s):
            # write code here
            ret = s.split(" ")
            ret.reverse()
            return ' '.join(ret)

（16）[二叉树的深度][Link 15]

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def TreeDepth(self, pRoot):
            # write code here
            if pRoot == None:
                return 0
            if pRoot.left == None and pRoot.right==None:
                return 1
            return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1

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

# -*- coding:utf-8 -*-
    class Solution:
        def FindNumbersWithSum(self, array, tsum):
            # write code here
            memorys= {}
            ret = []
            for num in array:
                if tsum-num in memorys:
                    if ret == []:
                        ret = [tsum-num,num]
                    elif ret and ret[0]*ret[1]>(tsum-num)*num:
                        ret = [tsum-num,num]
                else:
                    memorys[num] = 1
            return ret

（18）[顺时针打印矩阵][Link 16]

# -*- coding:utf-8 -*-
    class Solution:
        # matrix类型为二维列表，需要返回列表
        def printMatrix(self, matrix):
            # write code here
            m=len(matrix)
            ans=[]
            if m==0:
                return ans
            n=len(matrix[0])
            #ans = [[0 for i in range(n)] for j in range(n)]
            #print ans
            upper_i =0;lower_i=m-1;left_j=0;right_j=n-1
            num=1
            i=0;j=0
            right_pointer=1
            down_pointer=0
            while(num<=m*n):
                ans.append(matrix[i][j])
                if right_pointer==1:
                    if j<right_j:
                        j=j+1
                    else:
                        right_pointer=0
                        down_pointer=1
                        upper_i = upper_i+1
                        i = i+1
                elif down_pointer == 1:
                    if i<lower_i:
                        i = i+1
                    else:
                        right_pointer=-1
                        down_pointer=0
                        right_j = right_j -1
                        j = j-1
                elif right_pointer ==-1:
                    if j > left_j:
                        j=j-1
                    else:
                        right_pointer=0
                        down_pointer=-1
                        lower_i =lower_i-1
                        i = i-1
                elif down_pointer == -1:
                    if i > upper_i:
                        i=i-1
                    else:
                        right_pointer=1
                        down_pointer=0
                        left_j = left_j +1
                        j = j+1
                num=num+1
            return ans

（19）\* 二叉树的下一个结点  
[二叉树的下一个结点][Link 17]  
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。  
思路：中序遍历的顺序为LVR  
则有以下三种情况：  
a. 如果该结点存在右子结点，那么该结点的下一个结点是右子结点树上最左子结点  
b. 如果该结点不存在右子结点，且它是它父结点的左子结点，那么该结点的下一个结点是它的父结点  
c. 如果该结点既不存在右子结点，且也不是它父结点的左子结点，则需要一路向祖先结点搜索，直到找到一个结点，该结点是其父亲结点的左子结点。如果这样的结点存在，那么该结点的父亲结点就是我们要找的下一个结点。

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

（20）[对称的二叉树][Link 18]  
[Leetcode 101. Symmetric Tree][]  
判断一棵树是不是左右对称的树

class Solution:
        def Symmetrical(self,Lnode,Rnode):
            if Lnode == None and Rnode == None:
                return True
            if Lnode and Rnode:
                return Lnode.val == Rnode.val and self.Symmetrical(Lnode.right,Rnode.left) and self.Symmetrical(Lnode.left,Rnode.right)
            else:
                return False
        def isSymmetrical(self, pRoot):
            # write code here
            if pRoot == None:
                return True
            return self.Symmetrical(pRoot.left,pRoot.right)

（21）[把二叉树打印成多行][Link 19]  
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

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

（22）[之字形打印二叉树][Link 20]

class Solution:
        def Print(self, pRoot):
            # write code here
            if pRoot == None:
                return []
            stack = [pRoot]
            step = 1
            ret = []
            while(stack):
                tmpstack = []
                tmp = []
                for node in stack:
                    tmp+=[node.val]
                    if node.left:
                        tmpstack.append(node.left)
                    if node.right:
                        tmpstack.append(node.right)
                if step%2==0:
                    tmp.reverse()
                ret.append(tmp)
                step += 1
                stack = tmpstack[:]
            return ret

（23）\* 序列化和反序列化二叉树  
[序列化和反序列化二叉树][Link 21]  
[Serialize and Deserialize Binary Tree][]

class Solution:
        def Serialize(self, root):
            # write code here
            def doit(node):
                if node:
                    vals.append(str(node.val))
                    doit(node.left)
                    doit(node.right)
                else:
                    vals.append('#')
            vals = []
            doit(root)
            return ' '.join(vals)
    
        def Deserialize(self, s):
            # write code here
            def doit():
                val = next(vals)
                if val == '#':
                    return None
                node = TreeNode(int(val))
                node.left = doit()
                node.right = doit()
                return node
            vals = iter(s.split())
            return doit()

（24） \* 数据流中的中位数  
[数据流中的中位数][Link 22]  
[Find Median from Data Stream][]

from heapq import *
    class MedianFinder:
    
        def __init__(self):
            self.heaps = [], []
    
        def addNum(self, num):
            small, large = self.heaps
            heappush(small, -heappushpop(large, num))
            if len(large) < len(small):
                heappush(large, -heappop(small))
    
        def findMedian(self):
            small, large = self.heaps
            if len(large) > len(small):
                return float(large[0])
            return (large[0] - small[0]) / 2.0

（25）\* 二叉平衡树中的第k小数  
[二叉搜索树中的第k大结点][k]  
[Leetcode 230. Kth Smallest Element in a BST][]  
思路：BST的中序遍历就是一个有序数组，需要注意到Leetcode中限制了k在\[1,树结点个数\]而牛客网没有，所以需要考虑k的值有没有超出

class Solution:
        # 返回对应节点TreeNode
        def KthNode(self, pRoot, k):
            # write code here
            stack = []
            node = pRoot
            while node:
                stack.append(node)
                node = node.left
            cnt = 1
            while(stack and cnt<=k):
                node = stack.pop()
                right = node.right
                while right:
                    stack.append(right)
                    right = right.left
                cnt+=1
            if node and k==cnt-1:
                return node
            return None

（26）[重建二叉树][Link 23]  
[Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal][]  
根据先序、中序来构建二叉树

class Solution(object):
        def buildTree(self, pre, tin):
            """
            :type preorder: List[int]
            :type inorder: List[int]
            :rtype: TreeNode
            """
            if pre==[]:
                return None
            val = pre[0]
            idx = tin.index(val)
            ltin = tin[0:idx]
            rtin = tin[idx+1:]
            lpre = pre[1:1+len(ltin)]
            rpre = pre[1+len(ltin):]
            root = TreeNode(val)
            root.left = self.buildTree(lpre,ltin)
            root.right = self.buildTree(rpre,rtin)
            return root

[Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal][]  
根据中序和后序构建二叉树

class Solution(object):
        def buildTree(self, inorder, postorder):
            """
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            """
            if postorder == []:
                return None
            val = postorder[-1]
            idx = inorder.index(val)
            lin = inorder[0:idx]
            rin = inorder[idx+1:]
            lpos = postorder[0:len(lin)]
            rpos = postorder[len(lin):-1]
            root = TreeNode(val)
            root.left = self.buildTree(lin,lpos)
            root.right = self.buildTree(rin,rpos)
            return root

（27）[滑动窗口的最大值][Link 24]  
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{4,4,6,6,6,5\}； 针对数组\{2,3,4,2,6,2,5,1\}的滑动窗口有以下6个： \{\[2,3,4\],2,6,2,5,1\}， \{2,\[3,4,2\],6,2,5,1\}， \{2,3,\[4,2,6\],2,5,1\}， \{2,3,4,\[2,6,2\],5,1\}， \{2,3,4,2,\[6,2,5\],1\}， \{2,3,4,2,6,\[2,5,1\]\}。  
思考：假设当前窗口起始位置为start,结束位置为end，我们要构造一个stack, 使得stack\[0\]为区间\[start,end\]的最大值。

# -*- coding:utf-8 -*-
    class Solution:
        def maxInWindows(self, num, size):
            # write code here
            if size == 0:
                return []
            ret = []
            stack = []
            for pos in range(len(num)):
                while (stack and stack[-1][0] < num[pos]):
                    stack.pop()
                stack.append((num[pos], pos))
                if pos>=size-1:
                    while(stack and stack[0][1]<=pos-size):
                        stack.pop(0)
                    ret.append(stack[0][0])
            return ret

(28) [用两个栈实现队列][Link 25]  
思考：栈FILO，队列FIFO

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
        def push(self, node):
            # write code here
            self.stack1.append(node)
    
        def pop(self):
            # return xx
            if len(self.stack2):
                return self.stack2.pop()
            while(self.stack1):
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

(29) [旋转数组的最小数字][Link 26]  
思考：二分判断

# -*- coding:utf-8 -*-
    class Solution:
        def minNumberInRotateArray(self, rotateArray):
            # write code here
            if rotateArray == []:
                return 0
            _len = len(rotateArray)
            left = 0
            right = _len - 1
            while left <= right:
                mid = int((left + right) >> 1)
                if rotateArray[mid]<rotateArray[mid-1]:
                    return rotateArray[mid]
                if rotateArray[mid] >= rotateArray[right]:
                    # 说明在【mid，right】之间
                    left = mid + 1
                else:
                    # 说明在【left，mid】之间
                    right = mid - 1
            return rotateArray[mid]

（30）[丑数][Link 27]  
只包含因子2、3和5的数称作丑数（Ugly Number），求按从小到大的顺序的第N个丑数。  
思路：heap

# -*- coding:utf-8 -*-
    import heapq
    class Solution:
        def GetUglyNumber_Solution(self, index):
            # write code here
            if index<1:
                return 0
            heaps = []
            heapq.heappush(heaps,1)
            lastnum = None
            idx = 1
            while(idx<=index):
                curnum = heapq.heappop(heaps)
                while(curnum==lastnum):
                    curnum = heapq.heappop(heaps)
                lastnum = curnum
                idx+=1
                heapq.heappush(heaps,curnum*2)
                heapq.heappush(heaps,curnum*3)
                heapq.heappush(heaps,curnum*5)
            return lastnum

（31）[两个链表的第一个公共结点][Link 28]  
思考：设链表pHead1的长度为a,到公共结点的长度为l1；链表pHead2的长度为b,到公共结点的长度为l2，有a+l2 = b+l1

class Solution:
        def FindFirstCommonNode(self, pHead1, pHead2):
            # write code here
            if pHead1== None or pHead2 == None:
                return None
            pa = pHead1
            pb = pHead2 
            while(pa!=pb):
                pa = pHead2 if pa is None else pa.next
                pb = pHead1 if pb is None else pb.next
            return pa

(32) [第一个只出现一次的字符][Link 29]  
思考：hash加队列

# -*- coding:utf-8 -*-
    class Solution:
        def FirstNotRepeatingChar(self, s):
            # write code here
            queue = []
            memories = dict()
            for idx,char in enumerate(s):
                if char not in memories:
                    queue.append(idx)
                    memories[char]=0
                memories[char]+=1
                while(queue and memories[s[queue[0]]]>1):
                    queue.pop(0)
            return queue[0] if queue else -1

（33） [数组中的逆序对][Link 30]  
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007  
思考：这边的python会超时，但是思路是对的  
时间复杂度O(nlogn),空间复杂度O(n)。  
先将数组逆转，构建一个新的数组L，将num二分插入到L中，所插入的位置i，代表有i个数字比当前这个数字小

import bisect
    class Solution:
        def InversePairs(self, data):
            data.reverse()
            L = []
            ret = 0
            for d in data:
                pos = bisect.bisect_left(L,d)
                L.insert(pos,d)
                ret+= pos
                ret = ret % 1000000007
            return ret % 1000000007

C++解法：（来源于[好朋友][Link 31]的博客）

/**
    * 运行时间：191ms
    * 占用内存：4336k
    */
    class Solution {
    private:
        long long cnt;
    public:
        int InversePairs(vector<int> data) 
        {
            cnt = 0;  
            vector<int> TmpArray(data.size());
            Msort(data,TmpArray,0,data.size()-1);
            return cnt % 1000000007;
        }
    private:
        void Msort(vector<int>& data,vector<int>& TmpArray,int left, int right)
        {
          int center;
          if(left < right)
          {
            center = (left + right)/2;
            Msort(data,TmpArray,left,center);
            Msort(data,TmpArray,center+1,right);
            // 任意时刻只需要一个临时数组TmpArray活动
            Merge(data,TmpArray,left,center+1,right);
          }
        }
        void Merge(vector<int>& data,vector<int>& TmpArray,int Lpos,int Rpos,int RightEnd)
        { // 合并算法
          int i,LeftEnd,NumElements,TmpPos;
          LeftEnd = Rpos - 1;
          TmpPos = RightEnd;
          NumElements = RightEnd - Lpos + 1;
          /* 主循环*/
          while(LeftEnd >= Lpos && RightEnd >= Rpos)
          {
            if(data[LeftEnd] > data[RightEnd])
            {
              TmpArray[TmpPos--] = data[LeftEnd--];
              /*计算逆序对数*/
              cnt += RightEnd - Rpos + 1;
            }
            else //data[LeftEnd] <= data[RightEnd]
              TmpArray[TmpPos--] = data[RightEnd--];
          }
          while(LeftEnd >= Lpos) // 拷贝左半剩余部分
            TmpArray[TmpPos--] = data[LeftEnd--];
          while(RightEnd >= Rpos) // 拷贝右半剩余部分
            TmpArray[TmpPos--] = data[RightEnd--];
    
          /* 拷贝回原数组*/
          for(int i = 0;i < NumElements;i++,Lpos++)
            data[Lpos] = TmpArray[Lpos];
    
        }
    };

(34) [连续子数组的最大和][Link 32]  
思考：贪心

class Solution:
        def FindGreatestSumOfSubArray(self, array):
            # write code here
            if len(array)==1:
                return array[0]
            cur = pos = array[0]
            for i in range(1,len(array)):
                pos = max(pos+array[i],array[i])
                cur = max(cur,pos)
            return cur

(35) [最小的K个数][K]

import heapq
    class Solution:
        def GetLeastNumbers_Solution(self, tinput, k):
            # write code here
            heaps = []
            ret = []
            for num in tinput:
                heapq.heappush(heaps,num)
            if k>len(heaps):
                return []
            for i in range(k):
                ret.append(heapq.heappop(heaps))
            return ret

（36）[数组中出现次数超过一半的数字][Link 33]  
思考：摩尔投票法

# -*- coding:utf-8 -*-
    class Solution:
        def MoreThanHalfNum_Solution(self, numbers):
            # write code here
            if numbers == []:
                return 0
            val,cnt = None,0
            for num in numbers:
                if cnt==0:
                    val,cnt = num,1
                elif val == num:
                    cnt+=1
                else:
                    cnt-=1
            return val if numbers.count(val)*2>len(numbers) else 0

（37）\* [从1到n整数中1出现的次数][1_n_1]  
思考：可以从n的每个位上入手，pos来记录位，ans来记录当前1的个数，last来记录前面的数（这样讲好复杂，举个例子好了）  
xxxxYzzzz （假设9位）  
在Y上1的个数由xxxx,zzzz和Y来决定  
首先至少有xxxx0000个  
其次看Y  
如果Y大于1那么会多了10000个  
如果Y等于1那么会多了（zzzz+1）个

# -*- coding:utf-8 -*-
    class Solution:
        def NumberOf1Between1AndN_Solution(self, n):
            # write code here
            if n<1:  return 0
            if n==1: return 1
            last,ans,pos = 0,0,1
            while(n):
                num = n%10
                n = n/10
                ans += pos*n
                if num>1:
                    ans+=pos
                elif num==1:
                    ans+=(last+1)
                last = last+num*pos
                pos*=10
            return ans

（38）[把数组排成最小的数][Link 34]  
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。  
思考：总的思路是先将整型字符串化，然后重新定义排序规则，我的做法是将n扩展成长度为n+(maxlen-len(n))\*n\[0\]的字符串，看别人的解答又觉得巧妙

# -*- coding:utf-8 -*-
    import heapq
    class Solution:
        def PrintMinNumber(self, numbers):
            # write code here
            heaps = []
            maxlen = 0
            for num in numbers:
                maxlen+=len(str(num))
            for num in numbers:
                n = str(num)
                heapq.heappush(heaps,(int(n+(maxlen-len(n))*n[0]),num))
            ret = ''
            while(heaps):
                ret+=str(heapq.heappop(heaps)[1])
            return int(ret) if len(ret) else ''

链接：https://www.nowcoder.com/questionTerminal/8fecd3f8ba334add803bf2a06af1b993
    来源：牛客网
    # -*- coding:utf-8 -*-
    class Solution:
        def PrintMinNumber(self, numbers):
            # write code here
            if not numbers:return ""
            numbers = list(map(str,numbers))
            numbers.sort(cmp=lambda x,y:cmp(x+y,y+x))
            return '0' if numbers[0]=='0' else ''.join(numbers)

（39）[数组中重复的数字][Link 35]  
思考：哈希（然而依旧是一题Python不通过的题目）

# -*- coding:utf-8 -*-
    class Solution:
        # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
        # 函数返回True/False
        def duplicate(self, numbers, duplication):
            # write code here
            dup = dict()
            for num in numbers:
                if num not in dup:
                    dup[num] = True
                else:
                    duplication[0]=num
                    return True

（40）\* [构造乘积数组][Link 36]  
B\[i\]=A\[0\]A\[1\]…A\[i-1\]\*A\[i+1\]…\*A\[n-1\]  
思考：分为下三角和上三角DP计算B  
下三角B\[i\]=A\[0\]A\[1\]A\[2\]..A\[i−1\]=B\[i−1\]A\[i−1\]B\[i\]=A\[0\]A\[1\]A\[2\]..A\[i−1\]=B\[i−1\]A\[i−1\]  
上三角（从最后往前）tmp=A\[−1\]A\[−2\]A\[−3\]...tmp=A\[−1\]A\[−2\]A\[−3\]...

class Solution:
        def multiply(self, A):
            # write code here
            size = len(A)
            B = [1]*size
            for i in range(1,size):
                B[i] = B[i-1]*A[i-1]
            tmp = 1
            for i in range(size-2,-1,-1):
                tmp = tmp*A[i+1]
                B[i] = B[i]*tmp
            return B

（41）[二维数组中的查找][Link 37]  
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。  
思考：从0,n-1出开始，小了往下，大了往左

# -*- coding:utf-8 -*-
    class Solution:
        # array 二维列表
        def Find(self, target, array):
            # write code here
            if len(array)==0 or len(array[0])==0:
                return False
            i = 0
            j = len(array[0])-1
            while(i<len(array) and j>=0):
                if array[i][j]==target:
                    return True
                elif array[i][j]>target:
                    j-=1
                else:
                    i+=1
            return False

（42）\* [扑克牌顺子][Link 38]  
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^\_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

class Solution:
        def IsContinuous(self, numbers):
            # write code here
            if not numbers:
                return 0
            numbers.sort()
            zeros = numbers.count(0)
            for i, v in enumerate(numbers[:-1]):
                if v!=0:
                    if numbers[i+1]==v:
                        return False
                    zeros -= (numbers[i+1]-numbers[i]-1)
                    if zeros<0:
                        return False
            return True

（43）[孩子们的游戏][Link 39]

# -*- coding:utf-8 -*-
    class Solution:
        def LastRemaining_Solution(self, n, m):
            # write code here
            if n<1: return -1
            final,start = -1,0
            cnt = [i for i in range(n)]
            while cnt:
                k = (start+m-1)%n
                final = cnt.pop(k)
                n-=1
                start = k
            return final

（44）[正则表达式匹配][Link 40]  
请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab\*ac\*a”匹配，但是与”aa.a”和”ab\*a”均不匹配  
思考：  
第一种情况，当p == ” 时 return s==”  
当len(p)==1时 要满足len(s)==1 AND (p\[0\]==s\[0\] OR p\[0\] == ‘.’)  
当len(p)>1时，要讨论p\[1\] 是不是为’’ ，因为如果p\[1\]==’’ 时候 可能会是p\[2:\] 和 s 匹配情况  
但当p\[1\]!=’\*’ 时候 意味着 必须要关注是否 p\[0\]==s\[0\] 或者 p\[0\]==’.’  
那么这两个可以合并为  
IF len(p) == 0 or p\[1\]!=’\*’  
返回 len(s) AND match(p\[1:\],s\[1:\]) AND (p\[0\]==s\[0\] OR p\[0\] == ‘.’)  
然后最复杂的一种情况p\[1\] == ‘\*’  
p = ‘b\*bbacd’ s = ‘bbbbbacd’  
很明显的是如果p\[0\]!=s\[0\] 且 p\[0\]!=’.’ 那么 看p\[2:\] 和 s 的匹配情况  
如果p\[0\] == s\[0\] 或者 p\[0\] == ‘.’ ， 可以判断p\[2:\] 和 s\[1:\] … p\[2:\] 和 s\[2:\] … p\[2:\] 和 s\[3:\] … 搞个循环 就可以

# -*- coding:utf-8 -*-
    class Solution:
        # s, pattern都是字符串
        def __init__(self):
            self.dic = {}
        def match(self, s, p):
            # write code here
            if (s,p) in self.dic:
                return self.dic[(s,p)]
            if p == '':
                return s==''
            if len(p)==1 or p[1]!='*':
                self.dic[(s[1:],p[1:])] = self.match(s[1:],p[1:])
                return len(s)>0 and (p[0]=='.' or p[0]==s[0]) and self.dic[(s[1:],p[1:])]
            while(len(s) and (p[0]=='.' or p[0]==s[0])):
                self.dic[(s,p[2:])] = self.match(s,p[2:])
                if self.match(s[:],p[2:]):
                    return True
                s = s[1:]
            self.dic[(s,p[2:])] = self.match(s,p[2:])
            return self.dic[(s,p[2:])]

（45）[判断一个字符串是否表示数值][Link 41]  
就是各种逻辑

# -*- coding:utf-8 -*-
    class Solution:
        # s字符串
        def isNumeric(self, s):
            # write code here
            INVALID=0; SPACE=1; SIGN=2; DIGIT=3; DOT=4; EXPONENT=5;
            #0invalid,1space,2sign,3digit,4dot,5exponent,6num_inputs
            transitionTable=[[-1,  0,  3,  1,  2, -1],    #0 no input or just spaces 
                             [-1,  8, -1,  1,  4,  5],    #1 input is digits 
                             [-1, -1, -1,  4, -1, -1],    #2 no digits in front just Dot 
                             [-1, -1, -1,  1,  2, -1],    #3 sign 
                             [-1,  8, -1,  4, -1,  5],    #4 digits and dot in front 
                             [-1, -1,  6,  7, -1, -1],    #5 input 'e' or 'E' 
                             [-1, -1, -1,  7, -1, -1],    #6 after 'e' input sign 
                             [-1,  8, -1,  7, -1, -1],    #7 after 'e' input digits 
                             [-1,  8, -1, -1, -1, -1]]    #8 after valid input input space
            state=0; i=0
            while i<len(s):
                inputtype = INVALID
                if s[i]==' ': inputtype=SPACE
                elif s[i]=='-' or s[i]=='+': inputtype=SIGN
                elif s[i] in '0123456789': inputtype=DIGIT
                elif s[i]=='.': inputtype=DOT
                elif s[i]=='e' or s[i]=='E': inputtype=EXPONENT
    
                state=transitionTable[state][inputtype]
                if state==-1: return False
                else: i+=1
            return state == 1 or state == 4 or state == 7 or state == 8

（46）[字符流中第一个不重复的字符][Link 42]  
思考：用个队列和hash

# -*- coding:utf-8 -*-
    class Solution:
        # 返回对应char
        def __init__(self):
            self.memory = dict()
            self.queue = []
    
        def FirstAppearingOnce(self):
            # write code here
            while len(self.queue) and self.memory[self.queue[0]]>1:
                self.queue.pop(0)
    
            return self.queue[0] if len(self.queue) else '#'
        def Insert(self, char):
            # write code here
            if char not in self.memory:
                self.memory[char]=0
            self.memory[char]+=1
            if self.memory[char]==1:
                self.queue.append(char)

（47）[替换空格][Link 43]

# -*- coding:utf-8 -*-
    import re
    class Solution:
        # s 源字符串
        def replaceSpace(self, s):
            # write code here
            return re.sub(" ","%20",s)

（48）[矩阵中的路径][Link 44]  
思考：dfs加记忆化搜索

# -*- coding:utf-8 -*-
    class Solution:
        def hasPath(self, matrix, rows, cols, path):
            def dfs(memories,r,c,s):
                if s=='':
                    return True
                dx = [-1,1,0,0]
                dy = [0,0,-1,1]
                for k in range(4):
                    x = dx[k] + r
                    y = dy[k] + c
                    if x >= 0 and x < rows and y >= 0 and y < cols and memories[x][y] and matrix[x*cols+y]==s[0]:
                        memories[x][y]=False
                        if dfs(memories[:], x, y,s[1:]):
                            return True
                        memories[x][y]=True
                return False
    
            if path == '':
                return True
            memories = [[True for c in range(cols)] for r in range(rows)]
            for r in range(rows):
                for c in range(cols):
                    if matrix[r*cols+c] == path[0]:
                        memories[r][c] = False
                        if dfs(memories[:],r,c,path[1:]):
                            return True
                        memories[r][c] = True
            return False

（49）[机器人的运动范围][Link 45]  
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？  
思考：dfs+记忆化搜索

# -*- coding:utf-8 -*-
    class Solution:
        def movingCount(self, threshold, rows, cols):
            # write code here
            memories = set()
            def dfs(i,j):
                def judge(i,j):
                    return sum(map(int, list(str(i)))) + sum(map(int, list(str(j)))) <= threshold
                if not judge(i,j) or (i,j) in memories:
                    return
                memories.add((i,j))
                if i != rows - 1:
                    dfs(i + 1, j)
                if j != cols - 1:
                    dfs(i, j + 1)
            dfs(0,0)
            return len(memories)

（50）[求1+2+3+..+n][1_2_3_.._n]  
思考：递归

# -*- coding:utf-8 -*-
    class Solution:
        def Sum_Solution(self, n):
            # write code here
            if n == 1: return 1
            return n+self.Sum_Solution(n-1)

（51）\* [不用加减乘除做加法][Link 46]  
思考：不计进位的和为 a^b，进位就是 a&b  
a+b = a^b + (a&b)<<1;  
这题python依旧有坑 = =

public class Solution {
        public int Add(int a,int b) {
            int unit = a ^ b;  
            int carry_bit = a & b;  
            while(carry_bit != 0) {  
                int temp_a = unit;  
                int temp_b = carry_bit << 1;  
                unit = temp_a ^ temp_b;  
                carry_bit = temp_a & temp_b;  
            }  
            return unit;  
        }
    }

（52）[二叉搜索树与双向链表][Link 47]  
思考：左子树上最右结点 -> root -> 右子树上的最左结点

class Solution:
        def Convert(self, pRootOfTree):
            # write code here
            if pRootOfTree == None:
                return pRootOfTree
            if pRootOfTree.left == None and pRootOfTree.right == None:
                return pRootOfTree
            left = self.Convert(pRootOfTree.left)
            p = left
            if left:
                while(p.right):
                    p = p.right
                p.right = pRootOfTree
                pRootOfTree.left = p
            right = self.Convert(pRootOfTree.right)
            if right:
                pRootOfTree.right = right
                right.left = pRootOfTree
            return left if left else pRootOfTree

（53）[复杂链表的复制][Link 48]  
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）  
思考：hash

class Solution:
        # 返回 RandomListNode
        def Clone(self, head):
            """
            :type head: RandomListNode
            :rtype: RandomListNode
            """
    
            if head == None:
                return head
            node_dict = {}
            node_dict[head] = RandomListNode(head.label)
            tmp = head
            while(head):
                random = head.random
                nexthd = head.next
                if random !=None:
                    if random not in node_dict:
                        node_dict[random] = RandomListNode(random.label)
                    node_dict[head].random = node_dict[random]
                if nexthd !=None:
                    if nexthd not in node_dict:
                        node_dict[nexthd] = RandomListNode(nexthd.label)
                    node_dict[head].next = node_dict[nexthd]
                head = head.next
            return node_dict[tmp]

（54）[字符串的排列][Link 49]  
思考：dfs

# -*- coding:utf-8 -*-
    class Solution:
        def Permutation(self, ss):
            def dfs(s):
                if len(s) == '':
                    return []
                if len(s)==1:
                    return [s]
                if len(s)==2:
                    return list(set([s[0]+s[1],s[1]+s[0]]))
                ans = set([])
                left = s[0]
                right = dfs(s[1:])
                for word in right:
                    for i in range(len(word)+1):
                        ans.add(word[:i]+left+word[i:])
                return list(ans)
            if ss == '':
                return []
            return sorted(dfs(ss))

（55）[二进制中1的个数][1]  
思考：python没有无符号移动，需要处理下

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

（56）[链表中倒数第k个结点][k 1]  
思考：两个指针p,q p先走k步

class Solution:
        def FindKthToTail(self, head, k):
            # write code here
            p1 = p2 = head
            for i in range(k):
                if p1==None:
                    return None
                p1 = p1.next
            while(p1):
                p2 = p2.next
                p1 = p1.next
            return p2

（57）[合并两个排序的链表][Link 50]

class Solution:
        # 返回合并后列表
        def Merge(self, pHead1, pHead2):
            # write code here
            ret = ListNode(0)
            tmp = ret 
            p1 = pHead1
            p2 = pHead2
            while(p1 and p2):
                if p1.val<p2.val:
                    tmp.next = ListNode(p1.val)
                    p1 = p1.next
                else:
                    tmp.next = ListNode(p2.val)
                    p2 = p2.next
                tmp = tmp.next
            if p1:
                tmp.next = p1
            if p2:
                tmp.next = p2
            return ret.next

（58）[翻转链表][Link 51]

class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            head = None
            while(pHead):
                tmp = ListNode(pHead.val)
                tmp.next = head
                head = tmp
                pHead = pHead.next
            return head

class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            if pHead==None or pHead.next == None:
                return pHead
            p = self.ReverseList(pHead.next)
            pHead.next.next = pHead
            pHead.next = None
            return p

（59）[判断树B是否是树A的子结构][B_A]

class Solution:
        def HasSubtree(self, pRoot1, pRoot2):
            def subtree(pRoot1,pRoot2):
                if pRoot2 == None and pRoot1 == None:
                    return True
                if pRoot2 == None:
                    return False
                if pRoot1 == None:
                    return False
    
                if pRoot2.val == pRoot1.val:
                    if pRoot2.left == None and pRoot2.right == None:
                        return True
                    if subtree(pRoot1.left,pRoot2.left) and subtree(pRoot1.right,pRoot2.right):
                        return True
                return subtree(pRoot1.left,pRoot2) or subtree(pRoot1.right,pRoot2)
            if pRoot1 == None and pRoot2 == None:
                return False
            return subtree(pRoot1,pRoot2)

（60）\* [数值的n次方][n]  
思考：109109可以分解为10(1001,2)10(1001,2)，用二分

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

（61）[调整数组顺序使奇数位于偶数前面][Link 52]

# -*- coding:utf-8 -*-
    class Solution:
        def reOrderArray(self, array):
            size = len(array)
            pos = size-1
            cnt = 0
            while(cnt<size):
                if array[pos]%2==1:
                    tmp = array[pos]
                    for i in range(pos-1,-1,-1):
                        array[i+1] = array[i]
                    array[0] = tmp
                else:
                    pos -=1
                cnt +=1
            return array

（62）[包含min函数的栈][min]  
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

# -*- coding:utf-8 -*-
    class Solution:
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.stack = []
            self.minstack =[]
    
        def push(self, x):
            """
            :type x: int
            :rtype: void
            """
            self.stack.append(x)
            if len(self.minstack)==0 or self.minstack[-1][0]>x:
                self.minstack.append((x,1))
            elif self.minstack[-1][0] == x:
                self.minstack[-1] = (x,self.minstack[-1][1]+1)
    
        def pop(self):
            """
            :rtype: void
            """
            ans = self.stack[-1]
            self.stack = self.stack[0:len(self.stack)-1]
            if ans == self.minstack[-1][0]:
                if self.minstack[-1][1] == 1:
                    self.minstack.remove(self.minstack[-1])
                else:
                    self.minstack[-1] = (ans,self.minstack[-1][1]-1)
    
    
        def top(self):
            """
            :rtype: int
            """
            return self.stack[-1]
    
    
        def min(self):
            """
            :rtype: int
            """
            return self.minstack[-1][0]

（63）[二叉树中和为某一值的路径][Link 53]  
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。  
思考：dfs

class Solution:
        # 返回二维列表，内部每个列表表示找到的路径
        def FindPath(self, root, expectNumber):
            # write code here
            ret = []
            def dfs(root,sum_,tmp):
                if root:
                    if root.left==None and root.right == None:
                        if root.val == sum_:
                            tmp.append(root.val)
                            ret.append(tmp[:])
                    else:
                        tmp.append(root.val)
                        dfs(root.left,sum_-root.val,tmp[:])
                        dfs(root.right,sum_-root.val,tmp[:])
            dfs(root,expectNumber,[])
            return ret

（64）[从上往下打印二叉树][Link 54]  
思考：bfs

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

（65）\* [二叉搜索树的后序遍历序列][Link 55]  
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。  
思考：后序遍历意味着num\[-1\]为root，那么根据这个值和二叉搜索树的性质，可以把数组划分成两个部分，left 和 right ，再递归判断

# -*- coding:utf-8 -*-
    class Solution:
        def VerifySquenceOfBST(self, sequence):
            # write code here
            if len(sequence)==0:
                return False
            root = sequence[-1]
    
            i = 0
            for node in sequence[:-1]:
                if node > root:
                    break
                i += 1
    
            for node in sequence[i:-1]:
                if node < root:
                    return False
            left = True
            if i > 1:
                left = self.VerifySquenceOfBST(sequence[:i])
    
            right = True
            if i < len(sequence) - 2 and left:
                right = self.VerifySquenceOfBST(sequence[i+1:-1])
            return left and right

（66）[栈的压入、弹出序列][Link 56]

# -*- coding:utf-8 -*-
    class Solution:
        def IsPopOrder(self, pushV, popV):
            # write code here
            stack = []
            while(popV):
                if pushV and pushV[0]==popV[0]:
                    pushV.pop(0)
                    popV.pop(0)
                elif stack and stack[-1]==popV[0]:
                    stack.pop()
                    popV.pop(0)
                elif pushV:
                    stack.append(pushV.pop(0))
                else:
                    return False
            return True

[Link 1]: https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Leetcode]: https://leetcode.com/problems/invert-binary-tree/description/
[Link 2]: https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Leetcode 142. Linked List Cycle II]: https://leetcode.com/problems/linked-list-cycle-ii/description/
[Leetcode 141. Linked List Cycle]: https://leetcode.com/problems/linked-list-cycle/description/
[Link 3]: https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11209&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Leetcode. 82. Remove Duplicates from Sorted List II]: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
[Link 4]: https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 5]: https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&tqId=11160&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 6]: https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=13&tqId=11161&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 7]: https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 8]: https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&tqId=11163&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 9]: https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&tqId=11202&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 10]: https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[S]: https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 11]: https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec?tpId=13&tqId=11196&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 12]: https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 13]: https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&tqId=11193&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 14]: https://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3?tpId=13&tqId=11197&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 15]: https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tqId=11191&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[S 1]: https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=11195&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 16]: https://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 17]: https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 18]: https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tqId=11211&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Leetcode 101. Symmetric Tree]: https://leetcode.com/problems/symmetric-tree/description/
[Link 19]: https://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288?tpId=13&tqId=11213&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 20]: https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&tqId=11212&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 21]: https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=13&tqId=11214&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Serialize and Deserialize Binary Tree]: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
[Link 22]: https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=13&tqId=11216&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Find Median from Data Stream]: https://leetcode.com/problems/find-median-from-data-stream/description/
[k]: https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?tpId=13&tqId=11215&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Leetcode 230. Kth Smallest Element in a BST]: https://leetcode.com/problems/kth-smallest-element-in-a-bst/
[Link 23]: https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal]: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
[Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal]: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
[Link 24]: https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 25]: https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 26]: https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 27]: https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 28]: https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 29]: https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 30]: https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 31]: http://blog.csdn.net/u011480869/article/details/79403922
[Link 32]: https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&tqId=11183&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[K]: https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 33]: https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[1_n_1]: https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=11184&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 34]: https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=11185&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 35]: https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 36]: https://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46?tpId=13&tqId=11204&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 37]: https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 38]: https://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4?tpId=13&tqId=11198&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 39]: https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 40]: https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?tpId=13&tqId=11205&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 41]: https://www.nowcoder.com/practice/6f8c901d091949a5837e24bb82a731f2?tpId=13&tqId=11206&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 42]: https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720?tpId=13&tqId=11207&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 43]: https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423?tpId=13&tqId=11155&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 44]: https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&tqId=11218&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 45]: https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&tqId=11219&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[1_2_3_.._n]: https://www.nowcoder.com/practice/7a0da8fc483247ff8800059e12d7caf1?tpId=13&tqId=11200&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 46]: https://www.nowcoder.com/practice/59ac416b4b944300b617d4f7f111b215?tpId=13&tqId=11201&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 47]: https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 48]: https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 49]: https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[1]: https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11164&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[k 1]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 50]: https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 51]: https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11168&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[B_A]: https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[n]: https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 52]: https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[min]: https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=11173&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 53]: https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 54]: https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&tqId=11175&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 55]: https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[Link 56]: https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking