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

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

登录后可回复主题

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

x

【 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<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[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;
  }
}

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

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

登录后可回复主题