枚举

我个人认为，枚举比较难总结出像DP、并查集一样的通用模板，而是随着题目变化而变化。但也有一些基本原则。

在最简单的情况下，可以直接枚举所有可能的解来获得答案。但更一般的情况下，解空间可能会很大，这时候需要根据具体题目的特点来将解空间缩小到允许的复杂度，再进行枚举。

根据我个人的经验，如果在通读题目并进行模拟之后，还是很难发现题目内在的一些规律（比如递推关系等），那么就要考虑枚举、二分查找答案之类的与题目内在逻辑无关的做法。

1. 统计子串中的唯一字符

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

我的思路是分情况统计每一个位置上的字符的贡献。

不管是我的思路，还是灵神的思路，都好像没用到枚举，不知道为什么这题归为枚举……

另外灵神给出了一个思考子串统计类问题的通用技巧之一：

• 将所有子串按照其末尾字符的下标分组。
• 考虑两组相邻的子串：以 s[i−1]s[i-1]s[i−1] 结尾的子串、以 s[i]s[i]s[i] 结尾的子串。
• 以 s[i]s[i]s[i] 结尾的子串，可以看成是以 s[i−1]s[i-1]s[i−1]结尾的子串，在末尾添加上 s[i]s[i]s[i]` 组成。

具体参见这篇

代码

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        ans = 0
        n = len(s)
        c = [[] for i in range(26)]
        for i in range(n):
            c[ord(s[i]) - ord('A')].append(i)
        for i in range(26):
            if c[i] == []: continue # 字符不存在，跳过
            elif len(c[i]) == 1: # 字符唯一，贡献等于所有包含了它的子串数
                ans += (c[i][0] + 1) * (n - c[i][0])
            else: # 字符不唯一，分三种情况讨论，字符前无相同字符；字符两边都有相同字符；字符后无相同字符
                for j in range(len(c[i])):
                    if j == 0:
                        ans += (c[i][j] + 1) * (c[i][j + 1] - c[i][j])
                    elif j < len(c[i]) - 1:
                        ans += (c[i][j] - c[i][j - 1]) * (c[i][j + 1] - c[i][j])
                    else:
                        ans += (c[i][j] - c[i][j - 1]) * (n - c[i][j])
        return ans

2. 每种字符至少取 K 个

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

本周周赛题。

解法是枚举可能的 i 、 j 组合。 i 是从左取到的下标终点， j 是从右边取到的下标终点。每当枚举一个新的 i 时，应当让 j 尽可能大。

初始时，假设不从左边取，然后从 0 开始枚举。

本题应当在手动模拟几轮后，发现如果经由每次左右两端的对比来决定取谁的话会非常繁琐且不容易实现。还要认识到最终无非是两端取几个的问题，可以使用枚举。

代码

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        n = len(s)
        c = Counter()
        j = n
        while c['a'] < k or c['b'] < k or c['c'] < k:
            if j == 0: return -1
            j -= 1
            c[s[j]] += 1
        ans = n - j
        for i, ch in enumerate(s):
            c[ch] += 1
            while j < n and c[s[j]] > k:
                c[s[j]] -= 1
                j += 1
            ans = ans if ans < i + 1 + n - j else i + 1 + n - j
            if j == n: break
        return ans

3. 礼盒的最大甜蜜度

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

尝试模拟后无法发现题目有何内在逻辑，但注意到答案在有限区间内，且有 check 的方法，那么可以使用二分。这里不太容易想到如何 check 。

当确定一个差 d 时，对排序后的数组去取，最小的数必定是可以取的，然后取第一个大于等于 x + d 的数。如果最终取不到要求的数量，就往左走，否则往右走。

代码

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        n = len(price)
        l, r = 0, price[n - 1] - price[0] # 确定答案上下限
        ans = 0
        while l <= r:
            m = (l + r) >> 1
            # 开始 check
            cnt, x, idx = 1, price[0], 1
            while idx < n and cnt < k:
                if price[idx] >= x + m:
                    x = price[idx]
                    cnt += 1
                idx += 1

            if cnt == k:
                ans = ans if ans > m else m # 满足条件，向右继续
                l = m + 1
            else: r = m - 1 # 不满足，向左继续

        return ans

4. 计数质数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

说是枚举也没什么问题，但说是暴力 + 数学更贴切一点。

用数学上的方法来筛选出所有小于 n 的质数即可。

代码

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:  return 0
        nums = [1 for i in range(n + 1)]
        nums[0] = 0
        nums[1] = 0
        for num in range(2, int(sqrt(n)) + 1):
            if nums[num]:
                for i in range(num * num, n + 1, num):
                    nums[i] = 0
        return sum(nums[:n])

5. 数组中的最长山脉

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

一次遍历及常数空间通过。但是如果看不到错误用例，又会找不到哪里有问题。

虽然打着枚举标签，但感觉用不到枚举，用枚举的话，我的初步思路是检查所有山顶点，即两个相邻元素小于自身的点，向两边拓展来计算长度，取最长的一个。但这样就不算一次遍历了。虽然枚举的代码更容易理解。

代码

一次遍历做法

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        ans = 0
        n = len(arr)
        cnt = 1
        down = False
        for i in range(1, n):
            if (not down) and arr[i] > arr[i - 1]: cnt += 1
            elif arr[i] < arr[i - 1]:
                if cnt > 1:
                    down = True
                    cnt += 1
                else:
                    down = False
                    cnt = 1
            elif down and arr[i] > arr[i - 1]:
                down = False
                ans = ans if ans > cnt else cnt
                cnt = 2
            elif arr[i] == arr[i - 1]:
                if down:
                    ans = ans if ans > cnt else cnt
                    down = False
                cnt = 1
        if down: ans = ans if ans > cnt else cnt
        return ans

枚举做法

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        ans = 0
        n = len(arr)
        for i in range(1, n - 1):
            if arr[i - 1] < arr[i] and arr[i + 1] < arr[i]:
                cnt = 1
                for j in range(i - 1, -1, -1):
                    if arr[j] < arr[j + 1]: cnt += 1
                    else: break
                for k in range(i + 1, n):
                    if arr[k] < arr[k - 1]: cnt += 1
                    else: break
                ans = ans if ans > cnt else cnt
        return ans

6. 重新排序得到 2 的幂

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

统计词频即可。因为在数据范围内的 2 的幂非常有限，仅有30个，只要统计这30个数的词频，即可快速判断。

如果用枚举的话，可以用回溯找出每一个 n 的重排数，然后判断是否为 2 的幂。这里的判断可以用 bit_count() 实现，即重排数的二进制形式中， 1 的个数是否恰好为 1 。

代码

class Solution:
    def __init__(self):
        self.dicts = [defaultdict(int) for i in range(30)]
        for i in range(30):
            num = 1 << i
            while num:
                self.dicts[i][num % 10] += 1
                num //= 10
        print(self.dicts)
    def reorderedPowerOf2(self, n: int) -> bool:
        dic = defaultdict(int)
        while n:
            dic[n % 10] += 1
            n //= 10
        return dic in self.dicts