【 NO.1 检查是否每一行每一列都包含全部整数】

解题思路

签到题，可以用排序做，也可以用 Set 做。

代码展示

class Solution {

   public boolean checkValid(int[][] matrix) {

       for (int[] mat : matrix) {

           int[] m = Arrays.copyOf(mat, mat.length);

           Arrays.sort(m);

           for (int i = 0; i < m.length; i++) {

               if (m[i] != i + 1) {

                   return false;

              }

          }

      }

       for (int i = 0; i < matrix.length; i++) {

           int[] m = new int[matrix.length];

           for (int j = 0; j < matrix.length; j++) {

               m[j] = matrix[j][i];

          }

           Arrays.sort(m);

           for (int j = 0; j < m.length; j++) {

               if (m[j] != j + 1) {

                   return false;

              }

          }

      }

       return true;

  }

}

【 NO.2 最少交换次数来组合所有的 1 II】

解题思路

首先化环为链（将 nums 复制一次拼接到尾部）。

然后枚举最终结果的位置 —— 连续 tot 个 1 分布于 [i, i + tot) 下标时，需要转换的次数就是这段下标中 0 的数量。

每一段下标中 0 的数量可以用前缀和求出来。

代码展示

class Solution {

   public int minSwaps(int[] nums) {

       int[] link = new int[nums.length * 2];

       for (int i = 0; i < nums.length; i++) {

           link[i] = link[i + nums.length] = nums[i];

      }

       int[] preSum = new int[link.length];

       preSum[0] = link[0];

       for (int i = 1; i < link.length; i++) {

           preSum[i] = preSum[i - 1] + link[i];

      }

       int tot = preSum[preSum.length - 1] / 2;

       if (tot == nums.length) {

           return 0;

      }

       int max = 0;

       for (int i = tot + 1; i < preSum.length; i++) {

           max = Math.max(max, preSum[i] - preSum[i - tot]);

      }

       return tot - max;

  }

}

【 NO.3 统计追加字母可以获得的单词数】

解题思路

注意审题，只能追加一个字母。

因为题目不要求顺序，所以我们可以使用一个 26 位的二进制数来表示一个单词。

代码展示

class Solution {

   public int wordCount(String[] startWords, String[] targetWords) {

       Set startSet = new HashSet<>();

       for (var s : startWords) {

           startSet.add(toBinary(s));

      }

       int result = 0;

       for (var t : targetWords) {

           int target = toBinary(t);

           // 枚举追加的是哪个字母

           for (char c : t.toCharArray()) {

               if (startSet.contains(target - (1 << (c - 'a')))) {

                   result++;

                   break;

              }

          }

      }

       return result;

  }

   private int toBinary(String s) {

       int res = 0;

       for (char c : s.toCharArray()) {

           res += 1 << (c - 'a');

      }

       return res;

  }

}

【 NO.4 全部开花的最早一天】

解题思路

贪心，先种开花时间长的即可。

代码展示

class Solution {

   static class Flower implements Comparable {

       public Flower(int plant, int grow) {

           this.plant = plant;

           this.grow = grow;

           this.tot = grow + plant;

      }

       int plant;

       int grow;

       int tot;

       @Override

       public int compareTo(Flower o) {

           return o.grow - grow;

      }

  }

   public int earliestFullBloom(int[] plantTime, int[] growTime) {

       Flower[] flowers = new Flower[plantTime.length];

       for (int i = 0; i < plantTime.length; i++) {

           flowers[i] = new Flower(plantTime[i], growTime[i]);

      }

       Arrays.sort(flowers);

       int result = 0;

       int current = 0;

       for (var f : flowers) {

           result = Math.max(result, f.tot + current);

           current += f.plant;

      }

       return result;

  }

}