力扣第 275 场周赛

比赛时间 2022-01-09。本场周赛国服共 606 人 AK。

T1. 检查是否每一行每一列都包含全部整数（3 分）

解题思路

模拟。这里用 BitSet 记录每个整数是否出现，再用 BitSet#cardinality() 判断每个整数是否都出现。

时间复杂度：O(n^2)。

参考代码

class Solution {
    public boolean checkValid(int[][] matrix) {
        // n == matrix.length == matrix[i].length
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            BitSet row = new BitSet(n);
            BitSet col = new BitSet(n);
            for (int j = 0; j < n; j++) {
                row.set(matrix[i][j]);
                col.set(matrix[j][i]);
            }
            if (row.cardinality() != n || col.cardinality() != n) {
                return false;
            }
        }
        return true;
    }
}

T2. 最少交换次数来组合所有的 1 II（4 分）

解题思路

前缀和 + 贪心。用两倍长数组模拟环形数组，其余同 $1151. 最少交换次数来组合所有的 1。

时间复杂度：O(n)。

参考代码

class Solution {
    public int minSwaps(int[] nums) {
        int len = nums.length;
        // 两倍长度数组
        int[] nums2 = new int[len * 2];
        for (int i = 0; i < len; i++) {
            nums2[i] = nums[i];
            nums2[i + len] = nums[i];
        }

        // 前缀和
        int[] preSum = new int[len * 2 + 1];
        for (int i = 0; i < len * 2; i++) {
            preSum[i + 1] = preSum[i] + nums2[i];
        }

        // 贪心
        // 1 的个数
        int k = preSum[len];
        // [left, left+sum]
        int max = 0;
        for (int i = 0; i + k <= len * 2; i++) {
            max = Math.max(max, preSum[i + k] - preSum[i]);
        }
        return k - max;
    }
}

T3. 统计追加字母可以获得的单词数（5 分）

解题思路

先预处理 startWords 所有可以组合的可能，再逐个判断 targetWords 的字符串是否满足条件（字符串中的字母升序排序后 HashSet 判断）。

数据范围 5 * 10^4 * 26 近似 10^6，可以过。

时间复杂度 O(S*26log26 + T*26log26)，其中 S = startWords.length，T = targetWords.length。

参考代码

class Solution {
    public int wordCount(String[] startWords, String[] targetWords) {
        // 预处理 startWords
        Set<String> memo = new HashSet<>();
        for (String startWord : startWords) {
            int len = startWord.length();
            char[] oldChars = startWord.toCharArray();
            BitSet bitSet = new BitSet(26);
            for (int i = 0; i < len; i++) {
                bitSet.set(oldChars[i] - 'a');
            }
            for (int i = 0; i < 26; i++) {
                if (!bitSet.get(i)) {
                    String newStartWord = startWord.concat(String.valueOf((char) ('a' + i)));
                    char[] newChars = newStartWord.toCharArray();
                    Arrays.sort(newChars);
                    memo.add(new String(newChars));
                }
            }
        }

        // 统计
        int cnt = 0;
        for (String targetWord : targetWords) {
            char[] chars = targetWord.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            if (memo.contains(key)) {
                cnt++;
            }
        }
        return cnt;
    }
}

T4. 全部开花的最早一天（6 分）

解题思路

贪心。通过调整种子顺序找规律，发现最优方案为：生长时间久的先种，可用贪心解决。

时间复杂度：O(nlogn)，为排序所需的时间复杂度。

参考代码

class Solution {
    public int earliestFullBloom(int[] plantTime, int[] growTime) {
        // 贪心。生长时间久的先种
        int n = plantTime.length;
        int[][] plantGrow = new int[n][2];
        for (int i = 0; i < n; i++) {
            plantGrow[i][0] = plantTime[i];
            plantGrow[i][1] = growTime[i];
        }
        Arrays.sort(plantGrow, (o1, o2) -> Integer.compare(o2[1], o1[1]));

        int max = plantGrow[0][0] + plantGrow[0][1];
        int startPlant = plantGrow[0][0] - 1;
        for (int i = 1; i < n; i++) {
            startPlant += plantGrow[i][0];
            max = Math.max(max, startPlant + plantGrow[i][1] + 1);
        }
        return max;
    }
}

（全文完）