剑指offer的python解答合集（持续更新）

被疫情困在家里，没事刷刷剑指offer的题目，这里写一个题解合集，还没更完
20190129：搞定15道

面试题3：数组中重复的数字

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

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

面试题4：二维数组中查找

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

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

面试题5：替换空格

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

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

面试题6：从尾到头打印链表

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

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

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

面试题7：重建二叉树

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

# -*- 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):
        # write code here
        if len(pre) == 0:
            return None
        root_val = pre[0]
        root = TreeNode(root_val)
        idx = tin.index(root_val)
        if idx == 0:
            left_tree = None
        else:
            left_tree = self.reConstructBinaryTree(pre[1:idx+1], tin[:idx])
        if idx == len(pre) - 1:
            right_tree = None
        else:
            right_tree = self.reConstructBinaryTree(pre[idx+1:], tin[idx+1:])
        root.left = left_tree
        root.right = right_tree
        return root

面试题8：二叉树的下一个节点

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

# -*- 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 pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        while pNode:
            if pNode.next:
                if pNode.next.left == pNode:
                    return pNode.next
                pNode = pNode.next
            else:
                return None

面试题9：用两个栈实现队列

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

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

面试题10：斐波那契数列

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

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n <= 0:
            return 0
        if n == 1:
            return 1
        i = 2
        a, b = 0, 1
        while i <= n:
            s = a + b
            a, b = b, s
            i += 1
        return s

面试题11：旋转数组的最小数字

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

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        left = 0
        right = len(rotateArray) - 1
        while left < right:
            if rotateArray[left]<rotateArray[right]:
                return rotateArray[left]
            mid = (right + left) // 2
            if rotateArray[left] < rotateArray[mid]:
                left = mid
            elif rotateArray[mid] > rotateArray[right]:
                right = mid
            else:
                right -= 1
        return rotateArray[mid+1]

面试题12：矩阵中的路径

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

# -*- coding:utf-8 -*-
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        for i in range(len(matrix)):
            if matrix[i] == path[0]:
                if self.isPath(matrix, rows, cols, i, path):
                    return True
        return False
    
    def isPath(self, matrix, rows, cols, i, path):
        if matrix[i] != path[0]:
            return False
        if len(path) == 1:
            return True
        # 可以设置一个矩阵，来标志某一格子是否已经被走过
        matrix = matrix[:i] + '#' + matrix[i+1:]
        up = self.isPath(matrix, rows, cols, i-cols, path[1:]) if i >= cols else False
        down = self.isPath(matrix, rows, cols, i+cols, path[1:]) if i < len(matrix) - cols else False
        right = self.isPath(matrix, rows, cols, i+1, path[1:]) if ((i+1) % cols != cols and i+1 < len(matrix)) else False
        left = self.isPath(matrix, rows, cols, i-1, path[1:]) if (i % cols != cols and i-1>0) else False
        return up or down or left or right

面试题13：机器人的运动范围

• 题目描述
  地上有一个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
        return len(self.spaceCount(set(), 0, 0, threshold, rows, cols))
        
    def spaceCount(self, re, i, j, threshold, rows, cols):
        if self.get_bitsum(i) + self.get_bitsum(j) > threshold or (i, j) in re:
            return re
        re.add((i,j))
        if i + 1 < rows:
            re = self.spaceCount(re, i+1, j, threshold, rows, cols)
        if j + 1 < cols:
            re = self.spaceCount(re, i, j+1, threshold, rows, cols)
        return re

    def get_bitsum(self, num):
        s = 0
        while num>0:
            s += num % 10
            num = num // 10
        return s

面试题14：剪绳子

• 题目描述
  给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number < 2: return 0
        if number == 2:return 1
        if number == 3:return 2
        products = [0, 1, 2, 3]
        for i in range(4, number+1, 1):
            product = 0
            for j in range(1,i//2+1):
                res = products[j]* products[i-j]
                product = max(res,product)
                products.append(product)
        return products[-1]

面试题15：二进制中1的个数

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

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