前三题都比较简单，第四题调了很久，终于在结束后的10分钟靠自己的努力写出来了！
还好没掉分！！
5967. 检查是否所有 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出现的位置，比较他们的大小
class Solution {public boolean checkString(String s) {int n = s.length();int lasta = -1, firstb = n;for (int i = 0; i < n; i++) {char ch = s.charAt(i);if (ch == 'a') lasta = i;else firstb = Math.min(firstb, i);}return lasta < firstb;}}
5968. 银行中的激光束数量
银行内部的防盗安全装置已经激活。给你一个下标从 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’
思路：
就很简单的题，遍历计算即可
class Solution {public int numberOfBeams(String[] bank) {int last = 0;int res = 0;int n = bank.length, m = bank[0].length();for (int i = 0; i < n; i++) {int cnt = 0;for (int j = 0; j < m; j++) {if (bank[i].charAt(j) == '1')cnt++;}res += last * cnt;if (cnt != 0)last = cnt;}return res;}}
5969. 摧毁小行星
给你一个整数 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 <= 105
- 1 <= asteroids.length <= 105
- 1 <= asteroids[i] <= 105
思路：
贪心，将小行星按质量从小到大排序，依次用行星撞，能撞就加，不能撞返回false，能全部撞完返回true
class Solution {public boolean asteroidsDestroyed(int mass, int[] a) {Arrays.sort(a);long x = mass;for (int v : a) {if (x >= v)x += v;elsereturn false;}return true;}}
方法2：一种基于桶的线性做法
桶依次为[1, 2), [2, 4), [4, 8), ... [2x - 1, 2x]，数据范围在10^5以内，实际只需17个即可，我开了30个，不过不影响。
将所有数加到对应桶中并记录每个桶的最小值
遍历所有桶，如果当前行星质量小于桶中最小值，说明不够撞了，返回false
否则加上这个最小值后，会大于等于该桶内的所有值。故依次添加桶内所有值即可。
class Solution {public boolean asteroidsDestroyed(int mass, int[] asteroids) {List<Integer>[] list = new ArrayList[30];int[] min = new int[30];Arrays.fill(min, 200000);for (int i = 0; i < 30; i++)list[i] = new ArrayList<>();boolean flag = true;for (int x : asteroids) {int cur = x;int i;for (i = 30; i >= 0; i--)if ((1 << i & cur) != 0)break;list[i].add(x);min[i] = Math.min(min[i], x);}long w = mass;int idx = 0;for (List<Integer> ll : list) {if (ll.size() == 0) {idx++;continue;}if (w < min[idx++]) {flag = false;break;} else {for (int x : ll) {w += x;}}}return flag;}}
5970. 参加会议的最多员工数
一个公司准备组织一场会议，邀请名单上有 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.length
- 2 <= n <= 105
- 0 <= favorite[i] <= n - 1
- favorite[i] != i
思路;
可以将所有人分组，每个组都是一个仅有一个环的树形结构
将所有相关联的组分成两大类，根据环的大小来分，分成等于2和大于2的两类
所有环等于2的组能合并到一起(每个组中能坐到一起的最大值是环能延申出的最长链包含的人数)，而所有环大于2的组只能是成环的那些人能坐在一起。
故最终结果在两者中取max即可
代码实现思路：
- 先建反向图，如果a要靠b，就连一条边从b指向a
找到所有长为2的环，对每个环进行深搜找最长路径并累加，在深搜过程中对已经搜过的点打标记
- 对所有剩余节点建正向图，如果a要靠b，就连一条边从a指向b，并记录每条边的入度
将所有入度为0的点入队，依次处理每组节点
找到环并统计环长，和最终结果取max，在这个过程中将遍历过的打上标记
- 剩余那些没打标记的形成了几个首尾相连的环，每一组可以从任意起点处开始深搜，
找到环并统计环长，和最终结果取max，在这个过程中将遍历过的打上标记
- 返回最终结果即可
class Solution {int N = 100010;int[] h = new int[N], e = new int[N], ne = new int[N];int n, idx;boolean[] st = new boolean[N];public int maximumInvitations(int[] a) {n = a.length;Arrays.fill(h, -1);int[] cin = new int[n];// 1List<Integer> list = new ArrayList<>();for (int i = 0; i < n; i++) {if (i == a[a[i]])list.add(i);int b = i, c = a[i];add(c, b);}int res = 0;int cc = 0;for (int x : list) {int b = x, c = a[x];if (st[b]) continue;st[b] = st[c] = true;int cnt = 0;cnt += dfs(b, a) + dfs(c, a);cc += cnt;}res = Math.max(res, cc);// 2Arrays.fill(h, -1);idx = 0;for (int i = 0; i < n; i++) {int b = i, c = a[i];add(b, c);cin[c]++;}Queue<Integer> q = new LinkedList<>();for (int i = 0; i < n; i++) {if (!st[i] && cin[i] == 0)q.offer(i);}while (!q.isEmpty()) {int cur = q.poll();int slow = cur, fast = cur;int cnt = 0;do {slow = a[slow];st[slow] = true;fast = a[a[fast]];} while (slow != fast);slow = cur;while (slow != fast) {slow = a[slow];fast = a[fast];st[fast] = true;}do {fast = a[fast];cnt++;} while (fast != slow);res = Math.max(cnt, res);}for (int i = 0; i < n; i++) {if (!st[i])res = Math.max(dfs2(i, a), res);}// 3for (int i = 0; i < n; i++) {if (!st[i])res = Math.max(res, dfs2(i, a));}// 4return res;}int dfs2(int u, int[] a) {st[u] = true;int res = 1;if (!st[a[u]])res += dfs(a[u], a);return res;}void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}int dfs(int u, int[] a) {int cnt = 1;int max = 0;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!st[j]) {st[j] = true;max = Math.max(max, dfs(j, a));}}return cnt + max;}}
若有收获，就点个赞吧
0 人点赞
