第 130 场力扣夜喵双周赛（VP）

正方形中的最多点数

题目

输入长度为 \(n\) 的二维数组 \(points\) 和字符串 \(s\)，\(points[i]\) 表示第 \(i\) 个点的坐标，\(s[i]\) 表示第 \(i\) 个点的标签。如果以 \((0,0)\) 为中心且边平行于坐标轴的正方形内（包括边上的点，且边长可以为 \(0\)），不包含标签相同的两个点，则该正方形是合法的。输出合法正方形可以包含的最多点数。其中 \(points\) 中的点互不相同，\(s\) 只包含小写英文字母。

数据范围：\(1\leq n\leq 10^{5}\)，\(-10^{9}\leq points[i][0],points[i][1]\leq 10^{9}\)。

思路

首先可以想到，正方形的边长越长，包含的点就越多，越可能不合法。具有单调性，可以使用二分求解。在二分的过程中，判断正方形是否合法，如果合法则更新答案。时间复杂度为 \(O(n\log{U})\)，其中 \(U=\max_{i=0}^{n-1}(|x_{i}|,|y_{i}|)\)。更好的做法是观察到，如果正方形包含某个点 \((x,y)\)，则正方形的边长 \(len\) 必须满足 \(len\geq 2\times\max(|x|,|y|)\)。其中，\(\max(|x|,|y|)\) 是点 \((x,y)\) 到点 \((0,0)\) 的切比雪夫距离。实际上，我们只需要维护每种标签点的最小切比雪夫距离 \(min_{i}\)，以及除此之外所有点的最小切比雪夫距离 \(k\)。因为，如果正方形包含某个标签 \(i\)，必定是包含具有该标签的切比雪夫距离最小的那个点，而这个点需要满足 \(min_{i}<k\)。详情见代码，时间复杂度为 \(O(n)\)。优化思路参考灵神题解。

代码

class Solution {
    public int maxPointsInsideSquare(int[][] points, String s) {
        int n = points.length;
        int[] min = new int[26];
        Arrays.fill(min, Integer.MAX_VALUE);

        int k = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            int z = Math.max(Math.abs(x), Math.abs(y));
            int c = s.charAt(i) - 'a';
            if (z < min[c]) {
                k = Math.min(k, min[c]);
                min[c] = z;
            } else {
                k = Math.min(k, z);
            }
        }

        int ans = 0;
        for (int x : min) {
            if (x < k) {
                ans++;
            }
        }
        return ans;
    }
}

分割字符频率相等的最少子字符串

题目

输入长度为 \(n\) 的字符串 \(s\)（只包含小写英文字母），输出 \(s\) 最少能被分割为多少个平衡子字符串。平衡字符串就是字符串中不同字符出现频次都相同的字符串。

数据范围：\(1\leq n\leq 1000\)。

思路

定义 \(dp[i+1]\) 表示字符串 \([0,i]\) 最少能被分割的平衡子字符串数目，则转移方程为 \(dp[i+1]=\min(dp[j]+1)\)，其中 \(0\leq j\leq i\) 且字符串 \([j,i]\) 必须是平衡字符串。

代码

class Solution {
    public int minimumSubstringsInPartition(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            dp[i + 1] = i + 1;
            int k = 0, max = 0;
            int[] cnt = new int[26];
            for (int j = i; j >= 0; j--) {
                k += cnt[s.charAt(j) - 'a'] == 0 ? 1 : 0;
                max = Math.max(max, ++cnt[s.charAt(j) - 'a']);
                if (i - j + 1 == k * max) {
                    dp[i + 1] = Math.min(dp[i + 1], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }
}

大数组元素的乘积

不会。