力扣第 106 场双周赛

比赛时间 2023-06-11。本场周赛国服共 333 人 AK。

T1. 判断一个数是否迷人（3 分）

解题思路

模拟。

时间复杂度：O(1)。常数约为 10。

参考代码

class Solution {
    public boolean isFascinating(int n) {
        String s = String.valueOf(n) + (n * 2) + (n * 3);
        int[] cnt = new int[10];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - '0']++;
        }
        int[] expected = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        return Arrays.equals(expected, cnt);
    }
}

T2. 找到最长的半重复子字符串（4 分）

解题思路

双指针。由于数据范围较小，也可以直接暴力。

时间复杂度：O(n)。

参考代码

class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int l = 0, r = 0;
        int cnt = 0, ans = 0;
        while (r < n) {
            if (r > 0 && cs[r] == cs[r - 1]) cnt++;
            while (cnt > 1) {
                l++;
                if (cs[l] == cs[l - 1]) cnt--;
            }
            ans = Math.max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
}

T3. 移动机器人（5 分）

解题思路

两个机器人相撞时，可以看成他们彼此擦肩而过，因此直接加 d 即可。

相似题目: 1503. 所有蚂蚁掉下来前的最后一刻 https://leetcode.cn/problems/last-moment-before-all-ants-fall-out-of-a-plank/

时间复杂度：O(n)。

参考代码

class Solution {
    private static final int MOD = (int) (1e9 + 7);

    public int sumDistance(int[] nums, String s, int d) {
        int n = nums.length;
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nums[i] + (s.charAt(i) == 'R' ? d : -d);
        }

        Arrays.sort(arr);
        long ans = 0L;
        for (int i = 1; i < n; i++) {
            long d1 = arr[i] - arr[i - 1];
            ans = (ans + d1 * (i) % MOD * (n - i) % MOD) % MOD;
        }
        return (int) ans;
    }
}

T4. 找到矩阵中的好子集（6 分）

解题思路

状态压缩枚举。猜想：

• 当 n <= 5 时，不存在大小大于 2 的好集合。
• 当 n > 5 时，可能存在大小为 4 的好集合，如：

101010
100101
011001
010110

详见 tiger2005 的证明：https://leetcode.cn/circle/discuss/9UKZwR/view/5AVVpH/

时间复杂度：O(2^2n)。理论上界 32 * 32 = 1024。

参考代码

class Solution {
    public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // 2^5 = 32 个数
        Map<Integer, List<Integer>> maskIdxMap = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int mask = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    mask |= 1 << j;
                }
            }
            maskIdxMap.computeIfAbsent(mask, key -> new ArrayList<>()).add(i);
        }

        // 特判 mask = 0
        if (maskIdxMap.containsKey(0)) {
            return List.of(maskIdxMap.get(0).get(0));
        }

        List<Integer> resList = new ArrayList<>();
        for (Map.Entry<Integer, List<Integer>> entry1 : maskIdxMap.entrySet()) {
            int mask1 = entry1.getKey();
            List<Integer> val1 = entry1.getValue();

            for (Map.Entry<Integer, List<Integer>> entry2 : maskIdxMap.entrySet()) {
                int mask2 = entry2.getKey();
                List<Integer> val2 = entry2.getValue();

                // 如果 (mask1 & mask2) == 0，那么 mask1 != mask2
                if ((mask1 & mask2) == 0) {
                    resList.add(val1.get(0));
                    resList.add(val2.get(0));
                    resList.sort(null);
                    return resList;
                }
            }
        }
        return resList;
    }
}

（全文完）