上岸算法 发表于 2022-1-9 21:41:18

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

【 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 + 1) {
                   return false;
            }
          }
      }
       for (int i = 0; i < matrix.length; i++) {
         int[] m = new int;
         for (int j = 0; j < matrix.length; j++) {
               m = matrix;
          }
         Arrays.sort(m);
         for (int j = 0; j < m.length; j++) {
               if (m != 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;
       for (int i = 0; i < nums.length; i++) {
         link = link = nums;
      }
       int[] preSum = new int;
       preSum = link;
       for (int i = 1; i < link.length; i++) {
         preSum = preSum + link;
      }
       int tot = preSum / 2;
       if (tot == nums.length) {
         return 0;
      }
       int max = 0;
       for (int i = tot + 1; i < preSum.length; i++) {
         max = Math.max(max, preSum - preSum);
      }
       return tot - max;
}
}


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

解题思路
注意审题,只能追加一个字母。

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

代码展示

class Solution {
   public int wordCount(String[] startWords, String[] targetWords) {
       Set<Integer> 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<Flower> {
       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;
       for (int i = 0; i < plantTime.length; i++) {
         flowers = new Flower(plantTime, growTime);
      }
       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;
}
}
页: [1]
查看完整版本: 上岸算法LeetCode Weekly Contest 275解题报告