本文共 39659 字，大约阅读时间需要 132 分钟。

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）

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）

寻找环的入口结点 这题是的扩展。 判断是否存在环用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） 删除链表中重复的结点

用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）从头到尾打印链表

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项

# -*- 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）

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 $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）

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 思考：在dp[n] = dp[n-1] + dp[n-2] + .. + dp[1] + 1(直接跳n)步骤 即$dp[n] = \sum_{i=1}^{n-1} dp[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）

我们可以用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]$

# -*- 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）把字符串转换成整数

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为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）

思考：BST的定义为$|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%奇数==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）

对于一个给定的字符序列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）数字在排序数组中出现的次数

思考：原来是可以用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
   
    k:                end = mid-1            else:                start = mid+1        return 0
   

（14）

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字 思考：用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）

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

（16）

# -*- coding:utf-8 -*-# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass 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，如果有多对数字的和等于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）

# -*- 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
   
     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）* 二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 思路：中序遍历的顺序为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）

判断一棵树是不是左右对称的树

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）

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

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）

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）* 序列化和反序列化二叉树

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） * 数据流中的中位数

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小数

思路：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）

根据先序、中序来构建二叉树

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

根据中序和后序构建二叉树

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）

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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)

思考：栈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)

思考：二分判断

# -*- 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[right]:                # 说明在【mid，right】之间                left = mid + 1            else:                # 说明在【left，mid】之间                right = mid - 1        return rotateArray[mid]
   

（30）

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

# -*- coding:utf-8 -*-import heapqclass 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）

思考：设链表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)

思考：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）

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

import bisectclass 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++解法：（来源于的博客）

/*** 运行时间：191ms* 占用内存：4336k*/class Solution {private:    long long cnt;public:    int InversePairs(vector
   
     data)     {        cnt = 0;          vector
    
      TmpArray(data.size());        Msort(data,TmpArray,0,data.size()-1);        return cnt % 1000000007;    }private:    void Msort(vector
     
      & data,vector
      
       & 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
       
        & data,vector
        
         & 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)

思考：贪心

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)

import heapqclass 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）

思考：摩尔投票法

# -*- 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）*

思考：可以从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）

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

# -*- coding:utf-8 -*-import heapqclass 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）

思考：哈希（然而依旧是一题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）*

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]$ 上三角（从最后往前）$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）

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 思考：从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
   
    =0):            if array[i][j]==target:                return True            elif array[i][j]>target:                j-=1            else:                i+=1        return False
   

（42）*

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）

# -*- 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）

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含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）

就是各种逻辑

# -*- 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

（46）

思考：用个队列和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）

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

（48）

思考：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）

地上有一个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）

思考：递归

# -*- 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）*

思考：不计进位的和为 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）

思考：左子树上最右结点 -> 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）

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的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）

思考：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）

思考：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）

思考：两个指针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）

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

（58）

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）

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）*

思考：$10^9$可以分解为$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）

# -*- coding:utf-8 -*-class Solution:    def reOrderArray(self, array):        size = len(array)        pos = size-1        cnt = 0        while(cnt

（62）

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的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）

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 思考：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）

思考：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）*

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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）

# -*- 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

转载地址：http://tfqmi.baihongyu.com/