欢迎大家加QQ群：623375442，可以方便群里面交流。
100394. Count Almost Equal Pairs I
给你一个正整数数组 nums 。
如果我们执行以下操作 至多一次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：
- 选择 x 或者 y 之一，将这个数字中的两个数位交换。
请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。
注意 ，执行操作后一个整数可以有前导 0 。
测试样例：
输入：nums = [3,12,30,17,21]
输出：2
解释：近似相等数对包括：
- 3 和 30 。交换 30 中的数位 3 和 0 ，得到 3 。
- 12 和 21 。交换12 中的数位 1 和 2 ，得到 21 。
解答：这题范围不大，我们之间暴力两重循环，然后暴力计算这两个数是否相似。
class Solution {
public int countPairs(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
if (nums[i] == nums[j] || distanceOne(nums[i], nums[j])) {
++res;
}
}
}
return res;
}
private boolean distanceOne(int n1, int n2) {
if (n1 > n2) {
return distanceOne(n2, n1);
}
String str1 = String.valueOf(n1), str2 = String.valueOf(n2);
while (str1.length() != str2.length()) {
str1 = '0' + str1;
}
int firstMis = -1;
boolean isUsed = false;
for (int i = 0; i < str1.length(); ++i) {
if (str1.charAt(i) != str2.charAt(i)) {
if (isUsed) {
return false;
} else if (firstMis == -1) {
firstMis = i;
} else if (str1.charAt(firstMis) == str2.charAt(i) && str1.charAt(i) == str2.charAt(firstMis)) {
firstMis = -1;
isUsed = true;
} else {
return false;
}
}
}
return firstMis == -1;
}
}100412. Final Array State After K Multiplication Operations II
给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。
你需要对 nums 执行 k 次操作，每次操作中：
- 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
- 将 x 替换为 x * multiplier 。
k 次操作以后，你需要将 nums 中每一个数值对 10^9 + 7 取余。
请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。
测试样例：
输入：nums = [2,1,3,5,6], k = 5, multiplier = 2
输出：[8,4,6,5,6]
解释：
操作 结果
- 1 次操作后 [2, 2, 3, 5, 6]
- 2 次操作后 [4, 2, 3, 5, 6]
- 3 次操作后 [4, 4, 3, 5, 6]
- 4 次操作后 [4, 4, 6, 5, 6]
- 5 次操作后 [8, 4, 6, 5, 6]
取余操作后 [8, 4, 6, 5, 6]
解答：首先需要注意multiplier = 1的情况。我TLE了2次，一直以为是算法复杂度不对。
首先我们先暴力计算一下，让整个数组的最大和最小相除小于multiplier。这样，每次循环就是对这个数组按大小遍历一次。根据取余数的情况，平铺一下操作。
class Solution {
private static final int mod = 1_000_000_007;
public int[] getFinalState(int[] nums, int k, int multiplier) {
if (multiplier == 1) {
return nums;
}
long[] dup = new long[nums.length];
TreeSet<Integer> set = new TreeSet<>((a, b) -> (dup[a] != dup[b] ? Long.compare(dup[a], dup[b]) : Long.compare(a, b)));
for (int i = 0; i < dup.length; ++i) {
dup[i] = nums[i];
set.add(i);
}
// 让整个数组的最大和最小相除小于multiplier。比如[2,1,3,5,6] -> [4, 4, 6, 5, 6]。之后，就是按照大小按顺序一个个乘multilpler
while (dup[set.first()] * multiplier <= dup[set.last()] && k > 0) {
int f = set.pollFirst();
dup[f] *= multiplier;
set.add(f);
--k;
}
if (k == 0) {
return turnArr(dup);
} else {
// 平均分配次数
int time = k / nums.length, remain = k % nums.length;
int count = 0;
HashMap<Integer, Long> mem = new HashMap<>();
for (int i : set) {
int curTime = time;
if (count < remain) {
curTime += 1;
}
dup[i] = (dup[i] % mod) * mul(multiplier, curTime, mem) % mod;
++count;
}
return turnArr(dup);
}
}
private int[] turnArr(long[] dup) {
int[] res = new int[dup.length];
for (int i = 0; i < res.length; ++i) {
res[i] = (int) (dup[i] % mod);
}
return res;
}
private long mul(int mul, int time, HashMap<Integer, Long> mem) {
if (time == 0) {
return 1;
} else if (!mem.containsKey(time)) {
long tmp = mul(mul, time / 2, mem);
tmp = (tmp * tmp) % mod;
if (time % 2 == 1) {
tmp = (tmp * mul) % mod;
}
mem.put(time, tmp);
}
return mem.get(time);
}
}100403. Count Almost Equal Pairs II
注意：在这个问题中，操作次数增加为至多 两次 。
给你一个正整数数组 nums 。
如果我们执行以下操作 至多两次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：
- 选择 x 或者 y 之一，将这个数字中的两个数位交换。
请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。
注意 ，执行操作后得到的整数可以有前导 0 。
注意，该整数 不 含前导零。
测试样例：
输入：nums = [1023,2310,2130,213]
输出：4
解释：近似相等数对包括：
- 1023 和 2310 。交换 1023 中数位 1 和 2 ，然后交换数位 0 和 3 ，得到 2310 。
- 1023 和 213 。交换 1023 中数位 1 和 0 ，然后交换数位 1 和 2 ，得到 0213 ，也就是 213 。
- 2310 和 213 。交换 2310 中数位 2 和 0 ，然后交换数位 3 和 2 ，得到 0213 ，也就是 213 。
- 2310 和 2130 。交换 2310 中数位 3 和 1 ，得到 2130 。
解答：本来以为这题可以用第二题的算法暴力过，没想到会超时。那就反向思维一下，我们遍历数组。将每个数的任意2组数字互换，查看能有多少hit到的次数。
class Solution {
public int countPairs(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
map.put(n, map.getOrDefault(n, 0) + 1);
}
int res = 0;
for (int n : nums) {
int[] arr = trans(n);
Set<Integer> set = new HashSet<>();
map.put(n, map.get(n) - 1);
for (int a = 0; a < 8; ++a) {
for (int b = a + 1; b < 8; ++b) {
// 任意2位互换一次
swap(arr, a, b);
{
int num = trans(arr);
if (!set.contains(num)) {
set.add(num);
res += map.getOrDefault(num, 0);
}
}
for (int c = 0; c < 8; ++c) {
for (int d = c + 1; d < 8; ++d) {
// 任意2位再互换一次
swap(arr, c, d);
{
int num = trans(arr);
if (!set.contains(num)) {
set.add(num);
res += map.getOrDefault(num, 0);
}
}
swap(arr, c, d);
}
}
swap(arr, a, b);
}
}
}
return res;
}
private int[] trans(int n) {
int[] arr = new int[8];
for (int i = 7; i >= 0; --i) {
arr[i] = n % 10;
n /= 10;
}
return arr;
}
private int trans(int[] n) {
int res = 0;
for (int i = 0; i < n.length; ++i) {
res = res * 10 + n[i];
}
return res;
}
private void swap(int[] arr, int x, int y) {
int tmp = arr[y];
arr[y] = arr[x];
arr[x] = tmp;
}
}