背景

好久没写过算法题了，趁着Datawhale开学这期学习获取重温一下基础算法！

本次分享设计的内容为基础算法篇，主要有：

• 枚举算法（第 01 ~ 02 天）
• 递归算法与分治算法（第 03 ~ 06 天）
• 回溯算法（第 07 ~ 09 天）
• 贪心算法（第 10 ~ 12 天）
• 位运算（第 13 ~ 14 天）

枚举算法

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

枚举算法解题思路如下：

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

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

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

练习题

1. 两数之和

思路

• 在范围内，枚举两个数即可。

代码

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""l = len(nums)for i in range(l):for j in range(i + 1, l):if nums[i] + nums[j] == target:return [i, j]return []

204. 计数质数

思路

• 首先是判断质数：可以枚举2到自己的所有可能因数，如果都不能整除，说明是质数。
• 判断质数进阶：考虑到如果 i 是 x 的因数，则 x/i 也必然是 x 的因数，则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 $[2,\sqrt{x}]$ 上。因此我们在检验 x 是否为质数时，只需要枚举$[2,\sqrt{x}]$中的所有数即可。
• 枚举即可

进阶筛法：学习链接

• 这里考虑线性筛法，即发现一个质数的倍数肯定不是质数，每次标记出来。

代码

暴力枚举（超时）：

class Solution(object):def countPrimes(self, n):""":type n: int:rtype: int"""if n < 2:return 0cnt = 0for i in range(2, n):if self.isPrime(i):cnt = cnt + 1return cntdef isPrime(self, x):if x < 2:return Falseelif x == 2:return Truel = math.sqrt(x) + 1for i in range(2, int(l)):if x % i == 0:return Falsereturn True

筛法：

class Solution(object):def countPrimes(self, n):""":type n: int:rtype: int"""if n < 2:return 0primes = [True]* nprimes[0], primes[1] = False, Falsefor i in range(2, int(pow(n, 0.5)) + 1):if primes[i]:for j in range(i * i, n, i):primes[j] = Falsereturn sum(primes)

1925. 统计平方和三元组的数目

思路

• 不难发现：n<5 时，结果为0
• 枚举a，b，同时计算出它们的平方和，这时候可以两种选择
  • 考虑计算出潜在的c，然后判断是否在剩下的数范围
  • 或者继续枚举c，计算 $c\ast c==a\ast a+b\ast b$
• 另外观察到 a和b可以互换，所以我们顺序枚举，最后得到结果*2 即可答案

代码

class Solution(object):def countTriples(self, n):""":type n: int:rtype: int"""if n < 5:return 0ans = 0for i in range(3, n + 1):for j in range(i + 1, n + 1):kk = i * i + j * jfor k in range(j + 1, n + 1):if kk == k * k:ans += 1continuereturn ans * 2