【 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> 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> 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];

  }

}