上岸算法LeetCode Weekly Contest 274解题报告
【 NO.1 检查是否所有 A 都在 B 之前】解题思路
签到题。
代码展示
class Solution {
public boolean checkString(String s) {
return !s.contains("a") || !s.contains("b") || s.lastIndexOf('a') < s.indexOf('b');
}
}
【 NO.2 银行中的激光束数量】
解题思路
统计每行 1 的数量即可，如果没有 1 则跳过。
代码展示
class Solution {
public int numberOfBeams(String[] bank) {
int result = 0;
int last = 0;
for (var s : bank) {
int count = count1(s);
if (count > 0) {
result += count * last;
last = count;
}
}
return result;
}
private int count1(String s) {
int r = 0;
for (var c : s.toCharArray()) {
if (c == '1') {
r++;
}
}
return r;
}
}
【 NO.3 摧毁小行星】
解题思路
排序即可，注意使用 long。
代码展示
class Solution {
public boolean asteroidsDestroyed(int mass, int[] asteroids) {
Arrays.sort(asteroids);
long m = mass;
for (int a : asteroids) {
if (m >= a) {
m += a;
continue;
}
return false;
}
return true;
}
}
【 NO.4 参加会议的最多员工数】
解题思路
实际参加会议有两种情况：
刚好是一个环中的人参加会议，这样可以使得每个人都喜欢自己左侧的人。
有两个人相互喜欢，然后剩下的人形成一条链，比如 ，这样不要求首尾相接，可以有多条链。
代码展示
class Solution {
public int maximumInvitations(int[] favorite) {
// 1 找一个完整的环
// 2 找多条链
return Math.max(maxCircle(favorite), multipleLink(favorite));
}
private int multipleLink(int[] favorite) {
Map<Integer, List<Integer>> reverse = new HashMap<>();
for (int i = 0; i < favorite.length; i++) {
int from = favorite;
int to = i;
if (favorite == to) {
continue;
}
if (!reverse.containsKey(from)) {
reverse.put(from, new ArrayList<>());
}
reverse.get(from).add(to);
}
int result = 0;
for (int i = 0; i < favorite.length; i++) {
if (i < favorite && favorite] == i) {
result += maxLen(i, reverse) + maxLen(favorite, reverse);
}
}
return result;
}
private int maxLen(int start, Map<Integer, List<Integer>> reverse) {
if (!reverse.containsKey(start)) {
return 1;
}
int max = 0;
for (int next : reverse.get(start)) {
max = Math.max(max, maxLen(next, reverse));
}
return max + 1;
}
private int maxCircle(int[] favorite) {
Map<Integer, Integer> step = new HashMap<>();
int[] max = new int;
int res = 0;
for (int i = 0; i < favorite.length; i++) {
if (favorite] == i) {
max = max] = 2;
}
if (max == 0) {
step.clear();
getMaxCircle(0, i, step, max, favorite);
}
res = Math.max(res, max);
}
return res;
}
private void getMaxCircle(int i, int cur, Map<Integer, Integer> step, int[] max, int[] favorite) {
if (step.containsKey(cur)) {
max = i - step.get(cur);
return;
}
step.put(cur, i);
int nxt = favorite;
if (max > 0) {
max = max;
return;
}
getMaxCircle(i + 1, nxt, step, max, favorite);
max = max;
}
}
页:
[1]