面试算法高频04-分治与回溯

分治与回溯

分治和回溯算法，包括其概念、特性、代码模板，并结合具体题目进行讲解，旨在帮助学员理解和掌握这两种算法的应用。

1. 分治与回溯的概念
   • 分治（Divide & Conquer）：本质上基于递归，先将问题分解为多个子问题（Divide），分别求解子问题（Conquer），再将子问题的解合并（Merge）得到原问题的解 。以抛硬币问题为例帮助理解，通过不断将问题细分来简化求解过程。
   • 回溯（Backtracking）：采用试错思想，尝试分步解决问题。在分步过程中，若当前分步答案无法得到正确解答，则取消上一步或上几步计算，通过其他可能的分步解答继续尝试。它通常用简单递归实现，可能找到正确答案，也可能在尝试所有分步方法后宣告问题无解，最坏情况下时间复杂度为指数时间。
2. 分治算法
   • 代码模板：包含递归终止条件判断、数据准备、问题分解、子问题求解和结果合并等步骤。通过divide_conquer函数模板展示，在递归终止条件中判断问题是否为空，若为空则打印结果并返回；准备数据后将问题拆分为子问题，递归调用函数求解子问题，最后处理并生成最终结果 。
   • 理解要点：代码结构与递归相似，可看作在递归基础上增加了问题分解和结果合并步骤，有助于将复杂问题逐步简化解决。
3. 回溯算法
   • 代码示例 - 括号生成：在力扣22题括号生成中，通过_generate递归函数实现回溯。利用left和right分别记录左括号和右括号的使用数量，在递归过程中根据条件添加括号，当left和right都等于给定对数n时，将生成的括号组合加入结果列表 。
   • 算法理解：在解决问题时，通过不断尝试不同的分步选择，当发现当前选择无法得到有效答案时，回退到上一步重新选择，直至找到正确答案或确定问题无解。

练习题

括号生成

题目复述

题目要求是，给定一个整数 n ，n 代表着括号的对数。任务是编写一个函数，这个函数要能够生成所有可能的、并且是有效的括号组合。这里的有效是指在任意前缀中左括号的数量都不少于右括号的数量，且最终左、右括号的数量都等于 n 。举例来说，当 n = 3 时，生成的结果应该是像 ["((()))", "(()())", "(())()", "()(())", "()()()"] 这样的一系列有效的括号组合。

Python代码

from typing import Listclass Solution:def generateParenthesis(self, n: int) -> List[str]:result = []def _generate(left, right, s):# terminatorif left == n and right == n:result.append(s)return# drill downif left < n:_generate(left + 1, right, s + "(")if left > right:_generate(left, right + 1, s + ")")_generate(0, 0, "")return result

代码解析

1. 整体结构：定义了 Solution 类，其中 generateParenthesis 方法是对外提供功能的接口，接收整数 n 作为参数，返回值类型是字符串列表，即所有有效的括号组合。在 generateParenthesis 方法内部，又定义了一个局部函数 _generate ，它采用递归的方式来逐步生成括号组合。同时初始化了一个空列表 result ，用于存储最终有效的括号组合。
2. 递归终止条件（terminator）：在 _generate 函数中，通过判断 if left == n and right == n: 来确定是否达到递归终止条件。当左括号的数量 left 和右括号的数量 right 都等于给定的 n 时，说明已经成功构建出了一个完整且有效的括号组合，此时将这个组合字符串 s 添加到结果列表 result 中，然后通过 return 语句结束当前这一支递归调用。
3. 处理当前逻辑并递归深入（drill down）
   • 添加左括号：使用条件 if left < n: 进行判断，只要左括号的数量 left 还小于给定的 n ，就表示还可以继续添加左括号。此时通过递归调用 _generate(left + 1, right, s + "(") ，将左括号数量增加1 ，并把左括号字符 ( 添加到当前正在构建的括号组合字符串 s 后面，继续深入递归以进一步构建括号组合。
   • 添加右括号：利用条件 if left > right: 进行判断，当左括号的数量 left 大于右括号的数量 right 时，意味着可以添加右括号（这是为了保证在构建括号组合的任意时刻，左括号的数量都不少于右括号的数量，从而保证组合的有效性 ）。通过递归调用 _generate(left, right + 1, s + ")") ，将右括号数量增加1 ，并把右括号字符 ) 添加到当前的括号组合字符串 s 后面，继续递归构建括号组合。
4. 返回结果：在 generateParenthesis 方法中，调用 _generate(0, 0, "") 开始递归构建括号组合的过程，当递归结束后，直接返回存储着所有有效括号组合的 result 列表。

复杂度分析

• 时间复杂度：该算法的时间复杂度大致为 $O(4^n/\sqrt{n})$ 。从解空间角度来看，对于 n 对括号，其所有可能的组合数量规模大致符合这样的数量级。虽然在递归过程中通过条件判断（左括号数量和右括号数量的约束 ）减少了一些无效分支的计算，但整体数量级仍然是这个范围。
• 空间复杂度：递归调用栈的深度最大为 2n （因为最多会有 n 个左括号和 n 个右括号依次入栈 ），所以仅考虑递归栈的空间占用时，空间复杂度为 $O(n)$ 。再考虑到结果列表 result ，在最坏情况下它存储的有效括号组合数量为卡特兰数 $O(C_{2n}^n)$ ，每个组合的长度为 2n ，综合起来整个算法的空间复杂度为 $O(4^n/\sqrt{n})$ 。

题目描述

实现 pow(x, n) ，也就是计算 x 的 n 次幂函数（即 $x^n$ ）。题目给定了相关约束条件：-100.0 < x < 100.0 ，n 是 32 位有符号整数，数值范围在 [−2^31, 2^31 − 1] 。同时给出了示例：

• 示例 1 中，输入 x = 2.00000, n = 10 ，输出 1024.00000 。
• 示例 2 里，输入 x = 2.10000, n = 3 ，输出 9.26100 。
• 示例 3 时，输入 x = 2.00000, n = -2 ，输出 0.25000 ，因为 2^(-2) = 1/2^2 = 1/4 = 0.25 。

Python代码和解析

暴力解法

class Solution:def myPow(self, x: float, n: int) -> float:if n == 0:return 1elif n < 0:x = 1 / xn = -nresult = 1for _ in range(n):result *= xreturn result

解析：先处理特殊情况，当 n 为 0 ，任何数的 0 次幂是 1 ，直接返回 1 。若 n 为负，将 x 取倒数，n 变为正。然后通过 for 循环，让 result 连乘 n 次 x 得到结果。时间复杂度为 $O(n)$ ，因为要进行 n 次乘法；空间复杂度 $O(1)$ ，只用到几个固定变量。

分治算法

class Solution:def myPow(self, x: float, n: int) -> float:if n == 0:return 1elif n < 0:x = 1 / xn = -nreturn self.helper(x, n)def helper(self, x, n):if n == 0:return 1half = self.helper(x, n // 2)if n % 2 == 0:return half * halfelse:return half * half * x

解析：同样先处理 n 为 0 和负数情况。helper 递归函数用分治思想，把求 x 的 n 次幂问题分解成求 x 的 n//2 次幂问题。若 n 是偶数，x^n = (x^(n//2)) * (x^(n//2)) ；若 n 是奇数，x^n = (x^(n//2)) * (x^(n//2)) * x 。时间复杂度 $O(logn)$ ，每次递归问题规模减半；空间复杂度 $O(logn)$ ，递归调用栈深度最大为 $O(logn)$ 。

分治 + 迭代

class Solution:def myPow(self, x: float, n: int) -> float:if n < 0:x = 1 / xn = -nresult = 1current_product = xwhile n > 0:if n % 2 == 1:result *= current_productcurrent_product *= current_productn = n // 2return result

解析：先处理 n 为负的情况。初始化 result 为 1 ，current_product 为 x 。循环中，通过 n % 2 检查 n 的二进制位，为 1 就把 current_product 乘到 result 中，接着 current_product 平方，n 右移一位（除以 2 ），直到 n 为 0 。时间复杂度 $O(logn)$ ，循环次数是 n 二进制表示的位数；空间复杂度 $O(1)$ ，只用了几个固定变量。
在二进制幂次计算里，一个整数的幂次计算可以转化为对其二进制表示的处理。以计算$x^n$为例，将$n$用二进制表示后，每一位都对应着不同的$x$的幂次。

• 例如计算$x^{13}$，$13$的二进制是$1101$ ，$x^{13}=x^{8+4+1}=x^8\times x^4\times x^1$ 。从右往左看二进制位，第一位是$1$，代表$x^1$；第二位是$0$，代表没有$x^2$ ；第三位是$1$，代表$x^4$ ；第四位是$1$，代表$x^8$ 。
• 回到代码中，while n > 0:循环每次处理$n$的一个二进制位。if n % 2 == 1:判断当前处理的二进制位是否为$1$，如果是，说明这个二进制位对应的$x$的幂次需要乘到结果里。比如在计算$x^{13}$时，当处理到第一位（从右往左）和第三位、第四位时，由于这些位是$1$，所以要把对应的$x$的幂次（即当前的current_product）乘到result中。而current_product在每次循环中会不断平方，依次对应$x^1$ 、$x^2$ 、$x^4$ 、$x^8$等幂次。在计算$x^{13}$时，第一次循环current_product是$x$ ，对应$x^1$ ，因为第一位是$1$，所以result乘上$x$ ；第二次循环current_product变为$x^2$ ，但第二位是$0$，不乘；第三次循环current_product变为$x^4$ ，第三位是$1$，result乘上$x^4$ ；第四次循环current_product变为$x^8$ ，第四位是$1$，result乘上$x^8$ 。最终result的值就是$x^{13}$ 。 所以在二进制幂次计算中，奇数幂次（对应二进制位为$1$的情况）需要额外乘上当前的底数，以此完成幂次的计算。

题目描述

给定一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集，输出顺序可以任意。

最优解思路（位运算解法）

1. 对于一个含有 n 个元素的集合，它的子集个数为 $2^n$ 个 。可以用二进制数来表示每个子集，从 0 到 $2^n-1$ 这 $2^n$ 个二进制数，每一位对应集合中的一个元素，若该位为 1 ，表示对应元素在子集中；若为 0 ，表示对应元素不在子集中。
2. 遍历从 0 到 $2^n-1$ 的所有整数，对于每个整数，将其转换为二进制形式，根据二进制位的情况构建对应的子集。

代码实现（Python）

class Solution:def subsets(self, nums):n = len(nums)result = []for i in range(2 ** n):subset = []for j in range(n):if (i >> j) & 1:subset.append(nums[j])result.append(subset)return result

代码解析

1. 确定子集数量范围：
   • n = len(nums) 获取数组 nums 的长度。总共有 $2^n$ 个子集，所以通过 for i in range(2 ** n) 遍历从 0 到 $2^n-1$ 的所有整数。
2. 构建每个子集：
   • 对于每个整数 i ，内部通过 for j in range(n) 遍历 nums 数组的每个元素位置。(i >> j) & 1 用于判断 i 的二进制表示中第 j 位是否为 1 。i >> j 是将 i 的二进制表示右移 j 位，然后 & 1 是取最低位，如果结果为 1 ，说明第 j 位是 1 ，此时将 nums[j] 添加到当前子集 subset 中。
3. 收集结果：
   • 构建好一个子集 subset 后，将其添加到结果列表 result 中，最后返回 result 。

复杂度分析

• 时间复杂度：外层循环执行 $2^n$ 次，内层循环对于每个外层循环执行 n 次，整体时间复杂度为 $O(n\times 2^n)$ ，这是生成所有子集问题的理论最小时间复杂度。
• 空间复杂度：除输入数组外，额外空间主要用于存储结果集。最坏情况下有 $2^n$ 个子集，假设每个子集平均长度为 n ，空间复杂度为 $O(n\times 2^n)$ 。

前面我们提到一个含有(n)个元素的集合，其子集个数为(2^n)个，这可以通过二项式展开来理解，下面结合代码详细阐述。

二项式定理回顾

二项式定理的表达式为((a + b)^n=\sum_{k = 0}^{n}C_{n}k a^{n - k}b^{{k})，其中(C_{n}}k=\frac{n!}{k!(n - k)!})，它表示从(n)个不同元素中取出(k)个元素的组合数 。当(a = b = 1)时，((1 + 1)^n=\sum_{k = 0}^{n}C_{n}k\times1^{n - k}\times1^{k}=\sum_{k = 0}^{n}C_{n}k)，也就是(2^n = C_{n}^0 + C_{n}^1+C_{n}2+\cdots + C_{n}^n)。

代码逻辑与二项式展开的关联

以下是之前的代码：

class Solution:def subsets(self, nums):n = len(nums)result = []for i in range(2 ** n):subset = []for j in range(n):if (i >> j) & 1:subset.append(nums[j])result.append(subset)return result

1. 二项式展开各项含义

• (C_{n}^k)表示从(n)个元素中选取(k)个元素的组合方式的数量。在集合的子集中，这就对应着含有(k)个元素的子集的个数。
• 比如，对于一个有(n = 3)个元素的集合({a,b,c})：
  • (C_{3}^0)表示从(3)个元素中选(0)个元素的组合数，其值为(1)，对应的子集就是空集(\varnothing)。
  • (C_{3}^{1)表示从(3)个元素中选(1)个元素的组合数，(C_{3}}1=\frac{3!}{1!(3 - 1)!}=\frac{3!}{1!2!}=3)，对应的子集为({a})、({b})、({c})。
  • (C_{3}^{2)表示从(3)个元素中选(2)个元素的组合数，(C_{3}}2=\frac{3!}{2!(3 - 2)!}=\frac{3!}{2!1!}=3)，对应的子集为({a,b})、({a,c})、({b,c})。
  • (C_{3}^3)表示从(3)个元素中选(3)个元素的组合数，其值为(1)，对应的子集就是原集合({a,b,c})。

2. 代码中循环与二项式展开的对应关系

• 外层循环：for i in range(2 ** n)，这里(2^n)就是二项式展开((1 + 1)^{n)的结果。从(0)到(2}n-1)的每一个整数(i)都对应着集合的一个子集。这是因为每一个整数(i)的二进制表示可以用来确定集合中的哪些元素被选入子集中。
• 内层循环：for j in range(n)用于检查整数(i)的二进制表示的每一位。(i >> j) & 1 这个表达式用于判断(i)的第(j)位是否为(1)，如果为(1)，则将nums[j]添加到子集中。从二项式展开的角度看，当我们遍历所有的(i)时，实际上是在遍历所有可能的元素选取组合，也就是在遍历二项式展开中的每一项。

举例说明

假设nums = ['a', 'b', 'c']，(n = 3)，(2^n=8)。

• 当(i = 0)（二进制(000)）时，内层循环中(i >> j) & 1对于所有(j)都为(0)，得到子集(\varnothing)，对应二项式展开中的(C_{3}^0)这一项。
• 当(i = 1)（二进制(001)）时，(i >> 0) & 1 = 1，将nums[0]（即a）加入子集，得到子集({a})；当(i = 2)（二进制(010)）时，得到子集({b})；当(i = 4)（二进制(100)）时，得到子集({c})，这三个子集对应二项式展开中的(C_{3}^1)这一项。
• 当(i = 3)（二进制(011)）时，得到子集({a,b})；当(i = 5)（二进制(101)）时，得到子集({a,c})；当(i = 6)（二进制(110)）时，得到子集({b,c})，这三个子集对应二项式展开中的(C_{3}^2)这一项。
• 当(i = 7)（二进制(111)）时，得到子集({a,b,c})，对应二项式展开中的(C_{3}^3)这一项。

综上所述，代码通过遍历(0)到(2^n - 1)的所有整数，利用二进制位运算来确定元素的选取，从而得到集合的所有子集，这与二项式展开所表示的从(n)个元素中选取不同个数元素的组合情况是一一对应的，体现了集合子集个数与二项式展开结果(2^n)之间的紧密联系。

题目：多数元素（Majority Element）

链接：https://leetcode-cn.com/problems/majority-element/description/

题目描述

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n / 2⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解法一：哈希表法

1. 思路
   使用哈希表来记录每个元素出现的次数。遍历数组，对于每个元素，如果它已经在哈希表中，就将其对应的值（出现次数）加1；如果不在，就将其加入哈希表，出现次数初始化为1 。最后遍历哈希表，找出出现次数大于⌊n / 2⌋的元素。
2. Python代码实现

class Solution:def majorityElement(self, nums):num_count = {}n = len(nums)for num in nums:num_count[num] = num_count.get(num, 0) + 1if num_count[num] > n // 2:return num

3. 代码解释
   • 首先创建一个空的字典num_count用于存储元素及其出现次数，获取数组nums的长度n。
   • 然后遍历数组nums，对于每个元素num，使用num_count.get(num, 0)获取num在字典中的出现次数（如果不存在则默认为0），并将其加1。
   • 每次更新完出现次数后，检查当前元素的出现次数是否大于n // 2，如果大于则直接返回该元素。
4. 时间复杂度：$O(n)$，其中n是数组nums的长度。遍历数组一次，哈希表的操作平均时间复杂度为常数，所以整体时间复杂度为$O(n)$。
5. 空间复杂度：$O(n)$，在最坏情况下，数组中的所有元素都不同，此时哈希表需要存储n个键值对，所以空间复杂度为$O(n)$。

解法二：排序法

1. 思路
   先对数组进行排序，由于多数元素出现的次数大于⌊n / 2⌋，那么排序后数组中间位置（索引为n // 2）的元素必然是多数元素。
2. Python代码实现

class Solution:def majorityElement(self, nums):nums.sort()return nums[len(nums) // 2]

3. 代码解释
   • 使用nums.sort()对数组nums进行排序，Python的内置排序函数平均时间复杂度为$O(nlogn)$。
   • 排序后直接返回数组中间位置（索引为len(nums) // 2）的元素，该元素就是多数元素。
4. 时间复杂度：$O(nlogn)$，主要时间消耗在排序操作上，常见排序算法平均时间复杂度为$O(nlogn)$。
5. 空间复杂度：如果使用的是原地排序算法（如Python的list.sort ），空间复杂度为$O(1)$；如果使用的是需要额外空间的排序算法（如归并排序），空间复杂度为$O(n)$ 。

解法三：摩尔投票法（最优解）

1. 思路
   摩尔投票法的核心思想是通过两两抵消不同的元素，最后剩下的就是多数元素。维护一个候选元素candidate和它的计数值count。遍历数组，当count为0时，将当前元素设为candidate；如果当前元素与candidate相同，count加1，否则count减1 。遍历结束后，candidate即为多数元素。
2. Python代码实现

class Solution:def majorityElement(self, nums):candidate = Nonecount = 0for num in nums:if count == 0:candidate = numcount += (1 if num == candidate else -1)return candidate

3. 代码解释
   • 初始化候选元素candidate为None，计数值count为0。
   • 遍历数组nums，当count为0时，将当前元素num设为candidate。然后根据当前元素num是否与candidate相同，对count进行加1或减1操作。
   • 遍历结束后，candidate就是多数元素，直接返回。
4. 时间复杂度：$O(n)$，只需要遍历数组一次，时间复杂度为$O(n)$。
5. 空间复杂度：$O(1)$，只使用了常数级别的额外空间。