twitter,facebook,ins,youtube视频下载
磨针音视频转文字
磨针免费pdf转word
磨针微信定时发文件和消息
磨针c盘清理，任何场景都能释放几十G的空间
1. 枚举算法简介
枚举算法（Enumeration Algorithm）：也称为穷举算法，指的是按照问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，将它们逐一与目标状态进行比较以得出满足问题要求的解。在列举的过程中，既不能遗漏也不能重复。
枚举算法的核心思想是：通过列举问题的所有状态，将它们逐一与目标状态进行比较，从而得到满足条件的解。
由于枚举算法要通过列举问题的所有状态来得到满足条件的解，因此，在问题规模变大时，其效率一般是比较低的。但是枚举算法也有自己特有的优点：
- 多数情况下容易编程实现，也容易调试。
- 建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。
所以，枚举算法通常用于求解问题规模比较小的问题，或者作为求解问题的一个子算法出现，通过枚举一些信息并进行保存，而这些消息的有无对主算法效率的高低有着较大影响。
2. 枚举算法的解题思路
2.1 枚举算法的解题思路
枚举算法是设计最简单、最基本的搜索算法。是我们在遇到问题时，最应该优先考虑的算法。
因为其实现足够简单，所以在遇到问题时，我们往往可以先通过枚举算法尝试解决问题，然后在此基础上，再去考虑其他优化方法和解题思路。
采用枚举算法解题的一般思路如下：
- 确定枚举对象、枚举范围和判断条件，并判断条件设立的正确性。
- 一一枚举可能的情况，并验证是否是问题的解。
- 考虑提高枚举算法的效率。
我们可以从下面几个方面考虑提高算法的效率：
- 抓住问题状态的本质，尽可能缩小问题状态空间的大小。
- 加强约束条件，缩小枚举范围。
- 根据某些问题特有的性质，例如对称性等，避免对本质相同的状态重复求解。
2.2 枚举算法的简单应用
下面举个著名的例子：「百钱买百鸡问题」。这个问题是我国古代数学家张丘在「算经」一书中提出的。该问题叙述如下：
百钱买百鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则鸡翁、鸡母、鸡雏各几何？
翻译一下，意思就是：公鸡一只五块钱，母鸡一只三块钱，小鸡三只一块钱。现在我们用 100 块钱买了 100 只鸡，问公鸡、母鸡、小鸡各买了多少只？
下面我们根据算法的一般思路来解决一下这道题。
-
确定枚举对象、枚举范围和判断条件，并判断条件设立的正确性。
- 确定枚举对象：枚举对象为公鸡、母鸡、小鸡的只数，那么我们可以用变量 𝑥、y、z 分别来代表公鸡、母鸡、小鸡的只数。
- 确定枚举范围：因为总共买了 100 只鸡，所以 0≤𝑥,𝑦,𝑧≤100，则 𝑥、y、z 的枚举范围为 [0,100]。
- 确定判断条件：根据题意，我们可以列出两个方程式：5x + 3y + z/3= 100，x + y + z = 100。在枚举 𝑥、y、z 的过程中，我们可以根据这两个方程式来判断是否当前状态是否满足题意。
-
一一枚举可能的情况，并验证是否是问题的解。
-
根据枚举对象、枚举范围和判断条件，我们可以顺利写出对应的代码。
class Solution: def buyChicken(self): for x in range(101): for y in range(101): for z in range(101): if z % 3 == 0 and 5 * x + 3 * y + z // 3 == 100 and x + y + z == 100: print("公鸡 %s 只，母鸡 %s 只，小鸡 %s 只" % (x, y, z))
-
-
考虑提高枚举算法的效率。
- 在上面的代码中，我们枚举了 𝑥、$y$、$z$，但其实根据方程式 𝑥+𝑦+𝑧=100，得知：$z$ 可以通过 𝑧=100−𝑥−𝑦 而得到，这样我们就不用再枚举 𝑧 了。
- 在上面的代码中，对 𝑥、$y$ 的枚举范围是 [0,100]，但其实如果所有钱用来买公鸡，最多只能买 20 只，同理，全用来买母鸡，最多只能买 33 只。所以对 𝑥 的枚举范围可改为 [0,20]，$y$ 的枚举范围可改为 [0,33]。
class Solution: def buyChicken(self): for x in range(21): for y in range(34): z = 100 - x - y if z % 3 == 0 and 5 * x + 3 * y + z // 3 == 100: print("公鸡 %s 只，母鸡 %s 只，小鸡 %s 只" % (x, y, z))
3. 枚举算法的应用
3.1 两数之和
3.1.1 题目链接
3.1.2 题目大意
描述：给定一个整数数组 𝑛𝑢𝑚𝑠 和一个整数目标值 𝑡𝑎𝑟𝑔𝑒𝑡。
要求：在该数组中找出和为 𝑡𝑎𝑟𝑔𝑒𝑡 的两个整数，并输出这两个整数的下标。可以按任意顺序返回答案。
说明：
- 2≤𝑛𝑢𝑚𝑠.𝑙𝑒𝑛𝑔𝑡ℎ≤104。
- −109≤𝑛𝑢𝑚𝑠[𝑖]≤109。
- −109≤𝑡𝑎𝑟𝑔𝑒𝑡≤109。
- 只会存在一个有效答案。
示例：
- 示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
- 示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
3.1.3 解题思路
这里说下枚举算法的解题思路。
思路 1：枚举算法
- 使用两重循环枚举数组中每一个数 𝑛𝑢𝑚𝑠[𝑖]、$nums[j]$，判断所有的 𝑛𝑢𝑚𝑠[𝑖]+𝑛𝑢𝑚𝑠[𝑗] 是否等于 𝑡𝑎𝑟𝑔𝑒𝑡。
- 如果出现 𝑛𝑢𝑚𝑠[𝑖]+𝑛𝑢𝑚𝑠[𝑗]==𝑡𝑎𝑟𝑔𝑒𝑡，则说明数组中存在和为 𝑡𝑎𝑟𝑔𝑒𝑡 的两个整数，将两个整数的下标 𝑖、$j$ 输出即可。
思路 1：代码
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 []
思路 1：复杂度分析
- 时间复杂度：$O(n^2)$，其中 𝑛 为数组 𝑛𝑢𝑚𝑠 的元素数量。
- 空间复杂度：$O(1)$。
3.2 计数质数
3.2.1 题目链接
3.2.2 题目大意
描述：给定 一个非负整数 𝑛。
要求：统计小于 𝑛 的质数数量。
说明：
- 0≤𝑛≤5×106。
示例：
- 示例 1：
输入 n = 10 输出 4 解释 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7。
- 示例 2：
输入：n = 1 输出：0
3.2.3 解题思路
这里说下枚举算法的解题思路（注意：提交会超时，只是讲解一下枚举算法的思路）。
思路 1：枚举算法（超时）
对于小于 𝑛 的每一个数 𝑥，我们可以枚举区间 [2,𝑥−1] 上的数是否是 𝑥 的因数，即是否存在能被 𝑥 整除的数。如果存在，则该数 𝑥 不是质数。如果不存在，则该数 𝑥 是质数。
这样我们就可以通过枚举 [2,𝑛−1] 上的所有数 𝑥，并判断 𝑥 是否为质数。
在遍历枚举的同时，我们维护一个用于统计小于 𝑛 的质数数量的变量 𝑐𝑛𝑡。如果符合要求，则将计数 𝑐𝑛𝑡 加 1。最终返回该数目作为答案。
考虑到如果 𝑖 是 𝑥 的因数，则 𝑥𝑖 也必然是 𝑥 的因数，则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 [2,𝑥] 上。因此我们在检验 𝑥 是否为质数时，只需要枚举 [2,𝑥] 中的所有数即可。
利用枚举算法单次检查单个数的时间复杂度为 𝑂(𝑛)，检查 𝑛 个数的整体时间复杂度为 𝑂(𝑛𝑛)。
思路 1：代码
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
思路 1：复杂度分析
- 时间复杂度：$O(n \times \sqrt{n})$。
- 空间复杂度：$O(1)$。
3.3 统计平方和三元组的数目
3.3.1 题目链接
3.3.2 题目大意
描述：给你一个整数 𝑛。
要求：请你返回满足 1≤𝑎,𝑏,𝑐≤𝑛 的平方和三元组的数目。
说明：
- 平方和三元组：指的是满足 𝑎2+𝑏2=𝑐2 的整数三元组 (𝑎,𝑏,𝑐)。
- 1≤𝑛≤250。
示例：
- 示例 1：
输入 n = 5 输出 2 解释 平方和三元组为 (3,4,5) 和 (4,3,5)。
- 示例 2：
输入：n = 10 输出：4 解释：平方和三元组为 (3,4,5)，(4,3,5)，(6,8,10) 和 (8,6,10)。
3.3.3 解题思路
思路 1：枚举算法
我们可以在 [1,𝑛] 区间中枚举整数三元组 (𝑎,𝑏,𝑐) 中的 𝑎 和 𝑏。然后判断 𝑎2+𝑏2 是否小于等于 𝑛，并且是完全平方数。
在遍历枚举的同时，我们维护一个用于统计平方和三元组数目的变量 𝑐𝑛𝑡。如果符合要求，则将计数 𝑐𝑛𝑡 加 1。最终，我们返回该数目作为答案。
利用枚举算法统计平方和三元组数目的时间复杂度为 𝑂(𝑛2)。
- 注意：在计算中，为了防止浮点数造成的误差，并且两个相邻的完全平方正数之间的距离一定大于 1，所以我们可以用 𝑎2+𝑏2+1 来代替 𝑎2+𝑏2。
思路 1：代码
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
思路 1：复杂度分析
- 时间复杂度：$O(n^2)$。
- 空间复杂度：$O(1)$。