[数据结构与算法]2021-10-06 剑指offer2：01~12题目+思路+多种题解

写在前面

本文是采用python为编程语言，作者自行练习使用，题目列表为：剑指 Offer（第 2 版），未使用实体书，难度未标注的均为“简单”，我也不是很清楚为什么有几个编号没有提供。“《剑指 Offer（第 2 版）》通行全球的程序员经典面试秘籍。剖析典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。”，本文中的思路来源于每道题目中的题解部分，争取提供全面，优化后的题解，其中所有代码已通过题目检验。

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

题目

思路

这道题在原书上绝对不是简单级别啊！
它考察的是程序员的沟通能力，先问面试官要时间/空间需求！！！
只是时间优先就用字典，
还有空间要求，就用指针+原地排序数组，
如果面试官要求空间O(1)并且不能修改原数组，还得写成二分法！！！

题解

• 原地排序：充分利用题干信息，索引i对应的数字为

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i:
                i += 1
                continue
            if nums[nums[i]] == nums[i]:
                 return nums[i]
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return -1

• 二分法：数组无序，但根据题目，我们可以假装存在一个“排好序”的数组且知道总数目，来进行二分法。首先找到二分法的“分”的边界，即如果两个数字重复，则 min ~ 中位数/中位数 ~ max 这两个区间，一定有一个比较长，而比较长的那个就是重复数字存在的区间，不断缩小空间，直至找到该数。二分法的关键是排序关系（即可比较且每一半比较结果相同，比如都大/小）+舍弃没有必要的部分。

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        n = len(nums);
        left, right = 1, n-1;
        while left<right:
        	# 如果没有重复数字的中位数
            mid = left+(right-left)/2
            cnt = 0
            # 有重复数字下，统计比中位数小的数字个数
            for i in range(0,n):
            	if nums[i]<=mid:
            		cnt++
            # 从1到mid最多有mid个元素，超过它说明有重复元素，且重复元素处于0~mid之间
            if cnt>mid：
                right = mid
            else：
                left = mid+1
        return left

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

题目

思路

比较清晰的二分法，即站在右上角看，这个矩阵其实就像是一个Binary Search Tree。另外，注意边界条件。

题解

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        height,width=len(matrix),len(matrix[0])
        i,j=0,width-1
        while i<=height-1 and j>=0:
            print(i,j)
            num_p=matrix[i][j]
            if num_p<target:
                i+=1
            elif num_p>target:
                j-=1
            # 相等的情况出现的概率很小，放在最后
            else : return True
        return False

剑指 Offer 05. 替换空格

题目

思路

• 遍历添加：在 Python 中，字符串是不可变的，即无法直接修改字符串的某一位字符，需要新建一个字符串实现，所以无法避免额外的空间，可以直接append()
• 原地修改：在C++中的std::string则是可以原地修改的，而顺次修改因为长度变长会覆盖后面的字符，所以我们采取自后向前的方法，直到重复。

题解

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for c in s:
            if c == ' ': res.append("%20")
            else: res.append(c)
        return ''.join(res)

• 原地修改：这个代码来源于Leetcode用户@Krahets

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0, len = s.size();
        // 统计空格数量
        for (char c : s) {
            if (c == ' ') count++;
        }
        // 修改 s 长度
        s.resize(len + 2 * count);
        // 倒序遍历修改
        for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
            if (s[i] != ' ')
                s[j] = s[i];
            else {
                s[j - 2] = '%';
                s[j - 1] = '2';
                s[j] = '0';
                j -= 2;
            }
        }
        return s;
    }
};

作者：jyd
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/solution/mian-shi-ti-05-ti-huan-kong-ge-ji-jian-qing-xi-tu-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

题目

思路

• 先进后出即栈，先按顺序存进去，再倒出栈即可
• 递归：递归本质也是一个栈。先一步步走到栈底，再用“动态规划”的方法返回。

题解

• 栈

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

• 递归

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if not head:
            return []
        else:
            return self.reversePrint(head.next) + [head.val]

剑指 Offer 07. 重建二叉树（中等）

题目

思路

• 递归：按照如下思路划分两个序列，然后1.存储根节点 2.遍历左右子树 3.合并
  
  • 递归改进1：使用hash表存储索引，增快查找速度（index()的时间复杂度为O(n)）
  • 递归改进2：因为题目给出的参数是list，如果不断递归需要不断复制并开辟新的子list，改为在同一个列表上取索引递归
• 迭代：没看懂，贴个官方答案：重建二叉树

题解

• 递归原版：

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        cnt = len(preorder)
        if cnt==0:
            return None
        root = TreeNode(preorder[0])
        index = inorder.index(root.val)
        
        left_p, left_i = preorder[1:1+index], inorder[0:index]
        right_p, right_i = preorder[1+index:], inorder[index+1:]

        root.left = self.buildTree(left_p, left_i)
        root.right = self.buildTree(right_p, right_i)
        return root

• 递归改进：

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def buildbyindex(root, left, right):
            if left > right: 
            	return None
            rootnode = TreeNode(preorder[root]) 
            index = hashdic[preorder[root]]
            # left和right分别是在inorder中的索引，因为方便取                         
            rootnode.left = buildbyindex(root + 1, left, index - 1) 
            # 右子树的根节点索引在preoder中的位置：根节点+左子树长度+1
            rootnode.right = buildbyindex(index - left + root + 1, index + 1, right) 
            return rootnode 

        hashdic = {}
        cnt = len(inorder)
        for index in range(cnt):
            hashdic[inorder[index]] = index
        return buildbyindex(0, 0, cnt - 1)

• 迭代：

# 二刷再来补充

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

题目

思路

• 最先想到的肯定是一个栈用于进，另一个用于出。但是出完之后，可以不用再全部倒回原栈，因为队列==把两个栈栈底拼接起来。

题解

class CQueue:
    def __init__(self):
        self.ins, self.out = [], []

    def appendTail(self, value: int) -> None:
        self.ins.append(value)

    def deleteHead(self) -> int:
        if self.out:
            return self.out.pop()
        if not self.ins:
            return -1
        while self.ins:
            self.out.append(self.ins.pop())
        return self.out.pop()

剑指 Offer 10- I. 斐波那契数列

题目

思路

• 递归：递归法，很典型，逐步拆分子问题即可 -> 记忆化递归：建立一个表记录用到的f(n)
• 动态规划：自底向上求 -> 只与前两个数有关，没有必要浪费空间记录所有的n以及之前的，只需要两个变量
• 数学方法：某种固定公式的递归可以直接计算出表达式，如图所示：
  

题解

• 动态规划：本来是需要三个变量的，但是写出来会发现，可以直接通过两个变量计算来完成递归（当然选择python中的直接同时赋值更新也是可以的，second, first = first, second+first）

class Solution:
    def fib(self, n: int) -> int:
        MOD =10**9+7
        if n==0:
            return 0
        elif n==1:
            return 1
        first, result = 0, 1
     
        for num in range(2,n+1):
            result=first+result
            first=result-first
        return result%MOD

• 矩阵求法（这个代码并未全部通过！！！实在不知道问题出现在哪了）

import numpy as np
class Solution:
    def fib(self, n: int) -> int:
        # 这里的MOD如果使用1e9+7需要浮点数的转换
        MOD =10**9+7
        weights=np.array([[1,1],[1,0]])
        start =np.array([1,0])
        result = np.linalg.matrix_power(weights,n)@start
        if n<2:
            return n
        return result.tolist()[1]%MOD

剑指 Offer 10- II. 青蛙跳台阶问题

题目

思路

• 最后一步共两种情况：跳一下or跳两下，分别对应f(n-1)和f(n-2)种情况，所以该题实际上等价于上面的“10- I. 斐波那契数列”，只不过起始条件不同

题解

class Solution:
    def numWays(self, n: int) -> int:
    	MOD =10**9+7
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a % MOD

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

题目

思路

• 这个题。。。第一反应就是return min(numbers)嘛。。。然后看评论发现目的是要优化到O(logn)的复杂度，而且考察点就是这个排序的过程。再一看题目，排好序的，顺理成章得出了二分法。
• 下面就是分析二分法的舍弃规则：寻找最小的，肯定是舍弃大的部分，那这个部分怎么界定呢？可以将旋转后的数组视作“左排序 右排序”数组，从而舍弃大的部分。涉及到具体细节，取中间的数和两侧的数字比较，但因为我们需要取“较小的”，即倾向于向前取，考虑中间的数字比较左侧和右侧两种情况：发现比较左侧数字，会存在错误现象，这是因为边界条件框不进去。

题解

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

剑指 Offer 12. 矩阵中的路径（中等）

题目

思路

• 搜索某条路径的问题 -> DFS。进行算法的改进就是根据条件添加剪枝啦。而基础的DFS有两种实现方式：

  • 递归：整体流程是“访问首元素 - 对当前元素进行判定，剪枝以及和题目要求结合的位置（这个当前的含义是和当前递归参数有关的信息参与运算）- 利用dfs传递临近元素（改变参数）”，在这个过程中利用visited辅助剪枝和防止重复

  void DFS(Graph G,int v){ 
  	Visit[v]  
  	visited[v]=true
  	w = FirstAdj(G,v)				# 访问v的第一个邻接顶点
  	while(w!=0){   
      	if(!visited[w]{
          	DFS(G,w)				# 递归访问w的第一个...直到没有路为止递归返回到上一个这层位置
      	}
      	w = NextAdj(G,v,w)			# 访问v的第二个邻接顶点
  	}
  

  • 非递归：借助栈实现，整体流程是 “首元素入栈 - while循环（弹栈，弹出的是上一步加入的元素 - 判定，剪枝以及和题目要求结合的位置 - 入周围的栈，有时候判定可以提前在这一步进行）- 返回结果”，在这个过程中利用visited辅助剪枝和防止重复
    

  def DFS(graph,s):  				# s是起始点
      stack=[]  					# 数组可以动态的添加或者删除 append、pop
      stack.append(s)
      seen=[]  					# 来保存放过的节点
      seen.append(s)
      while(len(stack)>0):
          vertex=stack.pop()  	# 弹出当前元素，即上一步加入的候选项中的任意一个
          nodes=graph[vertex]
          for node in nodes:		# 候选项加入栈
              if node not in seen:
                  stack.append(node)	# 确保最远的在最上方
                  seen.append(node)
          print(vertex)			# 注意：弹出的元素才是真正使用的元素
  

题解

• 递归：这个代码来源于Leetcode用户@Krahets

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: 
            	return False
            if k == len(word) - 1: 
            	return True
            	
           	# 剪枝操作：以此替代已经用过的元素列表记载
            board[i][j] = ''
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = word[k]
            return res
            
		# 因为每一个元素都可能作为开头（根），所以需要遍历所有元素，分别判断以之为首能否构成word，再开始dfs
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                	return True
        return False
        
作者：jyd
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• 借助栈：递归和栈其实可以互相转化。注意这个题的特殊之处在于：需要知道当前是否回退，以确定和word中哪个不同的_index对应的字母比较，所以需要记录栈中的哪些是正常pop，哪些是回退，以及已经使用了多少节点

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n = len(board)
        m = len(board[0])
        w = len(word) 
		# 因为每一个元素都可能作为开头（根），所以需要遍历所有元素，分别判断以之为首能否构成word，再开始dfs
        for i_ in range(n):
            for j_ in range(m):
                stack = [(i_, j_, 0)]
                index = 0
                use_points = list()

                while stack:
                    i, j, ind = stack.pop()
                    
					# 在该种use_point的情况下，新加入到stack中的上下左右都无法满足第_index个字符
					# 以至于倒出了第_index-1个字符，即回退一步，进行新的dfs路径
                    if use_points and ind != index:
                        use_points.pop()
                        index -= 1
                        stack.append((i, j, ind))
                        continue
                        
					# 剪枝，走不过去不走了，而不是等到全部完成
                    if board[i][j] != word[index]:
                        continue
					else：
                    	use_points.append((i, j))
                    	index += 1

                    if index == w:
                        return True

                    # 上方元素
                    if i > 0 and (i - 1, j) not in use_points:
                        stack.append((i - 1, j, index))
                    # 下方元素
                    if i < n - 1 and (i + 1, j) not in use_points:
                        stack.append((i + 1, j, index))
                    # 左方元素
                    if j > 0 and (i, j - 1) not in use_points:
                        stack.append((i, j - 1, index))
                    # 右方元素
                    if j < m - 1 and (i, j + 1) not in use_points:
                        stack.append((i, j + 1, index))
        return False