上岸算法LeetCode Weekly Contest 274解题报告

上岸算法 · 发表于 2022-1-3 21:30:37

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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 参加会议的最多员工数】

解题思路
实际参加会议有两种情况：

刚好是一个环中的人参加会议，这样可以使得每个人都喜欢自己左侧的人。

有两个人相互喜欢，然后剩下的人形成一条链，比如 [1,0,0,2,1,4,7,8,9,6,7,10,8]，这样不要求首尾相接，可以有多条链。

代码展示

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[i];
         int to = i;
         if (favorite[from] == 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[i] && favorite[favorite[i]] == i) {
            result += maxLen(i, reverse) + maxLen(favorite[i], 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[favorite.length];
   int res = 0;
   for (int i = 0; i < favorite.length; i++) {
         if (favorite[favorite[i]] == i) {
            max[i] = max[favorite[i]] = 2;
      }
         if (max[i] == 0) {
            step.clear();
            getMaxCircle(0, i, step, max, favorite);
      }
         res = Math.max(res, max[i]);
   }
   return res;
  }

private void getMaxCircle(int i, int cur, Map<Integer, Integer> step, int[] max, int[] favorite) {
   if (step.containsKey(cur)) {
         max[cur] = i - step.get(cur);
         return;
   }
   step.put(cur, i);
   int nxt = favorite[cur];
   if (max[nxt] > 0) {
         max[cur] = max[nxt];
         return;
   }
   getMaxCircle(i + 1, nxt, step, max, favorite);
   max[cur] = max[nxt];
  }
}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 274解题报告

登录后可回复主题

浏览过的版块