01.枚举算法知识

枚举算法知识 #

1. 枚举算法简介 #

枚举算法(Enumeration Algorithm):也称为穷举算法,指的是按照问题本身的性质,一一列举出该问题所有可能的解,并在逐一列举的过程中,将它们逐一与目标状态进行比较以得出满足问题要求的解。在列举的过程中,既不能遗漏也不能重复。

枚举算法是设计最简单、最基本的搜索算法,其核心思想是通过列举问题的所有状态,将它们逐一与目标状态进行比较,从而得到满足条件的解。

  • 枚举算法的优点
    • 容易编程实现,也容易调试。
    • 建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。
  • 枚举算法的缺点
    • 效率比较低,不适合求解规模较大的问题。

所以,枚举算法通常用于求解问题规模比较小的问题,或者作为求解问题的一个子算法出现,通过枚举一些信息并进行保存,而这些消息的有无对主算法效率的高低有着较大影响。

2. 枚举算法解题思路 #

采用枚举算法解题的一般思路如下:

  1. 确定枚举对象、枚举范围和判断条件,并判断条件设立的正确性。
  2. 一一枚举可能的情况,并验证是否是问题的解。
  3. 考虑提高枚举算法的效率。

我们可以从下面几个方面考虑提高算法的效率:

  1. 抓住问题状态的本质,尽可能缩小问题状态空间的大小。
  2. 加强约束条件,缩小枚举范围。
  3. 根据某些问题特有的性质,例如对称性等,避免对本质相同的状态重复求解。

3. 枚举算法的应用 #

3.1 两数之和 #

3.1.1 题目链接 #

3.1.2 题目大意 #

  • 描述:给定一个整数数组 nums 和一个整数目标值 target
  • 要求:在该数组中找出和为 target 的两个整数,并输出这两个整数的下标。

3.1.3 解题思路 #

这里说下枚举算法的解题思路。

使用两重循环枚举数组中每一个数 nums[i]nums[j]。判断所有的 nums[i] + nums[j] 是否等于 target

  • 如果出现 nums[i] + nums[j] == target,则说明数组中存在和为 target 的两个整数,将两个整数的下标 ij 输出即可。

利用两重循环进行枚举的时间复杂度为 $O(n^2)$。

3.1.4 代码 #

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if i != j and nums[i] + nums[j] == target:
                    return [i, j]
        return []

3.2 计数质数 #

3.2.1 题目链接 #

3.2.2 题目大意 #

描述:给定 一个非负整数 n

要求:统计小于 n 的质数数量。

3.2.3 解题思路 #

这里说下枚举算法的解题思路(注意:提交会超时,只是讲解一下枚举算法的思路)。

对于小于 n 的每一个数 x,我们可以枚举区间 [2, x - 1] 上的数是否是 x 的因数,即是否存在能被 x 整数的数。如果存在,则该数 x 不是质数。如果不存在,则该数 x 是质数。

这样我们就可以通过枚举 [2, n - 1] 上的所有数 x,并判断 x 是否为质数。

在遍历枚举的同时,我们维护一个用于统计小于 n 的质数数量的变量 cnt。如果符合要求,则将计数 cnt1。最终返回该数目作为答案。

考虑到如果 ix 的因数,则 $\frac{x}{i}$ 也必然是 x 的因数,则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 $[2, \sqrt x]$ 上。因此我们在检验 x 是否为质数时,只需要枚举 $[2, \sqrt x]$ 中的所有数即可。

利用枚举算法单次检查单个数的时间复杂度为 $O(\sqrt{n})$,检查 n 个数的整体时间复杂度为 $O(n \sqrt{n})$。

3.2.4 代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def isPrime(self, x):
        for i in range(2, int(pow(x, 0.5)) + 1):
            if x % i == 0:
                return False
        return True

    def countPrimes(self, n: int) -> int:
        cnt = 0
        for x in range(2, n):
            if self.isPrime(x):
                cnt += 1
        return cnt

3.3 统计平方和三元组的数目 #

3.3.1 题目链接 #

3.3.2 题目大意 #

描述:给你一个整数 n

要求:请你返回满足 $1 \le a, b, c \le n$ 的平方和三元组的数目。

说明

  • 平方和三元组:指的是满足 $a^2 + b^2 = c^2$ 的整数三元组 (a, b, c)

3.3.3 解题思路 #

枚举算法。

我们可以在 [1, n] 区间中枚举整数三元组 (a, b, c) 中的 ab。然后判断 $a^2 + b^2$ 是否小于等于 n,并且是完全平方数。

在遍历枚举的同时,我们维护一个用于统计平方和三元组数目的变量 cnt。如果符合要求,则将计数 cnt1。最终,我们返回该数目作为答案。

利用枚举算法统计平方和三元组数目的时间复杂度为 $O(n^2)$。

  • 注意:在计算中,为了防止浮点数造成的误差,并且两个相邻的完全平方正数之间的距离一定大于 1,所以我们可以用 $\sqrt{a^2 + b^2 + 1}$ 来代替 $\sqrt{a^2 + b^2}$。

3.3.4 代码 #

1
2
3
4
5
6
7
8
9
class Solution:
    def countTriples(self, n: int) -> int:
        cnt = 0
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                c = int(sqrt(a * a + b * b + 1))
                if c <= n and a * a + b * b == c * c:
                    cnt += 1
        return cnt

4. 二进制枚举子集 #

4.1 二进制枚举子集简介 #

先来介绍一下「子集」的概念。

  • 子集:如果集合 A 的任意一个元素都是集合 S 的元素,则称集合 A 是集合 S 的子集。可以记为 $A \in S$。

有时候我们会遇到这样的问题:给定一个集合 S,枚举其所有可能的子集。

枚举子集的方法有很多,这里介绍一种简单有效的枚举方法:「二进制枚举子集算法」。

对于一个元素个数为 n 的集合 S 来说,每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 1 来表示选取该元素,用数字 0 来表示不选取该元素。

那么我们就可以用一个长度为 n 的二进制数来表示集合 S 或者表示 S 的子集。其中二进制的每一位数都对应了集合中某一个元素的选取状态。对于集合中第 i 个元素(i0 开始编号)来说,二进制对应位置上的 1 代表该元素被选取,0 代表该元素未被选取。

举个例子来说明一下,比如长度为 5 的集合 S = {5, 4, 3, 2, 1},我们可以用一个长度为 5 的二进制数来表示该集合。

比如二进制数 11111 就表示选取集合的第 0 位、第 1 位、第 2 位、第 3 位、第 4 位元素,也就是集合 {5, 4, 3, 2, 1} ,即集合 S 本身。如下表所示:

集合 S 对应位置(下标) 4 3 2 1 0
二进制数对应位数 1 1 1 1 1
对应选取状态 选取 选取 选取 选取 选取

再比如二进制数 10101 就表示选取集合的第 0 位、第 2 位、第 5 位元素,也就是集合 {5, 3, 1}。如下表所示:

集合 S 对应位置(下标) 4 3 2 1 0
二进制数对应位数 1 0 1 0 1
对应选取状态 选取 未选取 选取 未选取 选取

再比如二进制数 01001 就表示选取集合的第 0 位、第 3 位元素,也就是集合 {5, 2}。如下标所示:

集合 S 对应位置(下标) 4 3 2 1 0
二进制数对应位数 0 1 0 0 1
对应选取状态 未选取 选取 未选取 未选取 选取

通过上面的例子我们可以得到启发:对于长度为 5 的集合 S 来说,我们只需要从 00000 ~ 11111 枚举一次(对应十进制为 $0 \sim 2^5 - 1$)即可得到长度为 5 的集合 S 的所有子集。

我们将上面的例子拓展到长度为 n 的集合 S。可以总结为:

  • 对于长度为 5 的集合 S 来说,只需要枚举 $0 \sim 2^n - 1$(共 $2^n$ 种情况),即可得到所有的子集。

4.2 二进制枚举子集代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def subsets(self, S):                   # 返回集合 S 的所有子集
        n = len(S)                          # n 为集合 S 的元素个数
        sub_sets = []                       # sub_sets 用于保存所有子集
        for i in range(1 << n):             # 枚举 0 ~ 2^n - 1
            sub_set = []                    # sub_set 用于保存当前子集
            for j in range(n):              # 枚举第 i 位元素
                if i >> j & 1:              # 如果第 i 为元素对应二进制位删改为 1,则表示选取该元素
                    sub_set.append(S[j])    # 将选取的元素加入到子集 sub_set 中
            sub_sets.append(sub_set)        # 将子集 sub_set 加入到所有子集数组 sub_sets 中
        return sub_sets                     # 返回所有子集

参考资料 #

  • 【书籍】算法竞赛入门经典:训练指南 - 刘汝佳,陈锋 著
  • 【书籍】ACM-ICPC 程序设计系列 - 算法设计与实现 - 陈宇 吴昊 主编
  • 【博文】 枚举排列和枚举子集 - CUC ACM-Wiki
本站总访问量  次  |  您是本站第  位访问者