100149. Find Missing and Repeated Values
给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。
任务是找出重复的数字a 和缺失的数字 b 。
返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。
测试样例：
输入：grid = [[1,3],[2,2]]
输出：[2,4]
解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。
解答：这题可以利用位运算符 + 原地正负位运算，用O(1)的空间完成计算。但是easy题，就直接用HashMap暴力算了。
class Solution {
public int[] findMissingAndRepeatedValues(int[][] grid) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int[] r : grid) {
for (int n : r) {
map.put(n, map.getOrDefault(n, 0) + 1);
}
}
int[] res = new int[2];
for (int i = 1; i <= grid.length * grid.length; ++i) {
int tmp = map.getOrDefault(i, 0);
if (tmp == 2) {
res[0] = i;
} else if (tmp == 0) {
res[1] = i;
}
}
return res;
}
}100161. Divide Array Into Arrays With Max Difference
给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。
将这个数组划分为一个或多个长度为 3 的子数组，并满足以下条件：
- nums 中的 每个 元素都必须 恰好 存在于某个子数组中。
- 子数组中 任意 两个元素的差必须小于或等于 k 。
返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。
测试样例：
输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
输出：[[1,1,3],[3,4,5],[7,8,9]]
解释：可以将数组划分为以下子数组：[1,1,3]，[3,4,5] 和 [7,8,9] 。每个子数组中任意两个元素的差都小于或等于 2 。注意，元素的顺序并不重要。
解答：将数组排序之后，往最终结果中填充。因为已经排序了，这个条件：子数组中 任意 两个元素的差必须小于或等于 k 。应该是最容易满足的，如果无法达到要求，返回空数组。
class Solution {
private static final int[][] fail = new int[0][];
public int[][] divideArray(int[] nums, int k) {
Arrays.sort(nums);
int[][] res = new int[nums.length / 3][3];
for (int i = 0; i < nums.length; ++i) {
int x = i / 3, y = i % 3;
res[x][y] = nums[i];
if (res[x][y] - res[x][0] > k) {
return fail;
}
}
return res;
}
}100151. Minimum Cost to Make Array Equalindromic
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
你可以对 nums 执行特殊操作 任意次 （也可以 0 次）。每一次特殊操作中，你需要 按顺序 执行以下步骤：
- 从范围 [0, n - 1] 里选择一个下标 i 和一个 正 整数 x 。
- 将 |nums[i] - x| 添加到总代价里。
- 将 nums[i] 变为 x 。
如果一个正整数正着读和反着读都相同，那么我们称这个数是 回文数 。比方说，121 ，2552 和 65756 都是回文数，但是 24 ，46 ，235 都不是回文数。
如果一个数组中的所有元素都等于一个整数 y ，且 y 是一个小于 10^9 的 回文数 ，那么我们称这个数组是一个 等数数组 。
请你返回一个整数，表示执行任意次特殊操作后使 nums 成为 等数数组 的 最小 总代价。
测试样例：
输入：nums = [1,2,3,4,5]
输出：6
解释：我们可以将数组中所有元素变为回文数 3 得到等数数组，数组变成 [3,3,3,3,3] 需要执行 4 次特殊操作，代价为 |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6 。
将所有元素变为其他回文数的总代价都大于 6 。
解答：绝对值求和，可以很快速的知道，取中位数是最佳结果。接下来的问题就是寻找中位数附近的回文数，并且枚举出最优解。寻找附近的回文数可以把中位数从当中切分，然后把这半个数分别进行-1, 0, +1操作，并拼接回去。这样形成的数一定是最接近的回文数。然后暴力枚举这三种情况的最优值。
class Solution {
private static final int[] oper = {0,-1,1};
public long minimumCost(int[] nums) {
Arrays.sort(nums);
int mid = nums[nums.length / 2];
long min = Long.MAX_VALUE;
for (long t : findPalindromic(mid)) {
long cur = 0;
for (int n : nums) {
cur += Math.abs(t - n);
}
min = Math.min(min, cur);
}
return min;
}
private long[] findPalindromic(int n) {
String tmp = String.valueOf(n);
String split = tmp.substring(0, tmp.length() / 2 + (tmp.length() % 2));
int val = Integer.parseInt(split);
long[] res = new long[3];
for (int i = 0; i < oper.length; ++i) {
String v = String.valueOf(val + oper[i]);
if (v.length() < split.length() || (oper[i] == -1 && val == 1 && tmp.length() == 2)) {
res[i] = res[0] - 2;
} else if (v.length() > split.length()) {
res[i] = res[0] + 2;
} else if (tmp.length() % 2 == 0) {
StringBuilder sb = new StringBuilder(v);
res[i] = Long.parseLong(v + sb.reverse().toString());
} else {
StringBuilder sb = new StringBuilder(v);
res[i] = Long.parseLong(v.substring(0, v.length() - 1) + sb.reverse().toString());
}
}
return res;
}
}100123. Apply Operations to Maximize Frequency Score
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
你可以对数组执行 至多 k 次操作：
- 从数组中选择一个下标 i ，将 nums[i] 增加 或者 减少 1 。
最终数组的频率分数定义为数组中众数的 频率 。
请你返回你可以得到的 最大 频率分数。
众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。
测试样例：
输入：nums = [1,2,6,4], k = 3
输出：3
解释：我们可以对数组执行以下操作：
- 选择 i = 0 ，将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,3] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,2] 。
元素 2 是最终数组中的众数，出现了 3 次，所以频率分数为 3 。3 是所有可行方案里的最大频率分数。
解答：今天的题目还真是喜欢用到中位数这个性质。这题还是排序（这样最接近的数就会在相邻位置）。然后利用双指针来寻找最佳范围。
class Solution {
public int maxFrequencyScore(int[] nums, long k) {
Arrays.sort(nums);
long[] prefixSum = new long[nums.length + 1];
for (int i = 0; i < nums.length; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int st = 0, ed = 0;
int res = 0;
while (st < nums.length) {
while (ed < nums.length && cal(nums, prefixSum, st, ed) <= k) {
++ed;
}
res = Math.max(res, ed - st);
++st;
ed = Math.max(st, ed);
}
return res;
}
private long cal(int[] nums, long[] prefixSum, int st, int ed) {
int mid = (st + ed) / 2;
long midNum = nums[mid];
long diff = midNum * (mid - st + 1) - (prefixSum[mid + 1] - prefixSum[st]);
if (mid + 1 <= ed) {
diff += prefixSum[ed + 1] - prefixSum[mid + 1] - midNum * (ed - mid - 1 + 1);
}
return diff;
}
}