剑指Offer - Python题解

作者: deactivateuser | 来源:发表于2019-07-19 15:10 被阅读0次

1. 二维数组中的查找

题目描述

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

class Solution:
    # array 二维列表
    def Find(self, target, array):
        rowNum = len(array)
        columnNum = len(array[0])
        for p in range(rowNum):
            for q in range(columnNum):
                if target == array[p][q]:
                    return True
        return False

2. 替换空格

题目描述

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

class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        return s.replace(" ", "%20")

3. 从头到尾打印链表

题目描述

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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

4. 重建二叉树

题目描述

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

思路：前序遍历的第一个节点即为树的root，然后在中序遍历中找到这个节点，这个节点左边的即为left subtree，右边的即为right subtree。
例：{1,2,4,7,3,5,6,8}中1为root，{4,7,2,1,5,3,8,6}中{4,7,2}即为left subtree，{5,3,8,6}即为right subtree。

# 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 or len(tin)==0 :
            return None
        elif len(pre)==1 and len(tin)==1 :
            return TreeNode(pre[0])
        else:
            root = TreeNode(pre[0])
            root.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[0:tin.index(pre[0])])
            root.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
            return root

5. 用两个栈实现队列

题目描述

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

思路：push到stack1，从stack2来pop，stack2空了再加。

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

6. 旋转数组的最小数字

题目描述

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

思路：如果后一个数比前一个数小，则其为最小的数。

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return 0
        for i in range(len(rotateArray)):
            if rotateArray[i] > rotateArray[i+1]:
                return rotateArray[i+1]

7. 斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

参考：斐波那契数列的5种python写法

class Solution:
    def Fibonacci(self, n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a+b
        return a

8. 跳台阶

题目描述

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

思路：Fibonacci的应用

class Solution:
    def jumpFloor(self, number):
        a, b = 0, 1
        for i in range(number+1):
            a, b = b, a+b
        return a

9. 变态跳台阶

题目描述

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

思路：算出通项公式。f(n) = 2f(n - 1)

class Solution:
    def jumpFloorII(self, number):
        return 2**(number - 1)

10. 矩形覆盖

题目描述

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

class Solution:
    def rectCover(self, number):
        if number == 0:
            return 0
        a, b = 0, 1
        for i in range(number+1):
            a, b = b, a+b
        return a

11. 二进制中1的个数

题目描述

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

思路：python的负数的补码表示方法。
参考：Python小技巧：负数的补码表示

class Solution:
    def NumberOf1(self, n):
        count = 0
        if n >= 0:
            string = str(bin(n).replace('0b',''))
            for i in range(len(string)):
                if '1' == string[i]:
                    count += 1
            return count
        else:
            string = str(bin(((1 << 32) - 1) & n)[2:].zfill(32).replace('0b',''))
            for i in range(len(string)):
                if '1' == string[i]:
                    count += 1
            return count

12. 数值的整数次方

题目描述

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

class Solution:
    def Power(self, base, exponent):
        return base ** exponent

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

题目描述

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

class Solution:
    def reOrderArray(self, array):
        even, odd = [], []
        for i in range(len(array)):
            if array[i] % 2 == 0:
                even.append(array[i])
            else:
                odd.append(array[i])
        return odd + even

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

题目描述

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

思路：两个指针，一个先走k步，当第一个指针到最后了，第二个指针即为倒数第k个节点。

class Solution:
    def FindKthToTail(self, head, k):
        pre = post = head
        for i in range(k):
            if pre == None:
                return None
            pre = pre.next
        while pre != None:
            pre = pre.next
            post = post.next
        return post

15. 反转链表

题目描述

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

参考 https://www.javazhiyin.com/32787.html

class Solution:
    def ReverseList(self, pHead):
        if pHead == None:
            return None
        last = None
        while pHead:
            temp = pHead.next
            pHead.next = last
            last = pHead
            pHead = temp
        return last

16. 合并两个排序的链表

题目描述

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

class Solution:
    def Merge(self, pHead1, pHead2):
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        pHead = None
        if pHead1.val > pHead2.val:
            pHead = pHead2
            pHead.next = self.Merge(pHead1, pHead2.next)
        else:
            pHead = pHead1
            pHead.next = self.Merge(pHead1.next, pHead2)
        return pHead

17. 树的子结构

题目描述

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

class Solution:
    def Tree1HasTree2(self, tree1, tree2):
        if tree2 == None:
            return True
        if tree1 == None:
            return False
        if tree1.val != tree2.val:
            return False
        return self.Tree1HasTree2(tree1.left, tree2.left) and self.Tree1HasTree2(tree1.right, tree2.right)
    
    
    def HasSubtree(self, pRoot1, pRoot2):
        result = False
        if pRoot1 != None and pRoot2 != None:
            if pRoot1.val == pRoot2.val:
                result = self.Tree1HasTree2(pRoot1, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.left, pRoot2)
            if not result:
                result = self.HasSubtree(pRoot1.right, pRoot2)
        return result

18. 二叉树的镜像

题目描述

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

输入描述:
二叉树的镜像定义：

源二叉树
镜像二叉树

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

19. 顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

参考 https://www.runoob.com/python3/python3-func-zip.html
https://blog.csdn.net/weixin_41679411/article/details/86484570

class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        return matrix and list(matrix.pop(0)) + self.printMatrix(list(zip(*matrix))[::-1])

20. 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。

参考https://blog.csdn.net/qq_34364995/article/details/81451186

class Solution:
    def __init__(self):
        self.stack=[]
        self.min_stack=[]
        self.min_number = float('inf')
        
    def push(self, node):
        if node < self.min_number:
            self.min_number = node
            self.min_stack.append(self.min_number)
        self.stack.append(node)
        
    def pop(self):
        if self.stack != []:
            if self.stack[-1] == self.min_number:
                self.min_stack.pop()
            self.stack.pop(-1)
            
    def top(self):
        if self.stack != []:
            return self.stack[-1]
        else:
            return None
    
    def min(self):
        return self.min_stack[-1]

21. 栈的压入、弹出序列

题目描述

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

构造一个辅助栈来判断弹出序列是不是和压栈序列对应。首先遍历压栈序列的元素push到辅助栈，判断是不是弹出序列的首元素，如果是，则弹出序列pop首元素（指针后移），如果不是，则继续push，再接着判断；直到遍历完了压栈序列，如果辅助栈或者弹出序列为空，则返回True，否则返回False。

class Solution:
    def IsPopOrder(self, pushV, popV):
        stack = []
        for each in pushV:
            stack.append(each)
            while stack and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
        if stack == []:
            return True
        else:
            return False

22. 从上往下打印二叉树

题目描述

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

class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        node_list = [root]
        result = []
        if not root:
            return result
        while node_list:
            current_root = node_list.pop(0)
            result.append(current_root.val)
            if current_root.left:
                node_list.append(current_root.left)
            if current_root.right:
                node_list.append(current_root.right)
        return result

23. 二叉搜索树的后序遍历序列

题目描述

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

二叉搜索树是对一个有序数组进行二分查找形成的搜索树，它指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

任意节点的左、右子树也分别为二叉查找树；'

特点：左子树结点的值都小于根节点的值，右子树结点的值都大于根节点的值
后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问根节点
后序遍历得到的序列，最后一个数是树的根节点的值，序列中最后一个数前面的数可以分为两部分：一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值要大。

class Solution:
    def VerifySquenceOfBST(self, sequence):
        if len(sequence) == 0:
            return False
        root = sequence[-1]
        for split_index in range(len(sequence)):
            if sequence[split_index] > root:
                break
        for temp in range(split_index, len(sequence)):
            if sequence[temp] < root:
                return False
        left, right = True, True
        left = self.VerifySquenceOfBST(sequence[0:split_index])
        if left and split_index < len(sequence) - 1:
            right = self.VerifySquenceOfBST(sequence[split_index:-1])
        return right

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

题目描述

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

思路：

如果只有根节点或者找到叶子节点，我们就把其对应的val值返回

如果不是叶子节点，我们分别对根节点的左子树、右子树进行递归，直到找到叶子结点。然后遍历把叶子结点和父节点对应的val组成的序列返回上一层；如果没找到路径，其实也返回了序列，只不过是[]

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        result = []
        if not root:
            return result
        if not root.left and not root.right and root.val == expectNumber:
            return [[root.val]]
        else:
            left = self.FindPath(root.left, expectNumber - root.val)
            right = self.FindPath(root.right, expectNumber - root.val)
            for item in left + right:
                result.append([root.val] + item)
        return result

25. 复杂链表的复制

题目描述

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

思路：第一步在原链表的基础上复制节点，将节点复制在原节点的后面。第二步复制随机节点。第三步将新旧链表分离。

三步

class Solution:
    def Clone(self, pHead):
        if pHead == None:
            return None
        # Step 1
        pCur = pHead
        while pCur:
            node = RandomListNode(pCur.label)
            node.next = pCur.next
            pCur.next = node
            pCur = node.next
        # Step 2
        pCur = pHead
        while pCur:
            if pCur.random != None:
                pCur.next.random = pCur.random.next
            pCur = pCur.next.next
        # Step 3
        head = pHead.next
        cur = head
        pCur = pHead
        while pCur:
            pCur.next = pCur.next.next
            if cur.next != None:
                cur.next = cur.next.next
            cur = cur.next
            pCur = pCur.next
        return head

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

题目描述

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

Illustration

思路：核心算法依旧是中序遍历；不是从根节点开始，而是从中序遍历得到的第一个节点开始；定义两个辅助节点listHead(链表头节点)、listTail(链表尾节点)。事实上，二叉树只是换了种形式的链表；listHead用于记录链表的头节点，用于最后算法的返回；listTail用于定位当前需要更改指向的节点。

参考：https://blog.csdn.net/u010005281/article/details/79657259

class Solution:
    def __init__(self):
        self.listHead = None
        self.listTail = None
    
    def Convert(self, pRootOfTree):
        if pRootOfTree == None:
            return
        self.Convert(pRootOfTree.left)
        if self.listHead == None:
            self.listHead = pRootOfTree
            self.listTail = pRootOfTree
        else:
            self.listTail.right = pRootOfTree
            pRootOfTree.left = self.listTail
            self.listTail = pRootOfTree
        self.Convert(pRootOfTree.right)
        return self.listHead

27. 字符串的排列

题目描述

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

输入描述:

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

思路：化繁为简，像青蛙跳台阶的思想那样，无论输入的字符串有多长，其排列出来的组合式样式均可分为“第一个字符串+剩下的字符串”的样式，可以通过遍历赋予第一位上不同的字符。那剩下的字符串又可以如上分解。

注意：ss的索引字符串会超出范围，不过python在对字符串做切片操作时，当索引位置超出长度，python不会报错只会跳出本次循环。当然我们还要考虑字符串中是否包含重复元素，因为在输入中有重复值时就会生产相同的字符串，因此在代码中加一个判断即可。

class Solution:
    def Permutation(self, ss):
        result = []
        if len(ss) <= 1:
            return ss
        for i in range(len(ss)):
            for j in map(lambda x: ss[i] + x, self.Permutation(ss[:i]+ss[i+1:])):
                if j not in result:
                    result.append(j)
        return result

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

题目描述

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

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        numbers = sorted(numbers)
        count = 0
        for each in range(len(numbers)):
            if numbers[each] == numbers[len(numbers) // 2]:
                count = count + 1
        if count > len(numbers)/2:
            return numbers[len(numbers) // 2]
        else:
            return 0

29. 最小的k个数

题目描述

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

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        return sorted(tinput)[:k] if len(tinput) >= k else []

30. 连续子数组的最大和

题目描述

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

有个最优子结构性质：DP[i] = max{DP[i-1] + A[i], A[i]}

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        res = max(array)
        temp = 0
        for each in array:
            temp = max(each, temp + each)
            res = max(temp, res)
        return res

31. 整数中1出现的次数（从1到n整数中1出现的次数）

题目描述

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

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        number_string = ''
        for each in range(1, n+1):
            number_string = number_string + str(each)
        return len(number_string) - len(number_string.replace('1', ''))

32. 把数组排成最小的数

题目描述

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

class Solution:
    def PrintMinNumber(self, numbers):
        if numbers is None or len(numbers) == 0:
            return ''
        numbers = map(str, numbers)
        numbers.sort(cmp = lambda x, y : cmp(x + y, y + x))
        return ''.join(numbers).lstrip()

33. 丑数

题目描述

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

参考：https://blog.csdn.net/weixin_36372879/article/details/84871967

class Solution:
    def GetUglyNumber_Solution(self, index):
        if index < 1:
            return 0
        if index == 1:
            return 1
        uglyNumberList = [1]
        t2, t3, t5 = 0, 0, 0
        for i in range(1, index):
            if uglyNumberList[t2] * 2 <= uglyNumberList[i-1]:
                t2 += 1
            if uglyNumberList[t3] * 3 <= uglyNumberList[i-1]:
                t3 += 1
            if uglyNumberList[t5] * 5 <= uglyNumberList[i-1]:
                t5 += 1
            uglyNumber = min(uglyNumberList[t2]*2,uglyNumberList[t3]*3,uglyNumberList[t5]*5)
            uglyNumberList.append(uglyNumber)
        return uglyNumberList[index - 1]

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

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

class Solution:
    def FirstNotRepeatingChar(self, s):
        if not s or len(s)>10000:
            return -1
        for each in s:
            if s.count(each) == 1:
                return s.index(each)

35. 数组中的逆序对

题目描述

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

输入描述:

题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

示例1

输入：1,2,3,4,5,6,7,0
输出：7

超过运行时间限制。

class Solution:
    def InversePairs(self, data):
        count = 0
        while len(data)>1:
            min_data_index = data.index(min(data))
            count += min_data_index
            data.pop(min_data_index)
        return count%1000000007

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

题目描述

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

思路：

如果两个链表长度一样，则正常遍历，找到相同的或者不存在。

如果两个链表长度不同，则首先短的遍历结束后会从另一个链表开头开始遍历，而当另一个节点遍历结束后从另一个链表头开始遍历时，这两个链表的差则会消除。

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        p1 = pHead1
        p2 = pHead2
        while p1 != p2:
            p1 = pHead2 if p1 is None else p1.next
            p2 = pHead1 if p2 is None else p2.next
        return p1

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

题目描述

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

class Solution:
    def GetNumberOfK(self, data, k):
        return data.count(k)

38. 二叉树的深度

题目描述

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

class Solution:
    def TreeDepth(self, pRoot):
        if pRoot == None:
            return 0
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        return max(left, right) + 1

39. 平衡二叉树

题目描述

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

class Solution:
    def IsBalanced_Solution(self, pRoot):
        if pRoot == None:
            return True
        left_depth = self.TreeDepth(pRoot.left)
        right_depth = self.TreeDepth(pRoot.right)
        if abs(left_depth - right_depth) > 1:
            return False
        return True
        
    def TreeDepth(self, pRoot):
        if pRoot == None:
            return 0
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        return max(left, right) + 1

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

题目描述

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

class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        result = []
        for each in array:
            if array.count(each) == 1:
                result.append(each)
        return result

41. 和为s的连续正数序列

题目描述

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

输出描述

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

class Solution:
    def FindContinuousSequence(self, tsum):
        result = []
        for i in range(1, tsum // 2 + 1):
            t_sum = 0
            for j in range(i, tsum // 2 + 2):
                t_sum += j
                if t_sum == tsum:
                    result.append(list(range(i,j+1)))
        return result

42. 和为S的两个数字

题目描述

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

输出描述

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

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        result = []
        for i in range(len(array)):
            for j in range(len(array)-1, i-1, -1):
                if array[i] + array[j] == tsum:
                    result.append(array[i])
                    result.append(array[j])
                    return result
        return result

43. 左旋转字符串

题目描述

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

class Solution:
    def LeftRotateString(self, s, n):
        if s == '':
            return ''
        s_list = list(s)
        for i in range(n):
            temp = s_list.pop(0)
            s_list.append(temp)
        return ''.join(str(i) for i in s_list)

44. 翻转单词顺序列

题目描述

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

class Solution:
    def ReverseSentence(self, s):
        s_list = s.split(' ')
        return ' '.join(str(i) for i in s_list[::-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。

得到hash表后只需计算最大的键值和最小的键值的差，若小于5，不需考虑有多少大小王，都可以组成顺子。

class Solution:
    def IsContinuous(self, numbers):
        if len(numbers) != 5:
            return False
        cards = {}
        for each in numbers:
            if each == 0:
                continue
            if each in cards.keys():
                return False
            else:
                cards[each] = 1
        if max(cards.keys()) - min(cards.keys()) < 5:
            return True
        else:
            return False

46. 孩子们的游戏（圆圈中最后剩下的数）

题目描述

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

约瑟夫环问题
参考：https://blog.csdn.net/fuxuemingzhu/article/details/79702974

class Solution:
    def LastRemaining_Solution(self, n, m):
        if n < 1 or m < 1:
            return -1
        result = 0
        for i in range(2, n+1):
            result = (result + m) % i
        return result

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

题目描述

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

class Solution:
    def Sum_Solution(self, n):
        result = n
        temp = (n > 1 and self.Sum_Solution(n - 1))
        result = result + temp
        return result

48. 不用加减乘除做加法

题目描述

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

参考：https://www.acwing.com/activity/content/code/content/21074/

class Solution:
    def Add(self, num1, num2):
        while True:
            # 不进位加法
            s = num1 ^ num2
            # 计算进位
            carry = num1 & num2

            # 手动把高于 32 位的部分变成 0
            num1 = s & 0xFFFFFFFF
            num2 = carry << 1

            if carry == 0:
                break
        # 如果是正数和 0 ，就直接返回这个正数
        if num1 >> 31 == 0:
            return num1
        # 如果是负数
        return num1 - (1 << 32)

49. 把字符串转换成整数

题目描述

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

输入描述:

输入一个字符串,包括数字字母符号,可以为空

输出描述:

如果是合法的数值表达则返回该数字，否则返回0

示例1

输入
+2147483647
1a33

输出
2147483647
0

50. 数组中重复的数字

题目描述

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

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

51. 构建乘机数组

题目描述

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

class Solution:
    def multiply(self, A):
        if not A:
            return []
        B = [1 for _ in range(len(A))]
        for i in range(1, len(A)):
            B[i] = B[i-1] * A[i-1]
        temp = 1
        for i in range(len(A)-2, -1, -1):
            temp *= A[i+1]
            B[i] *= temp
        return B

52. 正则表达式匹配

题目描述

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

参考：https://blog.csdn.net/u010005281/article/details/80200492

class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        if s == pattern:
            return True
        if len(pattern) > 1 and pattern[1] == '*':
            if s and (s[0] == pattern[0] or pattern[0] == '.'):
                return self.match(s, pattern[2:]) or self.match(s[1:], pattern)
            else:
                return self.match(s, pattern[2:])
        elif s and pattern and (s[0] == pattern[0] or pattern[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"都不是。

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

题目描述

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

输出描述:

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

class Solution:
    def __init__(self):
        self.char_dic = {}
        self.char_s = ''
    
    def FirstAppearingOnce(self):
        for each in self.char_s:
            if self.char_dic[each] == 1:
                return each
        return '#'
        
        
    def Insert(self, char):
        if char not in self.char_dic.keys():
            self.char_dic[char] = 1
        else:
            self.char_dic[char] += 1
        self.char_s += char

55. 链表中环的入口结点

题目描述

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

56. 删除链表中重复的结点

题目描述

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

57. 二叉树的下一个结点

题目描述

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

分三种情况：

给定的节点为空——返回空；

给定的节点有右子树——沿着该右子树，返回右子树的第一个左叶子节点；

给定的节点没有右子树——如果位于某个节点的左子树中，则上溯直至找到该节点；否则就返回空。

class Solution:
    def GetNext(self, pNode):
        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 == pNode.next.left:
                    return pNode.next
                pNode = pNode.next
        return None

58. 对称的二叉树

题目描述

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

class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        return self.checkSymmetrical(pRoot.left, pRoot.right)
        
    def checkSymmetrical(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        return self.checkSymmetrical(left.left, right.right) and self.checkSymmetrical(left.right, right.left)

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

题目描述

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

class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        i = -1
        result_list = []
        current_layer = [pRoot]
        while current_layer:
            i *= -1
            current_list = []
            next_layer = []
            for node in current_layer:
                current_list.append(node.val)
                if node.left:
                    next_layer.append(node.left)
                if node.right:
                    next_layer.append(node.right)
            result_list.append(current_list[::i])
            current_layer = next_layer
        return result_list

60. 把二叉树打印成多行

题目描述

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

class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        if not pRoot:
            return []
        
        result_list = []
        current_layer = [pRoot]
        
        while current_layer:
            current_list = []
            next_layer = []
            for node in current_layer:
                current_list.append(node.val)
                if node.left:
                    next_layer.append(node.left)
                if node.right:
                    next_layer.append(node.right)
            result_list.append(current_list)
            current_layer = next_layer
        return result_list

61. 序列化二叉树

题目描述

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

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

class Solution:
    def Serialize(self, root):
        if not root:
            return '#'
        return str(root.val) + ',' + self.Serialize(root.left) + ',' + self.Serialize(root.right)
    
    def Deserialize(self, s):
        s_list = s.split(',')
        return self.DeserializeTree(s_list)
    
    def DeserializeTree(self, s_list):
        if len(s_list) == 0:
            return None
        value = s_list.pop(0)
        root = None
        if value != '#':
            root = TreeNode(int(value))
            root.left = self.DeserializeTree(s_list)
            root.right = self.DeserializeTree(s_list)
        return root

62. 二叉搜索树的第k个结点

题目描述

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

class Solution:
    count = 0
    def KthNode(self, pRoot, k):
        if not pRoot:
            return None
        node = self.KthNode(pRoot.left, k)
        if node:
            return node
        self.count += 1
        if self.count == k:
            return pRoot
        node = self.KthNode(pRoot.right, k)
        if node:
            return node

63. 数据流中的中位数

题目描述

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

class Solution:
    def __init__(self):
        self.arr = []
    def Insert(self, num):
        self.arr.append(num)
        self.arr.sort()
    def GetMedian(self, n=None):
        length = len(self.arr)
        if length % 2 == 1:
            return self.arr[length//2]
        else:
            return (self.arr[length//2 - 1] + self.arr[length//2]) / 2.0

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]}。

class Solution:
    def maxInWindows(self, num, size):
        result = []
        if not num or len(num) < size or size < 1:
            return result
        for i in range(len(num)-size + 1):
            result.append(max(num[i:i+size]))
        return result

65. 矩阵中的路径

题目描述

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

回溯法
参考：https://blog.csdn.net/qq_20141867/article/details/81065793

class Solution:
    def hasPath(self, matrix, rows, cols, path):
        if len(matrix) == 0 or len(matrix) != rows * cols or len(path) == 0:
            return False
        visited = [False] * len(matrix)
        pathLengthFound = 0
        for x in range(cols):
            for y in range(rows):
                if self.hasPathAlgorithm(matrix, rows, cols, path, x, y, visited, pathLengthFound):
                    return True
        return False
    
    def hasPathAlgorithm(self, matrix, rows, cols, path, x, y, visited, pathLengthFound):
        if pathLengthFound == len(path):
            return True
        current_haspath = False
        if 0 <= x <cols and 0 <= y < rows and matrix[y * cols + x] == path[pathLengthFound] and not visited[y * cols + x]:
            visited[y * cols + x] = True
            pathLengthFound += 1
            current_haspath = self.hasPathAlgorithm(matrix, rows, cols, path, x-1, y, visited, pathLengthFound) or self.hasPathAlgorithm(matrix, rows, cols, path, x, y-1, visited, pathLengthFound) or self.hasPathAlgorithm(matrix, rows, cols, path, x+1, y, visited, pathLengthFound) or self.hasPathAlgorithm(matrix, rows, cols, path, x, y+1, visited, pathLengthFound)
            
            if not current_haspath:
                pathLengthFound -= 1
                visited[y * cols + x] = False
        return current_haspath

66. 机器人的运动范围

题目描述

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

回溯法

class Solution:
    def movingCount(self, threshold, rows, cols):
        matrix = [[0 for _ in range(cols)] for _ in range(rows)]
        count = self.find_grid(threshold, rows, cols, matrix, 0, 0)
        return count
        
    def find_grid(self, threshold, rows, cols, matrix, x, y):
        count = 0
        if 0 <= x < rows and 0 <= y < cols and matrix[x][y] == 0 and self.judge(threshold, x, y):
            matrix[x][y] = 1
            count = 1 + self.find_grid(threshold, rows, cols, matrix, x-1, y) + self.find_grid(threshold, rows, cols, matrix, x, y-1) + self.find_grid(threshold, rows, cols, matrix, x+1, y) + self.find_grid(threshold, rows, cols, matrix, x, y+1)
        return count
    
    def judge(self, threshold, x, y):
        if sum(map(int, str(x) + str(y))) <= threshold:
            return True
        else:
            return False