剑指offer解题_Python版

1.二维数组中的查找

题目： 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：遍历每一行，查找该元素是否在该行之中。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        for i in array:
            if target in i:
                return True
        return False

2.替换空格

题目： 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：利用字符串中的replace直接替换即可。

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        return s.replace(' ','%20')

3.从尾到头打印链表

题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

思路：将链表中的值记录到list之中，然后进行翻转list。

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

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

4.重建二叉树(flag)

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

题解：首先前序遍历的第一个元素为二叉树的根结点，那么便能够在中序遍历之中找到根节点，那么在根结点左侧则是左子树；在根结点右侧，便是右子树。然后在递归遍历左子树和右子树。这里要注意一点，pre的左右子树分割长度与中序的左右子树分割长度一致。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if len(pre)==0:
            return None
        if len(pre)==1:
            return TreeNode(pre[0])
        else:
            flag = TreeNode(pre[0])
            #pre的左右子树分割长度与中序的左右子树分割长度一致。
            flag.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])  
            flag.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
        return flag

5.用两个栈实现队列(flag)

题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

题解：申请两个栈Stack1和Stack2，Stack1当作输入，Stack2当作pop。当Stack2空的时候，将Stack1进行反转，并且输入到Stack2。

# -*- 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 self.Stack2==[]:
            while self.Stack1:
                self.Stack2.append(self.Stack1.pop())
            return self.Stack2.pop()
        return self.Stack2.pop()

6.旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        else: 
            return min(rotateArray)

7.斐波那契数列(flag)

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39。

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

8.跳台阶

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

题解：ans[n]=ans[n-1]+ans[n-2]

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        if not number:
            return 0
        if number==1:
            return 1
        if number==2:
            return 2
        a,b=1,2
        for i in range(number-2):
            a,b=b,a+b
        return b

9.变态跳台阶

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题解：ans[n]=ans[n-1]+ans[n-2]+ans[n-3]+…+ans[n-n]，ans[n-1]=ans[n-2]+ans[n-3]+…+ans[n-n]，ans[n]=2*ans[n-1]。

class Solution:
    def jumpFloorII(self, number):
        if not number:
            return 0
        if number==1:
            return 1
        if number==2:
            return 2
        return 2**(number-1)

10.矩形覆盖

题目：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

题解：新增加的小矩阵竖着放，则方法与n-1时相同，新增加的小矩阵横着放，则方法与n-2时相同，于是f(n)=f(n-1)+f(n-2)。

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if not number:
            return 0
        if number==1:
            return 1
        if number==2:
            return 2
        a,b=1,2
        for _ in range(number-2):
            a,b=b,a+b
        return b

11.二进制中1的个数(flag)

题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

题解：每次进行右移一位，然后与1进行相与，如果是1则进行加1。

# 向右移1位可以看成除以2，向左移一位可以看成乘以2。移动n位可以看成乘以或者除以2的n次方。
# 负数原码（int整型用32位表示）所有位取反码然后+1得到补码；正数的补码为其自身
class Solution:  #转为字符串
    def NumberOf1(self, n):
        # write code here
        if n==0:
            return 0
        if n>0:
            a=bin(n).count('1')
            return a
        else:
            a=bin(2**32+n).count('1')
            return a
            
class Solution: #每次移一位，看此为是否为1，负数的表示内部已经是补码了
    def NumberOf1(self, n):
        # write code here
        count = 0
        for i in range(32):
            count += (n >> i) & 1
        return count

12.数值的整次方

题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        ans=1
        for i in range(0,abs(exponent)):
            ans=ans*base
        if exponent>0:
            return ans
        else:
            return 1/ans

13.调整数组顺序使奇数位于偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

题解：申请奇数数组和偶数数组，分别存放奇数值和偶数值，数组相加便为结果。

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        array=list(array)
        a=[]
        b=[]
        for i in array:
            if i%2==1:
                a.append(i)
            else:
                b.append(i)
        return a+b

14.链表中倒数第K个节点

题目：输入一个链表，输出该链表中倒数第k个结点。

题解：快慢指针。

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        l=[]
        count=0
        if not head:
            return None
        a1=head
        for i in range(k):
            if not a1:
                return None
            else:
                a1=a1.next
        a2=head
        while a1:
            a1=a1.next
            a2=a2.next
        return a2

15.反转链表(flag)

题目：输入一个链表，反转链表后，输出新链表的表头。

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead:
            return None
        if not pHead.next:
            return pHead
        Pre=None
        Next=None
        while pHead:
            Next=pHead.next # 暂存当前节点的下一个节点信息
            pHead.next=Pre  # 断开链表, 反转节点, 这两句都是为了保护链表断开不丢失next的指向
            Pre=pHead
            pHead=Next
        return Pre

16.合并两个排序的列表

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1 and not pHead2:
            return None
        if not pHead1 or not pHead2:
            if not pHead1:
                return pHead2
            else:
                return pHead1
        merge=ListNode(0)# 新一个头结点数值为x的链表
        p=merge    #返回时的指向头结点的指针
        while pHead1 and pHead2:
            if pHead1.val<=pHead2.val:
                merge.next=pHead1
                pHead1=pHead1.next
            else:
                merge.next=pHead2
                pHead2=pHead2.next
            merge=merge.next
        while pHead1:
            merge.next=pHead1
            pHead1=pHead1.next
            merge=merge.next
        while pHead2:
            merge.next=pHead2
            pHead2=pHead2.next
            merge=merge.next
        return p.next

17.树的子结构(flag)

题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）。

题解：递归；或者将树转变为中序序列，然后转变为str类型，最后判断是否包含。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        root1 = pRoot1
        root2 = pRoot2
        result = False
        if root1.val==root2.val:  # HasSubtree条件出口，满足根节点相同才继续判断子树结构
            result = self.hastree(root1,root2)
        if not result:
            result = self.HasSubtree(root1.left,root2)
        if not result:
            result = self.HasSubtree(root1.right,root2)
        return result
    def hastree(self,root1,root2):
        if root2==None:
            return True
        if root1==None:
            return False
        if root1.val==root2.val:
            return self.hastree(root1.left,root2.left) and self.hastree(root1.right,root2.right)
        if root1.val!=root2.val:
            return False

18.二叉树的镜像

题目： 操作给定的二叉树，将其变换为源二叉树的镜像。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        if root:
            root.left,root.right=root.right,root.left
            self.Mirror(root.left)
            self.Mirror(root.right)

19.顺时针打印矩阵(flag)

题目: 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        rows=len(matrix)
        cols=len(matrix[0])
        l=[]
        if rows==1 and cols==1:
            return [matrix[0][0]]
        left,right, up, down = 0,cols-1,0,rows-1  #这个是数组下标
        while left<=right and up<=down:    
            for i in range(left,right+1):     #range函数接收参数从小到大，大的数值不计入
                l.append(matrix[up][i])
            for j in range(up+1,down+1):
                l.append(matrix[j][right])
            if down-up>=1:   #相等时为剩余单行
                for k in range(left,right)[::-1]:   #这里注意逆序的数组下标
                    l.append(matrix[down][k])
            if right-left>=1:   #相等时为剩余单列
                for p in range(up+1,down)[::-1]:
                    l.append(matrix[p][left])
            up=up+1
            down=down-1
            left=left+1
            right=right-1
        return l

20.包含Min函数的栈(flag)

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack=[]
        self.minstack=[]      #pop()删除列表的最后一个元素,[-1]获取最后一个元素
    def push(self, node):     #最小栈存储 整个原栈的最小元素，若最小元素在原栈删除，则也要删除最小栈
        if not self.minstack or node<self.minstack[-1]:   
            self.minstack.append(node)
        self.stack.append(node)
    def pop(self):
        if not self.stack:
            return None
        elif self.stack[-1]==self.minstack[-1]:
            self.minstack.pop()
        else:
            self.stack.pop()
        # write code here
    def top(self):
        return self.stack[-1]
        # write code here
    def min(self):
        return self.minstack[-1]
        # write code here

21.栈的压入弹出序列(flag)

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）。

题解：构建压入和活动栈，只有处于压入栈栈顶或者活动栈内才可弹出；或者新构建一个中间栈，来模拟栈的输入和栈的输出，比对输入结果和输出结果是否相等。

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):  
        if not pushV:   
            return None
        fixed=[]   #压下去的辅助栈，处于栈顶可以出栈
        left=pushV[:]   #剩余的可活动栈，p元素位置之前的都要压入辅助栈
        flag=True
        for p in popV:
            if p not in pushV:   #还要判断pushV和popV元素不同的情况
                return False
            if p in left:
                k=left.index(p)
                fixed=fixed+left[:k+1]
                left=left[k+1:]
                fixed.pop()
            elif fixed:  #避免fixed[-1]越界
                if p!=fixed[-1]:
                    return False
                else:fixed.pop()
        return flag

22.从上往下打印二叉树

题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：层次遍历，用队列。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        res=[]
        value=[]
        if not root:
            return []  #返回空列表，而不是None
        else:
            res.append(root)
            value.append(root.val)
        while res:
            p=res.pop(0)   # pop(0)才是第一个元素
            if p.left:
                res.append(p.left)
                value.append(p.left.val)
            if p.right:
                res.append(p.right)
                value.append(p.right.val)
        return value

23.二叉树的后续遍历序列(flag)

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：二叉搜索树的特性是所有左子树值都小于中节点，所有右子树的值都大于中节点，递归遍历左子树和右子树的值。

# -*- coding:utf-8 -*-
# 后续遍历要满足 去除序列最后一个元素（根）后，将小于和大于这个元素直接分成两段，递归
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        if len(sequence)==1:
            return True
        front=[]
        back=[]
        flag=0  # 辅助与分段的标记，第一个大于p元素之后的都放在back断
        p=sequence.pop()
        for i in sequence:
            if i<=p and flag==0:
                front.append(i)
            else:
                flag=1
                back.append(i)
        if front and max(front)>p:  #front要满足所有元素都小于p
            return False
        if back and min(back)<p: #back要满足所有元素都大于p
            return False
        LEFT=True  #递归出口
        RIGHT=True
        if front:
            LEFT=self.VerifySquenceOfBST(front)
        if back:
            RIGHT=self.VerifySquenceOfBST(back)
        return LEFT and RIGHT

24.二叉树中和为某一值的路径(flag)

题目：输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        # 这题不太会，记一下
        if not root:#即是一开始条件语句，也是递归出口，若叶子节点不满足条件，left或者right返回空
            return []
        if root and not root.left and not root.right and root.val == expectNumber:
            return [[root.val]]  #递归出口，即叶子节点满足条件，不会执行以下任何语句；
                                 
        res = [] #每次清空
        # 先会一直先递归left，相当于深度优先搜索
        left = self.FindPath(root.left, expectNumber-root.val) #left_left1_left11_right11_...right1
        right = self.FindPath(root.right, expectNumber-root.val)
        # 遍历后的操作
        for i in left+right:  #是指里面的元素，[[root.val]]得到的元素是[root.val]
            res.append([root.val]+i)
        return res
    
   #      6        左图所示，left返回[[3]],right返回的res为[].append([2]+[1])=[[2,1]]
    #   3   2      最后一层返回[[6,3],[6,2,1]]
     #     1

25.复杂链表的复制(flag)

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

思路：

1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面（暂不处理随机节点）；

2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;

3、拆分链表，将链表拆分为原链表和复制后的链表

# -*- coding:utf-8 -*-
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return
        pCur = pHead
        while pCur:
            node = RandomListNode(pCur.label)
            node.next = pCur.next
            pCur.next = node
            pCur = node.next
        pCur = pHead
        while pCur:
            if pCur.random:
                pCur.next.random = pCur.random
            pCur = pCur.next.next
        pCur = pHead
        cur = pHead.next
        h = cur
        while cur:  #拆分
            pCur.next = cur.next
            if pCur.next:
                cur.next = pCur.next.next
            pCur = pCur.next
            cur = cur.next
        return h

26.二叉搜索树与双向列表

题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：中序遍历，然后添加一个pre指针

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def __init__(self):
        self.a=[]
    def Convert(self, pRootOfTree):
        # write code here
         
        if pRootOfTree==None:
            return 
        self.Convert(pRootOfTree.left)
        self.a.append(pRootOfTree)
        self.Convert(pRootOfTree.right)
        for i in range(len(self.a)-1):
            self.a[i].right=self.a[i+1]
            self.a[i+1].left=self.a[i]
        return self.a[0]

27.字符串的排列(flag)

题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路：用itertools.permutations;或者通过将固定每一位的字符，然后进行和后面的每个字符进行交换，得到所有结果集。

# -*- coding:utf-8 -*-
import itertools
class Solution:
    def Permutation(self, ss):
        if not ss:
            return []
        return sorted(list(set(map(''.join, itertools.permutations(ss)))))
    
    #  abc
    #  itertools.permutations(ss)输出('a','b','c') ('a','c','b')...等
    #  map函数后为abc acb..

28.数组中出现次数超过一般的数字

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0

题解：判断是否有超过一半的元素，如果有则在数组中间的元素

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        if len(numbers)==1:
            return numbers[0]
        l=len(numbers)//2
        k=sorted(list(numbers))  #排序，满足条件处于中间位置的为最多元素
        count=0                  #不满足条件则遍历判断 此元素maxcount是否超过一半
        maxcount=0
        for i in range(len(k)-1):
            if k[i]==k[i+1]:
                count=count+1
                if count>maxcount:
                    maxcount=count
            else:
                count=0
        if maxcount>=l:
            return k[l]
        else:
            return 0

29.最小的K个数

题目：输入n个整数，找出其中最小的K个数，例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if len(tinput)<k:
            return []
        res=sorted(tinput)
        return res[:k]

30.连续子数组的最大和(flag)

题目：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here  只需要返回最大数，下标不管
        # 思路：创建一个列表储存要加入的元素，当累积和小于0则清空前面一段
        # 另外一个更简单的思路PART2
        if len(array)==1:
            return array[0]  
        if max(array)<=0:  #全是负数
            return max(array)
        if min(array)>=0:
            return sum(array)
        cum_max=0
        maxnum=0
        res=[]
        for  k, i in enumerate(array):  
            if cum_max+i>=0 and max(array[k:])>0: # 注意一点，当前数组后面全是负数，不能再加了
                res.append(i)
                cum_max=cum_max+i
            else:
                #curmax=0  #此时可以记下标，这里不要求
                cum_max=0
                if sum(res)>maxnum:
                    maxnum=sum(res)
                res=[]
        return max(maxnum,sum(res))    #sum(res)是最后数组res一直加入元素而没有更新maxnum 
    
    # ======================part2：==========================
    # class Solution:
    #    def FindGreatestSumOfSubArray(self, array):
    #        maxnum= float(-inf)
    #        cum_max= 0
    #        for i in array:
    #            if cum_max+i<0:
    #                cum_max=i        #这一句是精华，什么都不作处理，下一个值当做cum_max
    #            else:
    #                cum_max=cum_max+i
    #            if cum_max>maxnum:
    #                maxnum=cum_max
    #            return maxnum

31.整数中1出现的次数

题目：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count=0
        for i in range(1+n):
            count=count+str(i).count('1')
        return count

32.把数组排成最小的数(flag)

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

思路：将数组转换成字符串之后，进行两两比较字符串的大小，比如3,32的大小由332和323确定，即3+32和32+3确定。

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ''
        cmp_def = lambda x1,x2: int(str(x1)+str(x2))-int(str(x2)+str(x1))
        a=sorted(numbers,cmp=cmp_def)  #sortef创建副本，sort原地
        b=list(map(lambda x:str(x),a)) #列表数字转字符串
        return ''.join(b)  #jion反馈一个字符串

33.丑数(flag)

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

思路：每一个丑数必然是由之前的某个丑数与2，3或5的乘积得到的，这样下一个丑数就用之前的丑数分别乘以2，3，5，找出这三这种最小的并且大于当前最大丑数的值，即为下一个要求的丑数。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code herei
        # 思路，创建一个数组存储丑数；创建三个丑数数组独立下标对应乘以235，最小为当前丑数
        if index==0:
            return 0
        if index==1:
            return 1
        uglyarr=[1]
        a2,a3,a5=0,0,0
        for i in range(index-1):
            n1,n2,n3=uglyarr[a2]*2,uglyarr[a3]*3,uglyarr[a5]*5        
            min_num=min(n1,n2,n3)
            uglyarr.append(min_num)
            if min_num==n1:
                a2=a2+1
            if min_num==n2:
                a3=a3+1
            if min_num==n3:
                a5=a5+1
        return uglyarr[-1]

34.第一个只出现一次的字符

题目：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1。

# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        ss=list(s)
        for i,e in enumerate(ss):
            if s.count(e)==1:
                return i
        return -1

35.数组中的逆序对(Flag)

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。

输入描述：题目保证输入的数组中没有的相同的数字。

'''
/*
归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面数组array[i]~array[mid]都是大于array[j]的，
count += mid+1 - i参考剑指Offer，但是感觉剑指Offer归并过程少了一步拷贝过程。还有就是测试用例输出结果比较大，对每次返回的count mod(1000000007)求余
*/
'''
# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        return self.inverseCount(data[:], 0, len(data)-1, data[:])%1000000007
       
    def inverseCount(self, tmp, start, end, data):
        if end-start <1:
            return 0
        if end - start == 1:
            if data[start]<=data[end]:
                return 0
        mid = (start+end)//2
        cnt = self.inverseCount(data, start, mid, tmp) + self.inverseCount(data, mid+1, end, tmp)
        # print(start, mid, end, cnt, data)
        i = start
        j = mid + 1
        ind = start  # 用于tmp的下标
           
        while(i <= mid and j <= end): # tmp排序
            if data[i] <= data[j]:
                tmp[ind] = data[i]
                i += 1
            else:
                tmp[ind] = data[j]
                cnt += mid - i + 1
                j += 1
            ind += 1
        while(i<=mid):
            tmp[ind] = data[i]
            i += 1
            ind += 1
        while(j<=end):
            tmp[ind] = data[j]
            j += 1
            ind += 1
        return cnt

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

题目：输入两个链表，找出它们的第一个公共结点。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#有些题的输入指针，没有val属性，只有next

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        while pHead1:
            p2=pHead2  
            while p2:
                if pHead1==p2:
                    return pHead1
                p2=p2.next
            pHead1=pHead1.next
        return None

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

题目：统计一个数字在排序数组中出现的次数。

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        count=0
        flag=1
        if not data:
            return 0
        for i in data:
            if i==k:
                count=count+1
                flag=1  #设置处在相同阶段的标志
            if count>0 and flag!=1: #不在相同阶段就break 
                break
        return count

38.二叉树的深度(flag)

题目：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

# -*- 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 not pRoot:
            return 0
        left=self.TreeDepth(pRoot.left)  #操作放在后面，想象后序遍历
        right=self.TreeDepth(pRoot.right)
        return max(left,right)+1

39.平衡二叉树(flag)

题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

题解：平衡二叉树是左右子数的距离不能大于1，因此递归左右子树，判断子树距离是否大于1。用Maxdeep递归求深度

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        # 递归且有一个实现求深度的递归函数
        if not pRoot:
            return True
        if abs(self.Maxdeep(pRoot.left)-self.Maxdeep(pRoot.right))>1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
    def Maxdeep(self,pRoot):
        if not pRoot:
            return 0
        left = self.Maxdeep(pRoot.left)
        right = self.Maxdeep(pRoot.right)
        return max(left,right)+1

40.数组中只出现一次的数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

题解：转为字符串；或者将数组中数转到set之中，然后利用dict存储每个数字出现的次数。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if not array:
            return None
        if len(array)==1:
            return array[0]
        l=[]
        arr_str_list=list(map(lambda x:str(x),array))
        arr_str=''.join(arr_str_list) #输入要为字符列表
        for i,e in enumerate(arr_str_list):
            if arr_str.count(e)==1:
                l.append(i)
        ll=[]
        for i in l:
            ll.append(array[i])
        return ll
# ====================================
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        arrayset=set(array)
        dict={}
        for num in arrayset:
            dict[num]=0
        for i in range(0,len(array)):
            dict[array[i]]=dict[array[i]]+1
        ans=[]
        for num in arrayset:
            if dict[num]==1:
                ans.append(num)
        return ans

41.和为S的连续正整数序列

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

输出描述：输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        #若是100,只需要从1：50找就可以了，+2是考虑到下标0开始，让搜索范围大一些
        bitsum=tsum//2+2 
        ori=list(range(1,bitsum)) 
        res=[]
        for i in range(1,bitsum):
            l=[]
            summ=i #累积总和
            for j in range(i+1,bitsum):
                summ=summ+j
                if summ==tsum:
                    l=ori[i-1:j] #i,j看做下标返回满足条件的数组
                if summ>tsum:
                    break
            if l:
                res.append(l)
        return res

42.和为S的两个数字(flag)

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

输出描述：对应每个测试案例，输出两个数，小的先输出

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        # 返回列表类型的，若不满足条件则[]
        if len(array)<=1 or min(array)>tsum:
            return []
        res=[]
        for i in range(len(array)):  # 都是索引下标循环
            for j in range(i+1,len(array)): 
                if array[i]+array[j]==tsum:
                    # 从头开始搜索这时候得到的应该是乘积最小的，可以直接退出外层循环
                    res.append(array[i])
                    res.append(array[j])
                    break
                if array[j]>tsum:
                    break
            else:  # 上面循环正常结束才会执行，若上面循环执行break则这条语句不执行
                continue
            break
                
        if res:
            return res
        else:
            return []

43.左旋字符子串

题目：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

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

44.反转单词顺序(flag)

题目：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        ss=s.split(' ')
        return ' '.join(ss[::-1])

45.扑克牌顺序

题目：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的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

# -*- coding:utf-8 -*-
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        # 只需要判断没有0的数组里数值是唯一且max-min<5即可
        if len(numbers)<5 and not numbers:
            return False
        grost_num=0
        without_gro=[]
        for i in numbers:
            if i==0:
                grost_num+=1
            elif i in without_gro and i!=0: #唯一
                return False
            else:
                without_gro.append(i)
        if max(without_gro)-min(without_gro)<5:
            return True
        else:
            return False

46.孩子们的圈圈(圈圈中最后剩下的数)(flag)

题目：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)。

# -*- coding:utf-8 -*-
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        # flag=0
        # 把index想象为连续拼接数组
        if not n or not m:
            return -1
        num = list(range(n))
        index = 0
        while len(num)>1: # 剩余两个都要继续执行
            index=(index+m-1)%len(num) #index为上一次停的地方，加上m-1为重新第m-1个出列
            num.pop(index)
        return num[0]

47.求1+2+3+…+n

题目：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

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

48.不用加减乘除做加法

题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

思路：二进制异或进位。

# -*- coding:utf-8 -*-
class Solution:
    def Add(self, num1, num2):
        # write code here
        # 位操作不懂
        return sum([num1,num2])
        
# ============================
'''
首先看十进制是如何做的： 5+7=12，三步走
第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。

第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。

同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。

第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。

第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
     继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
'''
class Solution:
    def Add(self, num1, num2):
        # write code here
        while num2!=0:
            sum=num1^num2
            carry=(num1&num2)<<1
            num1=sum
            num2=carry
        return num1

49.把字符串转换成整数

题目：将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

输入描述：输入一个字符串,包括数字字母符号,可以为空输出描述:如果是合法的数值表达则返回该数字，否则返回0。

# -*- coding:utf-8 -*-
class Solution:
    def StrToInt(self, s):
        # write code here
        l=[s]
        try:
            num=list(map(eval,l))  
        except Exception as e:
            return 0
        else:
            return num[0]

50.数组中重复的数字

题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路：利用dict计算重复数字。

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

51.构建乘积数组

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

注意：没有A[i]

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        if not A:
            return None
        if len(A)==1:
            return None
        B=[None]*len(A)
        for i,e in enumerate(A):
            cumpower=1
            for ii,ee in enumerate(A):
                if ii!=i:
                    cumpower=cumpower*ee
            B[i]=cumpower
        return B

52.正则表达式匹配(flag)

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

思路:

当模式中的第二个字符不是 *时：

• 如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
• 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

当模式中的第二个字符是 *时：

• 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
• 如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式。
  • 模式后移2字符，相当于 x被忽略。即模式串中与他前面的字符和字符串匹配0次。
  • 字符串后移1字符，模式后移2字符。即模式串中*与他前面的字符和字符串匹配1次。
  • 字符串后移1字符，模式不变，即继续匹配字符下一位，因为 可以匹配多位。即模式串中与他前面的字符和字符串匹配多次。

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

53.表示数值的字符串

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

# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        l=[s]
        try:
            b=float(s)
            return True
        except Exception as e:
            return False

54.字符流中第一个不重复的字符(flag)

题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

输出描述：如果当前字符流没有存在出现一次的字符，返回#字符。

# -*- coding:utf-8 -*-
# flag=0
class Solution:
    # 返回对应char
    def __init__(self):
        self.s=''
        self.dict={}
    def FirstAppearingOnce(self):
        for i in self.s:
            if self.dict[i]==1:
                return i
        return '#'
        # write code here
    def Insert(self, char):
        # write code here
        self.s+=char
        if char in self.dict:
            self.dict[char]+=1
        else:
            self.dict[char]=1

55.链表中环的入口节点(flag)

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x;n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口：直线+小段环=整环，故p1再走整环-小段环到达起点。

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        fast,slow=pHead,pHead
        if fast and fast.next: 
            fast=fast.next.next
            slow=slow.next
        while fast and fast.next and fast!=slow:
            fast=fast.next.next
            slow=slow.next
        if not fast.next: 
            return None
        fast=pHead
        while fast!=slow:
            fast=fast.next
            slow=slow.next
        return fast

56.删除链表中重复的节点(flag)

题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留(全部删除)，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        result = ListNode(0)
        res = result
        tmp = pHead
        while tmp and tmp.next:
            if tmp.val == tmp.next.val:
                while tmp.next and tmp.val == tmp.next.val:
                    tmp = tmp.next
            else:
                res.next = tmp  #把整个tmp之后的链表都接上去了
                res = res.next
            tmp = tmp.next
        res.next = tmp
        return result.next
            
# 一开始res为{-1}，1和2不同，res.next = tmp得到{-1，1,2,3,3,4,4,5}，res和tmp指针往下
# 第二次2和3不同，res.next = tmp得到{-1，1，+，2,3,3,4,4,5}，+号前为res指针位置
# 第三次3和3相同，tmp指针到4的位置，下一次res.next=tmp得到{-1,1,2，+，4,4,5}

57. 二叉树中的下一个节点

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：分析二叉树的下一个节点，一共有以下情况：1.二叉树为空，则返回空；2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。

# -*- coding:utf-8 -*-
class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        if pNode.right:
            pNode=pNode.right
            while pNode.left:
                pNode=pNode.left
            return pNode

        else: #存在该节点在父节点右边，且一直递归，这时要找爷爷节点 型如"\"
            while pNode.next:
                if pNode.next.left==pNode:
                    return pNode.next
                else:
                    pNode=pNode.next
            return None

58.对称的二叉树(flag)

题目：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：采用递归的方法来判断两数是否相同。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#  设计一个递归求issame的函数,issame(root1.left,root2.right)
class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        if not pRoot.left and not pRoot.right:
            return True
        if pRoot.left and pRoot.right:
            return self.issame(pRoot.left,pRoot.right)
        else:
            return False
        # write code here
    def issame(self, root1, root2):
        if not root1 and not root2:
            return True
        if root1 and root2:
            if root1.val==root2.val:
                return self.issame(root1.left,root2.right) and self.issame(root2.left,root1.right)
        else:
            return False

59.按之字形顺序打印二叉树(flag)

题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def Print(self, pRoot):
        # write code here
        res=[]
        if not pRoot:
            return []
        level=[pRoot]
        reverseflag=False
        while level:
            levelvalue=[]
            nextlevel=[]
            for i in level:
                levelvalue.append(i.val)
                if i.left:
                    nextlevel.append(i.left)
                if i.right:
                    nextlevel.append(i.right)
            if reverseflag:
                levelvalue.reverse()
            if levelvalue:
                res.append(levelvalue)
                # for j in levelvalue:
                #     res.append(j) 
            reverseflag = not reverseflag
            level=nextlevel
        return res

60.把二叉树打印成多行

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

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
from collections import deque
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res=[]
        level = [pRoot]
        while level:
            levelvalue=[]
            nextlevel=[]
            for i in level:
                levelvalue.append(i.val)
                if i.left:
                    nextlevel.append(i.left)
                if i.right:
                    nextlevel.append(i.right)
            if levelvalue:
                res.append(levelvalue)
            level = nextlevel
        return res

61.序列化二叉树(flag)

题目：请实现两个函数，分别用来序列化和反序列化二叉树。

思路：转变成前序遍历，空元素利用”#”代替，然后进行解序列。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#序列化指的是遍历二叉树为字符串；所谓反序列化指的是依据字符串重新构造成二叉树。
#当在遍历二叉树时碰到Null指针时，这些Null指针被序列化为一个特殊的字符“#”,结点之间的数值用逗号隔开。
class Solution:
    def Serialize(self, root):
        def Pre_Order(root):
            if root:
                result.append(str(root.val))
                Pre_Order(root.left)
                Pre_Order(root.right)
            else:
                result.append('#')
        result = []
        Pre_Order(root)
        return ','.join(result)
 
        # write code here
    def Deserialize(self, s):
        s = s.split(',')
         
        def Change(num):
            num[0] += 1
            if num[0] < len(s):
                if s[num[0]] == '#':
                    return None
                root = TreeNode(int(s[num[0]]))
                root.left = Change(num)
                root.right = Change(num)
                return root
            else:
                return None
        num = [-1]
        return Change(num)

62.二叉搜索树中的第K个节点

题目：给定一棵二叉搜索树，请找出其中的第k小的结点。例如（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

思路：中序遍历后，返回第K个节点值。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回对应节点TreeNode
    def __init__(self):
        self.res = []
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot:
            return None
        #pnode=pRoot  # 为啥要加这一句呢？
        self.sorttree(pRoot)
        if len(self.res)<k or k<=0:
            return None
        else:
            return self.res[k-1]
        
    def sorttree(self,pRoot): # 中序排序
        if not pRoot:
            return []
        left = self.sorttree(pRoot.left)
        self.res.append(pRoot)
        right = self.sorttree(pRoot.right)

63.数据流中的中位数

题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr=[]
    def Insert(self, num):
        # write code here
        self.arr.append(num)
    def GetMedian(self,arr): #为啥这里要加 arr 作为输入,换为其他参数也行，必须要占位？
        # write code here
        res=sorted(self.arr)
        if len(res)%2==0:
            return (res[len(res)//2-1]+res[len(res)//2])/2.0
        else:
            return res[len(res)//2]

64.滑动窗口的最大值

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

# -*- coding:utf-8 -*-
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size<=0:
            return []
        if size==1:
            return num
        res=[]
        for i in range(len(num)-size+1):
            res.append(max(num[i:i+size]))
        return res

65.矩阵中的路径(flag)

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

思路：当起点第一个字符相同时，开始进行递归搜索，设计搜索函数。

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        for i in range(rows):
            for j in range(cols):
                if matrix[i*cols+j]==path[0]:
                    if self.findpath(list(matrix),rows,cols,path[1:],i,j):
                        return True
        return False
    def findpath(self, matrix, rows, cols, path ,i ,j):
        if not path:
            return True
        matrix[i*cols+j]='0'
        if j+1<cols and matrix[i*cols+j+1]==path[0]:  #j+1<cols 这里是下标，不能等于
            return self.findpath(matrix, rows, cols, path[1:],i,j+1)
        elif j-1>=0 and matrix[i*cols+j-1]==path[0]:
            return self.findpath(matrix, rows, cols, path[1:],i,j-1)
        elif i+1<rows and matrix[(i+1)*cols+j]==path[0]:
            return self.findpath(matrix, rows, cols, path[1:],i+1,j)
        elif i-1>=0 and matrix[(i-1)*cols+j]==path[0]:
            return self.findpath(matrix, rows, cols, path[1:],i-1,j)
        else:
            return False

66.机器人的运动范围

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

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        # 回溯的出口 ： 所有self.findgrid回溯出口的不满足if条件就停止
        matrix = [[0 for i in range(cols)] for j in range(rows)]
        count = self.findgrid(threshold,rows,cols,matrix,0,0)
        return count
     
    def findgrid(self,threshold,rows,cols,matrix,i,j):
        count = 0
        if 0<=i<rows and 0<=j<cols and (sum(map(int, str(i) + str(j))) <= threshold) and matrix[i][j]==0:
            matrix[i][j] = 1
            count = 1 + self.findgrid(threshold,rows,cols,matrix,i,j-1)\
            + self.findgrid(threshold,rows,cols,matrix,i,j+1)\
            + self.findgrid(threshold,rows,cols,matrix,i+1,j)\
            + self.findgrid(threshold,rows,cols,matrix,i-1,j)
        return count