欢迎大家加QQ群：623375442，可以方便群里面交流。现在LeetCode的周赛真的越来越恶心的，第三题纯纯数学。希望LeetCode没有办法解决AI的问题的话，索性停办周赛算了。
100576. Maximum Sum With at Most K Elements
给你一个大小为 n x m 的二维矩阵 grid ，以及一个长度为 n 的整数数组 limits ，和一个整数 k 。你的目标是从矩阵 grid 中提取出 至多 k 个元素，并计算这些元素的最大总和，提取时需满足以下限制：
- 从 grid 的第 i 行提取的元素数量不超过 limits[i] 。
返回最大总和。
测试样例：
输入：grid = [[1,2],[3,4]], limits = [1,2], k = 2
输出：7
解释：
- 从第 2 行提取至多 2 个元素，取出 4 和 3 。
- 至多提取 2 个元素时的最大总和 4 + 3 = 7 。
解答：遍历过程中，利用优先队列减少数据。
class Solution {
public long maxSum(int[][] grid, int[] limits, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < grid.length; ++i) {
PriorityQueue<Integer> tmp = new PriorityQueue<>();
for (int n : grid[i]) {
tmp.add(n);
if (tmp.size() > limits[i]) {
tmp.poll();
}
}
for (int n : tmp) {
queue.add(n);
if (queue.size() > k) {
queue.poll();
}
}
}
long res = 0;
for (int n : queue) {
res += n;
}
return res;
}
}100585. Check If Digits Are Equal in String After Operations II
给你一个由数字组成的字符串 s 。重复执行以下操作，直到字符串恰好包含 两个 数字：
- 从第一个数字开始，对于 s 中的每一对连续数字，计算这两个数字的和 模 10。
- 用计算得到的新数字依次替换 s 的每一个字符，并保持原本的顺序。
如果 s 最后剩下的两个数字相同，则返回 true 。否则，返回 false。
测试样例：
输入：s = "3902"
输出：true
解答：能知道是杨辉三角，但是这个模10还要扩展欧几里得算法真的不会。。。
class Solution {
public boolean hasSameDigits(String s) {
int n = s.length();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = s.charAt(i) - '0';
}
long[][] frac = new long[n + 1][3];
frac[0][0] = 1;
for (int i = 1; i <= n; i++) {
int t = i, c2 = 0, c5 = 0;
while (t % 2 == 0) {
c2++;
t /= 2;
}
while (t % 5 == 0) {
c5++;
t /= 5;
}
frac[i][0] = frac[i - 1][0] * t % 10;
frac[i][1] = frac[i - 1][1] + c2;
frac[i][2] = frac[i - 1][2] + c5;
}
long[] c = new long[n - 1];
long s1 = 0, s2 = 0;
int[] re = {0, 1, 0, 7, 0, 0, 0, 3, 0, 9};
for (int i = 0; i < n - 1; i++) {
long c2 = frac[n - 2][1] - frac[i][1] - frac[n - i - 2][1];
long c5 = frac[n - 2][2] - frac[i][2] - frac[n - i - 2][2];
if (c2 > 0 && c5 > 0) continue;
c[i] = frac[n - 2][0] * re[(int) frac[i][0]] * re[(int) frac[n - i - 2][0]] * quickMulti(2, c2, 10) * quickMulti(5, c5, 10) % 10;
s1 += arr[i] * c[i];
s1 = s1 % 10;
s2 += arr[i + 1] * c[i];
s2 = s2 % 10;
}
return s1 == s2;
}
private long quickMulti(long a, long q, int mod) {
long res = 1;
long p = 1;
long v = a;
while (p <= q) {
if ((q & p) != 0) {
res *= v;
res %= mod;
}
p = (p << 1);
v = v * v % mod;
}
return res;
}
}100592. Maximize the Distance Between Points on a Square
给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。
同时给你一个 正整数 k 和一个二维整数数组 points，其中 points[i] = [xi, yi] 表示一个点在正方形边界上的坐标。
你需要从 points 中选择 k 个元素，使得任意两个点之间的 最小 曼哈顿距离 最大化 。
返回选定的 k 个点之间的 最小 曼哈顿距离的 最大 可能值。
两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。
测试样例：
输入：side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4
输出：2
class Solution {
public int maxDistance(int side, int[][] points, int k) {
ArrayList<int[]> arr1 = new ArrayList<>();
ArrayList<int[]> arr2 = new ArrayList<>();
ArrayList<int[]> arr3 = new ArrayList<>();
ArrayList<int[]> arr4 = new ArrayList<>();
int n = points.length;
for (int[] p : points) {
if (p[0] == 0) {
arr1.add(p);
} else if (p[1] == side) {
arr2.add(p);
} else if (p[0] == side) {
arr3.add(p);
} else {
arr4.add(p);
}
}
arr1.sort((o1, o2) -> Integer.compare(o1[1], o2[1]));
arr2.sort((o1, o2) -> Integer.compare(o1[0], o2[0]));
arr3.sort((o1, o2) -> Integer.compare(o2[1], o1[1]));
arr4.sort((o1, o2) -> Integer.compare(o2[0], o1[0]));
long s = side;
ArrayList<Long> arr = new ArrayList<>(n);
for (int[] v : arr1) arr.add((long) v[1]);
for (int[] v : arr2) arr.add(v[0] + s);
for (int[] v : arr3) arr.add(s - v[1] + 2 * s);
for (int[] v : arr4) arr.add(s - v[0] + 3 * s);
TreeSet<Long> ts = new TreeSet<>();
for (long v : arr) {
ts.add(v);
ts.add(v + s * 4);
}
int l = 0, r = side;
while (l < r) {
int m = l + (r - l + 1) / 2;
boolean flag = false;
for (Long v : arr) {
boolean t = true;
long p = v;
for (int i = 0; i < k - 1; i++) {
Long p1 = ts.ceiling(p + m);
if (p1 == null || p1 >= v + s * 4) {
t = false;
break;
} else {
p = p1;
}
}
if (p + m > v + s * 4) t = false;
if (t) {
flag = t;
break;
}
}
if (flag) {
l = m;
} else {
r = m - 1;
}
}
return l;
}
}