算法基础算法

分类讨论

字数统计: 3k字   |   阅读时长: 12分
, ,

摘要: 本文通过两道题来说明分类讨论在算法中的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

分类讨论是算法中常见的一种思想，这种思想没有固定的套路，需要结合具体的问题进行分析。本文列出 5 道题，其中【29. 两数相除】和【335. 路径交叉】在此前我们单独讲解过，参考文章 【分类讨论】力扣335-路径交叉 和 【分类讨论】力扣29-两数相除。

本文我们详解【420. 强密码检验器】和【672. 灯泡开关 Ⅱ】这两道题，其余的题直接给出代码。来体会一下分类讨论的思想再具体问题中是如何展开的。

420. 强密码检验器

满足以下条件的密码被认为是强密码：

  • 由至少 6 个，至多 20 个字符组成。
  • 包含至少 一个小写 字母，至少 一个大写 字母，和至少 一个数字 。
  • 不包含连续三个重复字符 (比如 “Baaabb0” 是弱密码, 但是 “Baaba0” 是强密码)。

给你一个字符串 password ，返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0 。

在一步修改操作中，你可以：

  • 插入一个字符到 password ，
  • 从 password 中删除一个字符，或
  • 用另一个字符来替换 password 中的某个字符。

提示：

1
2
1 <= password.length <= 50
password 由字母、数字、点 '.' 或者感叹号 '!' 组成

示例 1：
输入：password = “a”
输出：5

示例 2：
输入：password = “aA1”
输出：3

示例 3：
输入：password = “1337C0d3”
输出：0

算法：分类讨论

不满足强密码的串，有三种类型的问题：长度不对(长了或短了), 缺少类型，有三连串。

有三种操作，插入，删除，修改。分别能解决一些问题：

  • 插入可以解决长度短了，缺少类型，和三连串问题
  • 删除可以解决长度长了，和三连串问题
  • 修改可以解决，缺少类型，和三连串问题

这里面有几个特性：

  1. 长度问题，必须通过插入删除来修正，长了要用删除，短了要用插入。
  2. 为了解决长度问题必须使用的插入删除操作，可以抵扣一些解决缺少类型和三连串问题的操作。具体地，插入可以抵扣解决缺少类型问题的操作；删除可以抵扣解决三连串问题的操作。
  3. 虽然插入可以解决三连串问题，但是不用分析将解决长度问题的插入操作用于抵扣解决三连串问题的操作。因为长度如果短了，一定小于 5。插入的字符肯定可以
  4. 插入，删除，修改都可以解决三连串问题，但是效率上 修改 > 插入 > 删除，例如一次操作，修改可以解决 len = 5 的情况，插入可以解决 len = 4 的情况，删除只能解决 len = 3 的情况。
  5. 基于第 4 点，如果长度满足要求，则应该所有操作都用修改。

基于这些特性，算法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
miss := 缺少的类型个数
k3[i] := 模 3 余 i 的三连串的长度列表
k3_all := 只用修改，解决所有三连串所需的次数

对 n 分类讨论: 

n < 6:  答案为 max(6 - l, miss)

6 <= n <= 20: 答案为 max(miss, k3_all)

n > 20: 删除 n - 20 次
这些删除可以无法抵扣解决类型确实的操作，但可以抵扣解决三连串的操作
抵扣顺序：
    先抵扣模 3 余 0 的，每个串可以用 1 个删除抵扣一次，完成后若长度 len - 1 仍大于 3，则放入 k3[2] 中
    然后抵扣模 3 余 1 的，每个串可以用 2 个删除抵扣一次，完成后若长度 len - 2 仍大于 3，则放入 k3[2] 中
    最后抵扣模 3 余 2 的: 每个串可以持续抵扣知道剩余长度 < 3。用 3 个删除抵扣 1 次。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class Solution {
public:
    int strongPasswordChecker(string s) {
        // 小写，大写，数字缺少的种类数，可以改或者插入
        int miss = check_miss(s);
        // k3[0] := 3n 型的各个长度
        // k3[1] := 3n + 1 型的各个长度
        // k3[2] := 3n + 2 型的各个长度
        vector<vector<int>> k3 = check3(s);

        int n = s.size();

        if(n < 6)
        {
            return max(6 - n, miss);
        }
        else
        {
            int k3_all = 0;
            for(auto i: k3)
                for(int len: i)
                    k3_all += len / 3;
            if(n <= 20)
                return max(miss, k3_all);
            else
            {
                // 如果全都用替换，解决所有三连串需要 k3_all 步
                // 下面看至少要做的 n - 20 步删除可以替换几步
                int N = n - 20; // 解决长度溢出的删除次数
                // 先替换 3n 型, 一次删除可以抵一次替换
                while(!k3[0].empty() && N > 0)
                {
                    int len = k3[0].back();
                    --N;
                    k3[0].pop_back();
                    --k3_all;
                    if(len - 1 >= 3)
                        k3[2].push_back(len - 1);
                }
                // 再替换 3n + 1 型，2 次删除可以抵 1 次替换
                while(!k3[1].empty() && N > 1)
                {
                    int len = k3[1].back();
                    N -= 2;
                    k3[1].pop_back();
                    --k3_all;
                    if(len - 2 >= 3)
                        k3[2].push_back(len - 2);
                }
                // 最后替换 3n + 1 型，3 次删除可以抵 1 次替换
                while(!k3[2].empty() && N > 2)
                {
                    int len = k3[2].back();
                    N -= 3;
                    --k3_all;
                    if(len - 3 >= 5)
                        k3[2].back() -= 3;
                    else
                        k3[2].pop_back();
                }
                // 如果是 empty 退出的而不是 N 耗尽，
                // 则 n - 20 的删除将处理三连串所需的改操作全都抵扣了
                return n - 20 + max(k3_all, miss);
            }
        }
    }

private:
    int check_miss(const string& s)
    {
        bool f1 = 1, f2 = 1, f3 = 1;
        for(const char &ch: s)
        {
            if(ch >= 'A' && ch <= 'Z')
                f1 = 0;
            if(ch >= 'a' && ch <= 'z')
                f2 = 0;
            if(ch >= '0' && ch <= '9')
                f3 = 0;
            if(f1 + f2 + f3 == 0)
                break;
        }
        return f1 +  f2 + f3;
    }

    vector<vector<int>> check3(const string& s)
    {
        int n = s.size();
        int i = 0;
        vector<vector<int>> result(3);
        while(i < n)
        {
            char ch = s[i];
            int j = i;
            while(j < n && s[j] == ch)
                ++j;
            int len = j - i;
            if(len >= 3)
                result[len % 3].push_back(len);
            i = j;
        }
        return result;
    }
};

672. 灯泡开关 Ⅱ

房间中有 n 只已经打开的灯泡，编号从 1 到 n 。墙上挂着 4 个开关 。

这 4 个开关各自都具有不同的功能，其中：

  • 开关 1 ：反转当前所有灯的状态（即开变为关，关变为开）
  • 开关 2 ：反转编号为偶数的灯的状态（即 0, 2, 4, …）
  • 开关 3 ：反转编号为奇数的灯的状态（即 1, 3, …）
  • 开关 4 ：反转编号为 j = 3k + 1 的灯的状态，其中 k = 0, 1, 2, …（即 1, 4, 7, 10, …）

你必须 恰好 按压开关 presses 次。每次按压，你都需要从 4 个开关中选出一个来执行按压操作。

给你两个整数 n 和 presses ，执行完所有按压之后，返回 不同可能状态 的数量。

提示：

1
2
1 <= n <= 1000
0 <= presses <= 1000

示例 1：
输入：n = 1, presses = 1
输出：2
解释：状态可以是：

  • 按压开关 1 ，[关]
  • 按压开关 2 ，[开]

示例 2：
输入：n = 2, presses = 1
输出：3
解释：状态可以是：

  • 按压开关 1 ，[关, 关]
  • 按压开关 2 ，[开, 关]
  • 按压开关 3 ，[关, 开]

示例 3：
输入：n = 3, presses = 1
输出：4
解释：状态可以是：

  • 按压开关 1 ，[关, 关, 关]
  • 按压开关 2 ，[关, 开, 关]
  • 按压开关 3 ，[开, 关, 开]
  • 按压开关 4 ，[关, 开, 开]

算法：分类讨论

分析操作序列的循环性

寻找操作序列的循环性，当找到循环性之后，只需要分析循环节内的情况就可以了

首先看一串操作序列，一行灯泡可以产生哪些状态。以长度为 8 为例子，初始状态 11111111 记为 1，一次操作后可以到达 4 中状态，分别对应 abcd 这 4 种操作。

1
2
3
4
5
6
操作编号  状态编号    状态
初始      0           11111111
a         1           00000000
b         2           01010101
c         3           10101010
d         4           10010010

考虑两次操作的时候，就出现循环了，具体地：操作序列为 aa, bb, cc, dd，都会到达一个此前已有的状态 0，发生循环。但是也有不发生循环的例如操作序列 14。

如果长度为2的操作序列没有 d 这个操作，则一定发生了循环，例如 ab 这个操作序列，原始的 11111111 会变成 10101010，这相当于 ab 这个操作序列等价于一步操作 c。类似地可以得到以下等价性:

  • $aa \Leftrightarrow 无操作$
  • $bb \Leftrightarrow 无操作$
  • $cc \Leftrightarrow 无操作$
  • $ab \Leftrightarrow c$
  • $ac \Leftrightarrow b$
  • $ba \Leftrightarrow c$
  • $bc \Leftrightarrow a$
  • $ca \Leftrightarrow b$
  • $cb \Leftrightarrow a$

当考虑含 d 的长为 2 的操作序列，有一些还是会回到原有状态上

  • $dd \Leftrightarrow 无操作$

剩下的均会产生新状态的是以下操作：产生了三种新状态，将三种新状态记为 5,6,7，分别对应操作序列 ad, bd, cd，将这三个操作序列标记为 e, f, g。

  • $ad : 11111111 \rightarrow 01101101$
  • $bd : 11111111 \rightarrow 00111000$
  • $cd : 11111111 \rightarrow 11000111$
  • $da : 11111111 \rightarrow 01101101$
  • $dv : 11111111 \rightarrow 00111000$
  • $dc : 11111111 \rightarrow 11000111$

于是操作和状态的关系表更新如下：

1
2
3
4
5
6
7
8
9
操作编号  状态编号    状态
初始      0           11111111
a         1           00000000
b         2           01010101
c         3           10101010
d         4           10010010
e(ad)     5           01101101
f(bd)     6           00111000
g(cd)     7           11000111

当考虑长度为 3 的操作序列时候，会发现所有的序列都会到达一个已有的状态。此时操作序列再边长也不会有新状态了。

分析 m 和 n 的大小和关系

剩下的就是分析 m 和 n 的情况了:

m \ n 0 1 2 >= 3
0 1 1 1 1
1 1 2 3 4
2 1 2 4 7
>= 3 1 2 4 8

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int flipLights(int n, int m) {
        if(n == 0 || m == 0)
            return 1;
        else if(n == 1)
            return 2;
        else if(n == 2)
        {
            if(m == 1)
                return 3;
            else
                return 4;
        }
        else
        {
            if(m == 1)
                return 4;
            else if(m == 2)
                return 7;
            else
                return 8;
        }
    }
};

2437. 有效时间的数目

给你一个长度为 5 的字符串 time ，表示一个电子时钟当前的时间，格式为 “hh:mm” 。最早 可能的时间是 “00:00” ，最晚 可能的时间是 “23:59” 。

在字符串 time 中，被字符 ? 替换掉的数位是 未知的 ，被替换的数字可能是 0 到 9 中的任何一个。

请你返回一个整数 answer ，将每一个 ? 都用 0 到 9 中一个数字替换后，可以得到的有效时间的数目。

示例 1：
输入：time = “?5:00”
输出：2
解释：我们可以将 ? 替换成 0 或 1 ，得到 “05:00” 或者 “15:00” 。注意我们不能替换成 2 ，因为时间 “25:00” 是无效时间。所以我们有两个选择。

示例 2：
输入：time = “0?:0?”
输出：100
解释：两个 ? 都可以被 0 到 9 之间的任意数字替换，所以我们总共有 100 种选择。

示例 3：
输入：time = “??:??”
输出：1440
解释：小时总共有 24 种选择，分钟总共有 60 种选择。所以总共有 24 * 60 = 1440 种选择。

提示：

1
2
3
4
time 是一个长度为 5 的有效字符串，格式为 "hh:mm" 。
"00" <= hh <= "23"
"00" <= mm <= "59"
字符串中有的数位是 '?' ，需要用 0 到 9 之间的数字替换。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def countTime(self, time: str) -> int:
        ans = 1

        if time[0] == '?' and time[1] == '?':
            ans *= 24
        elif time[0] == '?':
            if time[1] <= '3':
                ans *= 3
            else:
                ans *= 2
        elif time[1] == '?':
            if time[0] == '2':
                ans *= 4
            else:
                ans *= 10

        if time[3] == '?' and time[4] == '?':
            ans *= 60
        elif time[3] == '?':
            ans *= 6
        elif time[4] == '?':
            ans *= 10

        return ans
Share