算法基础算法

分类讨论

字数统计: 2.5k字   |   阅读时长: 10分
, ,

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

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

分类讨论是算法中常见的一种思想，这种思想没有固定的套路，需要结合具体的问题进行分析。本文给出 4 道题，其中【29. 两数相除】和【335. 路径交叉】在此前我们单独讲解过，本文我们详解【420. 强密码检验器】和【672. 灯泡开关 Ⅱ】这两道题，来体会一下分类讨论的思想再具体问题中是如何展开的。

420. 强密码检验器

问题

一个强密码应满足以下所有条件：

由至少6个，至多20个字符组成。
至少包含一个小写字母，一个大写字母，和一个数字。
同一字符不能连续出现三次 (比如 “…aaa…” 是不允许的, 但是 “…aa…a…” 是可以的)。
编写函数 strongPasswordChecker(s)，s 代表输入字符串，如果 s 已经符合强密码条件，则返回0；否则返回要将 s 修改为满足强密码条件的字符串所需要进行修改的最小步数。

插入、删除、替换任一字符都算作一次修改。

分析

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

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

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

这里面有几个特性：

  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 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后，你需要返回这 n 只灯泡可能有多少种不同的状态。

假设这 n 只灯泡被编号为 [1, 2, 3 …, n]，这 4 个按钮的功能如下：

  • 将所有灯泡的状态反转（即开变为关，关变为开）
  • 将编号为偶数的灯泡的状态反转
  • 将编号为奇数的灯泡的状态反转
  • 将编号为 3k+1 的灯泡的状态反转（k = 0, 1, 2, …)

分析

分析操作序列的循环性

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

首先看一串操作序列，一行灯泡可以产生哪些状态。以长度为 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 -> 01101101$
  • $bd : 11111111 -> 00111000$
  • $cd : 11111111 -> 11000111$
  • $da : 11111111 -> 01101101$
  • $dv : 11111111 -> 00111000$
  • $dc : 11111111 -> 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;
        }
    }
};

335. 路径交叉

问题

给定一个含有 n 个正数的数组 x。从点 (0,0) 开始，先向北移动 x[0] 米，然后向西移动 x[1] 米，向南移动 x[2] 米，向东移动 x[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

编写一个 O(1) 空间复杂度的一趟扫描算法，判断你所经过的路径是否相交。

分析

【分类讨论】力扣335-路径交叉

29. 两数相除

问题

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

分析

【分类讨论】力扣29-两数相除

Share