侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学, 哈希表, 计数】统计一个数组中好对子的数目

GabrielxD
2022-08-09 / 0 评论 / 0 点赞 / 75 阅读 / 855 字 / 正在检测是否收录...

题目

1814. 统计一个数组中好对子的数目


给你一个数组 nums ,数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 , rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是 好的 :

  • 0 <= i < j < nums.length
  • nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

请你返回好下标对的数目。由于结果可能会很大,请将结果对 10^9 + 7 取余 后返回。

示例 1:

输入:nums = [42,11,1,97]
输出:2
解释:两个坐标对为:
 - (0,3):42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
 - (1,2):11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。

示例 2:

输入:nums = [13,10,35,24,76]
输出:4

提示:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

解题

方法一:哈希表 数学 计数

思路

好对子需要满足的条件:nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

这个式子变形一下:nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])

这个题就变成了:【数学, 哈希表, 计数】好数对的数目 ,只不过把对 count(i) 求组合数变成了对 count(nums[i] - rev(nums[i])) 求组合数。

注意数据范围,不用 long long(c++) 或者 long(java) 可能会溢出。

代码

class Solution {
    const int MOD = 1e9 + 7;

    int rev(int x) {
        string str_x = to_string(x);
        reverse(str_x.begin(), str_x.end());
        return stoi(str_x);
    }

public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, long long> counts;
        for (int& num : nums) ++counts[num - rev(num)];
        int ans = 0;
        for (auto& [k, v] : counts) ans = (ans + (v * (v - 1) / 2)) % MOD;
        return ans;
    }
};
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countNicePairs(int[] nums) {
        Map<Integer, Long> map = new HashMap<>();
        for (int num : nums) {
            int tmp = num - Integer.parseInt(new StringBuilder(Integer.toString(num)).reverse().toString());
            map.put(tmp, map.getOrDefault(tmp, 0L) + 1);
        }
        int ans = 0;
        for (long count : map.values()) ans = (int) ((ans + (count * (count - 1) / 2)) % MOD);
        return ans;
    }
}

用字符串辅助反转数字未免有点浪费,可以换成取模运算:

class Solution {
    const int MOD = 1e9 + 7;

    int rev(int x) {
        int rev_x = 0;
        while (x) {
            rev_x = rev_x * 10 + x % 10;
            x /= 10;
        }
        return rev_x;
    }

public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, long long> counts;
        for (int& num : nums) ++counts[num - rev(num)];
        int ans = 0;
        for (auto& [k, v] : counts) ans = (ans + (v * (v - 1) / 2)) % MOD;
        return ans;
    }
};
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countNicePairs(int[] nums) {
        Map<Integer, Long> map = new HashMap<>();
        for (int num : nums) {
            int diff = num - rev(num);
            map.put(diff, map.getOrDefault(diff, 0L) + 1);
        }
        int ans = 0;
        for (long count : map.values()) ans = (int) ((ans + (count * (count - 1) / 2)) % MOD);
        return ans;
    }

    private int rev(int x) {
        int rev_x = 0;
        while (x != 0) {
            rev_x = rev_x * 10 + x % 10;
            x /= 10;
        }
        return rev_x;
    }
}

用累加的方式求排列数,仅需一次遍历:

class Solution {
    const int MOD = 1e9 + 7;

    int rev(int x) {
        int rev_x = 0;
        while (x) {
            rev_x = rev_x * 10 + x % 10;
            x /= 10;
        }
        
        return rev_x;
    }

public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, long long> counts;
        int ans = 0;
        for (int& num : nums) {
            int tmp = num - rev(num);
            long long* count = &counts[tmp];
            ans = (ans + *count) % MOD;
            (*count)++;
        }
        
        return ans;
    }
};
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countNicePairs(int[] nums) {
        Map<Integer, Long> map = new HashMap<>();
        int ans = 0;
        for (int num : nums) {
            int diff = num - rev(num);
            long count = map.getOrDefault(diff, 0L);
            ans = (int) (ans + count) % MOD;
            map.put(diff, count + 1);
        }
        return ans;
    }

    private int rev(int x) {
        int rev_x = 0;
        while (x != 0) {
            rev_x = rev_x * 10 + x % 10;
            x /= 10;
        }
        return rev_x;
    }
}
0

评论区