class Solution {
public:
int countPairs(vector<int>& nums) {
}
};
3265. 统计近似相等数对 I
给你一个正整数数组 nums 。
如果我们执行以下操作 至多一次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：
x 或者 y 之一，将这个数字中的两个数位交换。请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。
注意 ，执行操作后一个整数可以有前导 0 。
示例 1：
输入：nums = [3,12,30,17,21]
输出：2
解释：
近似相等数对包括：
示例 2：
输入：nums = [1,1,1,1,1]
输出：10
解释：
数组中的任意两个元素都是近似相等的。
示例 3：
输入：nums = [123,231]
输出：0
解释：
我们无法通过交换 123 或者 321 中的两个数位得到另一个数。
提示：
2 <= nums.length <= 1001 <= nums[i] <= 106相似题目
原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 6.5 MB, 提交时间: 2024-08-26 09:59:49
func countPairs(nums []int) (ans int) {
slices.Sort(nums)
cnt := map[int]int{}
for _, x := range nums {
set := map[int]struct{}{x: {}} // 不交换
s := []byte(strconv.Itoa(x))
m := len(s)
for i := range s {
for j := i + 1; j < m; j++ {
s[i], s[j] = s[j], s[i]
set[atoi(s)] = struct{}{} // 交换一次
s[i], s[j] = s[j], s[i]
}
}
for x := range set {
ans += cnt[x]
}
cnt[x]++
}
return
}
// 手动转 int 快一些
func atoi(s []byte) (res int) {
for _, b := range s {
res = res*10 + int(b&15)
}
return
}
python3 解法, 执行用时: 106 ms, 内存消耗: 16.6 MB, 提交时间: 2024-08-26 09:59:32
class Solution:
def countPairs(self, nums: List[int]) -> int:
nums.sort()
ans = 0
cnt = defaultdict(int)
for x in nums:
st = {x} # 不交换
s = list(str(x))
m = len(s)
for i in range(m):
for j in range(i + 1, m):
s[i], s[j] = s[j], s[i]
st.add(int(''.join(s))) # 交换一次
s[i], s[j] = s[j], s[i]
ans += sum(cnt[v] for v in st)
cnt[x] += 1
return ans
java 解法, 执行用时: 35 ms, 内存消耗: 44 MB, 提交时间: 2024-08-26 09:59:13
class Solution {
public int countPairs(int[] nums) {
Arrays.sort(nums);
int ans = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
Set<Integer> st = new HashSet<>();
st.add(x); // 不交换
char[] s = Integer.toString(x).toCharArray();
int m = s.length;
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
swap(s, i, j);
st.add(Integer.parseInt(new String(s))); // 交换一次
swap(s, i, j);
}
}
for (int v : st) {
ans += cnt.getOrDefault(v, 0);
}
cnt.merge(x, 1, Integer::sum);
}
return ans;
}
private void swap(char[] s, int i, int j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
cpp 解法, 执行用时: 59 ms, 内存消耗: 38.3 MB, 提交时间: 2024-08-26 09:59:01
class Solution {
public:
int countPairs(vector<int>& nums) {
ranges::sort(nums);
int ans = 0;
unordered_map<int, int> cnt;
for (int x : nums) {
unordered_set<int> st = {x}; // 不交换
string s = to_string(x);
int m = s.length();
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
swap(s[i], s[j]);
st.insert(stoi(s)); // 交换一次
swap(s[i], s[j]);
}
}
for (int v : st) {
ans += cnt.contains(v) ? cnt[v] : 0;
}
cnt[x]++;
}
return ans;
}
};