最近这段时间，如果说没做成啥事情，那确实🤦‍♂️

忙也谈不上，闲倒也没闲到哪里去，被学校这头课设、大作业和实验压着，就是一股很无力的感觉，想学不知道从哪里开始，想做却一点也做不成的感觉很强烈，挫败感更强了，更想摆烂了…

前天晚上失眠，难受就翻来覆去刷视频，然后看到了这个：

Learn Go Programming - Golang Tutorial for Beginners

一时兴起就全部看完了，真的是被压抑的太久了，居然耐住性子看到了天亮，也多亏自己这几年英语没白学，听力也是基本没有啥难度，总之就是一时爽，事后很后悔的那种。

但是不管怎么说呢，把Golang的基本语法掌握了那就该去刷刷题练练手了，不然到时候生疏了还得从头学起。

那别的不说，就先看看这周的周赛题目吧。

T1 2124. 检查是否所有 A 都在 B 之前

题目

给你一个 仅 由字符 'a' 和 'b' 组成的字符串 s 。如果字符串中 每个 'a' 都出现在 每个 'b' 之前，返回 true ；否则，返回 false 。

示例 1：

输入：s = “aaabbb”
输出：true
解释：
‘a’ 位于下标 0、1 和 2 ；而 ‘b’ 位于下标 3、4 和 5 。
因此，每个 ‘a’ 都出现在每个 ‘b’ 之前，所以返回 true 。

示例 2：

输入：s = “abab”
输出：false
解释：
存在一个 ‘a’ 位于下标 2 ，而一个 ‘b’ 位于下标 1 。
因此，不能满足每个 ‘a’ 都出现在每个 ‘b’ 之前，所以返回 false 。

示例 3：

输入：s = “bbb”
输出：true
解释：
不存在 ‘a’ ，因此可以视作每个 ‘a’ 都出现在每个 ‘b’ 之前，所以返回 true 。

提示：

1 <= s.length <= 100
s[i] 为 'a' 或 'b'

题解

水题，所有的a都要出现在所有的b之前，也就是对∀a,b\forall a, b，都有'a'的下标比'b'的下标小。

可以很容易想到的就是所有的'a'都在左侧，所有的'b'都在右侧，用双指针向中间逼近即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
func checkString(s string) bool {
    i := 0
    j := len(s) - 1
    for i < len(s) && s[i] == 'a' {
        i++
    }
    for j >= 0 && s[j] == 'b' {
        j--
    }
    return i - j == 1
}

当然还有一些别的思路，例如我们直接搜索字符串中是否存在"ba"，如果没有即为true，否则为false。

这个就有点类似脑经急转弯了，代码如下：

1
2
3
func checkString(s string) bool {
    return !strings.Contains(s, "ba")
}

T2 2125. 银行中的激光束数量

题目

银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。

对任意两个安全设备而言，如果同时 满足下面两个条件，则二者之间存在 一个 激光束：

  • 两个设备位于两个 不同行 ：r1 和 r2 ，其中 r1 < r2 。
  • 满足 r1 < i < r2 的 所有 行 i ，都 没有安全设备 。

激光束是独立的，也就是说，一个激光束既不会干扰另一个激光束，也不会与另一个激光束合并成一束。

返回银行中激光束的总数量。

示例 1：

输入：bank = [“011001”,“000000”,“010100”,“001000”]
输出：8
解释：在下面每组设备对之间，存在一条激光束。总共是 8 条激光束：

  • bank[0][1] – bank[2][1]
  • bank[0][1] – bank[2][3]
  • bank[0][2] – bank[2][1]
  • bank[0][2] – bank[2][3]
  • bank[0][5] – bank[2][1]
  • bank[0][5] – bank[2][3]
  • bank[2][1] – bank[3][2]
  • bank[2][3] – bank[3][2]

注意，第 0 行和第 3 行上的设备之间不存在激光束。
这是因为第 2 行存在安全设备，这不满足第 2 个条件。

示例 2：

输入：bank = [“000”,“111”,“000”]
输出：0
解释：不存在两个位于不同行的设备

提示：

m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j] 为 '0' 或 '1'

题解

简单的理解了题意之后，我们就基本清楚了大致的要求。

题目的要求就是排除掉当前的所有空行，将有安全装置的相邻各行之间相乘进行配对，例如示例1中，有三行存在安全装置，安全装置的数量分别为：3,2,13, 2, 1，因此我们的总激光束数量就应该是3∗2+2∗1=83 * 2 + 2 * 1 = 8。

因此，很容易的能够写出下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func numberOfBeams(bank []string) int {
    pre := -1
    res := 0
    for i := 0; i < len(bank); i++ {
        count := 0
        for j := 0; j < len(bank[i]); j++ {
            if bank[i][j] == '1' {
                count++
            }
        }
        if count != 0{
            if pre != -1 {
                res += pre * count
            }
            pre = count
        }
    }
    return res
}

这里我们引入了一个pre变量用来保存前一个有效行的装置数量，当初始化时，我们将其定为-1，表示暂无前一个有效行，在相加的时候再做特判就好了。

仔细一想，其实pre直接初始化为0的话，连特判都不需要了，这也是一个很妙的优化代码的点子。另外Golang的一些小细节我还是不熟😪，居然还有Count方法。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
func numberOfBeams(bank []string) (ans int) {
    pre := 0
    for _, row := range bank {
        cnt := strings.Count(row, "1")
        if cnt > 0 {
            ans += pre * cnt
            pre = cnt
        }
    }
    return
}

T3 2126. 摧毁小行星

题目

给你一个整数 mass ，它表示一颗行星的初始质量。再给你一个整数数组 asteroids ，其中 asteroids[i] 是第 i 颗小行星的质量。

你可以按 任意顺序 重新安排小行星的顺序，然后让行星跟它们发生碰撞。如果行星碰撞时的质量 大于等于 小行星的质量，那么小行星被 摧毁 ，并且行星会 获得 这颗小行星的质量。否则，行星将被摧毁。

如果所有小行星 都 能被摧毁，请返回 true ，否则返回 false 。

示例 1：

输入：mass = 10, asteroids = [3,9,19,5,21]
输出：true

解释：一种安排小行星的方式为 [9,19,5,3,21] ：

  • 行星与质量为 9 的小行星碰撞。新的行星质量为：10 + 9 = 19
  • 行星与质量为 19 的小行星碰撞。新的行星质量为：19 + 19 = 38
  • 行星与质量为 5 的小行星碰撞。新的行星质量为：38 + 5 = 43
  • 行星与质量为 3 的小行星碰撞。新的行星质量为：43 + 3 = 46
  • 行星与质量为 21 的小行星碰撞。新的行星质量为：46 + 21 = 67

所有小行星都被摧毁。

示例 2：

输入：mass = 5, asteroids = [4,9,23,4]
输出：false

解释：
行星无论如何没法获得足够质量去摧毁质量为 23 的小行星。
行星把别的小行星摧毁后，质量为 5 + 4 + 9 + 4 = 22 。
它比 23 小，所以无法摧毁最后一颗小行星。

提示：

1≤mass≤1051 \leq mass \leq 10^5

1≤asteroids.length≤1051 \leq asteroids.length \leq 10^5

1≤asteroids[i]≤1051 \leq asteroids[i] \leq 10^5

题解

很容易就能看出来是一道贪心，就像大鱼吃小鱼一样，从小到大排好了慢慢吃肯定是最优解。

因此我们直接对小行星的数组进行排序，随后从左向右进行简单的模拟即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
func asteroidsDestroyed(mass int, asteroids []int) bool {
    sort.Ints(asteroids)
    for _, v := range asteroids {
        if mass < v {
            return false
        }
        mass += v
    }
    return true
}

T4 2127. 参加会议的最多员工数

题目

一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。

员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。

给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。

示例 1：

输入：favorite = [2,2,1,2]
输出：3

解释：

上图展示了公司邀请员工 0，1 和 2 参加会议以及他们在圆桌上的座位。
没办法邀请所有员工参与会议，因为员工 2 没办法同时坐在 0，1 和 3 员工的旁边。
注意，公司也可以邀请员工 1，2 和 3 参加会议。

所以最多参加会议的员工数目为 3 。

示例 2：

输入：favorite = [1,2,0]
输出：3

解释：

每个员工都至少是另一个员工喜欢的员工。所以公司邀请他们所有人参加会议的前提是所有人都参加了会议。

座位安排同图 1 所示：

  • 员工 0 坐在员工 2 和 1 之间。
  • 员工 1 坐在员工 0 和 2 之间。
  • 员工 2 坐在员工 1 和 0 之间。

参与会议的最多员工数目为 3 。

示例 3：

输入：favorite = [3,0,1,4,1]
输出：4

解释：

上图展示了公司可以邀请员工 0，1，3 和 4 参加会议以及他们在圆桌上的座位。
员工 2 无法参加，因为他喜欢的员工 0 旁边的座位已经被占领了。
所以公司只能不邀请员工 2 。

参加会议的最多员工数目为 4 。

提示：

n==favorite.lengthn == favorite.length
2≤n≤1052 \leq n \leq 10^5
0≤favorite[i]≤n−10 \leq favorite[i] \leq n - 1
favorite[i]≠ifavorite[i] \neq i

题解

某种程度上，我们可以把当前的问题定义成一个有向图，每条边从当前员工指向他喜欢的员工。

看完题干，首先就能想到一些狗血的剧情（不是），比如a喜欢b，b喜欢c，c喜欢d，但是最后d又喜欢a的情形，大家把自己圈成了一个环，每个人都得不到（不是）。

于是我们就会形成如下的数据结构：

由于每个人只能喜欢一个人，因此我们的环与环之间不可能产生公共边或者公共点，这样的数据结构我们叫做基环内向树。

由于环与环之间不可能有交集，因此在本文问题中，有向图可以分为多个基环内向树，并且基环内向树之间的是相互独立没有交集的。

但是这并不是满足要求的所有情形，示例1就是一个很好的反例，我们看到员工1和员工2之间是一个互相喜欢的关系，由于这个互相喜欢的关系，我们的喜欢关系不一定要沿着一个桌子完全成环才行。

例如：

换句话说不一定要围着桌子坐成一圈，让他们单独坐一行他们也干😂他们真的很随意

在这种情况下，我们的链就会发生延伸，我们可以顺着一个节点向下到达最深处，然后把一条链上的节点全部拉出来。很显然，这种情况下，答案就不是2了。

更加恐怖的是，其实对于环的大小为2的情况下，两个节点其实都是可以发生扩展的：

因此答案就变成了节点1的最大深度+节点2的最大深度+2。

但是，更加恐怖的是，刚才已经说过了，这帮人真的很随意，没必要做成一圈也很开心😂那如果让几帮这样的人坐在一圈呢？居然也是可行的：

好了好了，我们总结一下。首先我们的最大值需要和各个环的大小进行比较（也就是一开头说的那种情况），这种情况下，最多人数自然就是环的大小。同样很自然的，环的定位我们可以使用拓扑排序来辅助完成。

另外，我们还需要处理一类“不讲唔得”的人，这类人以一个二元环为中心根节点向外拓展，这类人的情况刚才也说了，就是节点1的最大深度+节点2的最大深度+2，由于这类人可以“扎堆”，所以我们选择将每一堆人的最大深度加起来最后再和最大值比较。至于节点的最大深度，其实我们在拓扑排序的过程中处理就可以了。

代码如下：

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
func maximumInvitations(favorite []int) int {
    n := len(favorite)
  //套用拓扑排序模板，将所有环外的分枝节点全部剪去
    inDegrees := make([]int, n)
  //每个节点的最大深度
    maxDepth := make([]int, n)
  //注意到由于每个人只有一个喜欢的人，因此邻接数组其实就是favorite数组，因此可以省略
    for _, v := range favorite {
      //初始化各个节点的入度
        inDegrees[v]++
    }
  //创建队列
    queue := []int{}
    for i, v := range inDegrees {
      //从入度为0的叶子节点入手开始进行剪枝
        if v == 0 {
            queue = append(queue, i)
        }
    }
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        next := favorite[cur]
      //每次取出节点时对其父节点的最大深度进行更新
        maxDepth[next] = max(maxDepth[next], maxDepth[cur] + 1)
      //如果父节点的入度已经减为0，说明父节点已经到达树枝的边缘，直接入队，等待被剪掉
        if inDegrees[next]--; inDegrees[next] == 0 {
            queue = append(queue, next)
        }
    }
    res := 1
    sum := 0
    for i, v := range inDegrees {
      //查找入度为1的节点，顺着节点进行一圈的遍历，同时将入度抹为0
      //顺带统计一圈的节点数量
        if v == 1 {
            cur := i
            circle := []int{}
            for inDegrees[cur] == 1 {
                circle = append(circle, cur)
                inDegrees[cur]--
                cur = favorite[cur]
            }
            if len(circle) == 2 {
              //如果是二元环，即为节点1的最大深度+节点2的最大深度+2
                sum += 2
              //把结果加到总sum里面，代表一堆二元环“扎堆”
                for _, v := range circle {
                    sum += maxDepth[v]
                }
            } else {
              //否则就是直接和环的大小进行比较就好了
                res = max(res, len(circle))
            }
        }
    }
  //将答案和“扎堆”的情况进行比较更新
    res = max(res, sum)
    return res
}

func max(a, b int) int { if b > a { return b }; return a }
//噗，Go居然没有max函数