剑指 Offer 03. 数组中重复的数字

题目

答案

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i, num in enumerate(nums):
            while nums[i] != i:
                m = nums[i]
                if nums[m] == m:
                    return m
                else:
                    nums[i] = nums[m]
                    nums[m] = m
        return -1

解析

剑指 Offer 04. 二维数组中的查找

题目

答案

class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if target == matrix[i][j]:
                return True
        return False

def findNumberIn2DArray(matrix, target):
    i, j = len(matrix) - 1, 0
    while i >= 0 and j < len(matrix[0]):
        if target > matrix[i][j]:
            j += 1
        elif target < matrix[i][j]:
            i -= 1
        else:
            return True
    return False

解析

剑指 Offer 05.替换空格

题目

答案

class Solution(object):
    def replaceSpace(self, s):
        """
        :type s: str
        :rtype: str
        """
        return s.replace(" ", "%20")

剑指 Offer 06. 从尾到头打印链表

题目

答案

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reversePrint(self, head):
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        return stack[::-1]

解析

这道题使用了栈这种数据结构，我们先将链表中的元素从头到尾依次入栈，在代码中表示就是stack.append(head.val)。

然后将栈中的元素依次出栈，在Python中我们只需要使用反转链表即可stack[::-1]。

剑指 Offer 07. 重建二叉树

题目

实例一：
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

实例二：
Input: preorder = [-1], inorder = [-1]
Output: [-1]

答案

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        index = {}
        for i, val in enumerate(inorder):
            index.setdefault(val, i)  

        def recur(rootInd, leftInd, rightInd):
            if leftInd > rightInd: 
                return None
            rootVal = preorder[rootInd]
            inRootInd = index[rootVal]
            root = TreeNode(rootVal)
            root.left = recur(rootInd+1, leftInd, inRootInd-1)
            root.right = recur(rootInd + (inRootInd-leftInd) + 1, inRootInd+1, rightInd)
            return root
        return recur(0, 0, len(inorder)-1)

解析

剑指 Offer 09. 用两个栈实现队列

题目

答案

class CQueue(object):
    def __init__(self):
        self.S_in = []
        self.S_out = []
    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.S_in.append(value)
    def deleteHead(self):
        """
        :rtype: int
        """
        if self.S_out == []:
            while self.S_in != []:
                self.S_out.append(self.S_in.pop())
        if self.S_out != []:
            return self.S_out.pop()
        else:
            return -1

解析

剑指 Offer 10. 斐波那契数列

题目

答案

class Solution:
    def fib(self, n: int) -> int:
        x, y = 0, 1
        while n != 0:
            y = x + y
            x = y - x
            n -= 1
        return x % 1000000007

解析

剑指 Offer 11. 旋转数组的最小数字

题目

答案

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        i, j = 0, len(numbers)-1
        while i < j:
            m = (i + j) // 2
            if numbers[m] > numbers[j]:
                i = m + 1
            elif numbers[m] < numbers[j]:
                j = m
            else:
                j -= 1
        return numbers[j]

解析

剑指 Offer 12. 矩阵中的路径

题目

答案

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]
        def bfs(i, j, k):
            if k == len(word):
                return True
            if i < 0 or i >= m:
                return False
            if j < 0 or j >= n:
                return False
            if visited[i][j]:
                return False
            if word[k] != board[i][j]:
                return False
            visited[i][j] = True
            res = bfs(i+1, j, k+1) or bfs(i-1, j, k+1) or bfs(i, j+1, k+1) or bfs(i, j-1, k+1)
            visited[i][j] = False
            return res
        for i in range(m):
            for j in range(n):
                if bfs(i, j, 0):
                    return True
        return False

解析

剑指 Offer 13. 机器人的运动范围

题目

答案

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def sum(i, j):
            res = 0
            while i:
                res += i%10
                i //= 10
            while j:
                res += j%10
                j //= 10
            return res
        visited = set()
        def dfs(i, j):
            if i >= m or j >= n or sum(i, j) > k or (i, j) in visited:
                return 0
            visited.add((i, j))
            return 1 + dfs(i+1, j) + dfs(i, j+1)

        return dfs(0, 0)

解析