时间戳

首页 > 解决方案 > 在 Leetcode 中计数 Nice Pairs 给了我错误的结果

java - 在 Leetcode 中计数 Nice Pairs 给了我错误的结果

问题描述

我最近在 Leetcode 中遇到了一个有趣的问题。这是问题网址。

i因此，简单来说，计算与 2 个索引和的以下条件匹配的对数j。

nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

我认为的简单解决方案是保持整数的计数及其倒数并找到 NC2。

这是我的方法，

class Solution {
    public int countNicePairs(int[] nums) {
        
        int[] rev = new int[nums.length];
        
        for(int i=0;i< nums.length;i++){
            rev[i] = Integer.parseInt(new StringBuilder(String.valueOf(nums[i])).reverse().toString());
        }
        
        System.out.println(Arrays.toString(rev));
        
        Map<Integer,Integer> map = new HashMap<>();
        
        for(int i=0;i<nums.length;i++){
            int diff = Math.abs(rev[i]-nums[i]);
            map.put(diff,map.getOrDefault(diff,0)+1);
        }
        
        int mod = (int)(1e9 +7);
        
        long op = 0;
        
        for(int val: map.values()){
            op +=((long)(val)*(long)(val-1)/(long)2);
            op = op%mod;
        }
        
        
        return (int)(op%mod);
    }
}

此代码在 4 个测试用例中失败。并且其中提到的示例粘贴在https://justpaste.it/2n1ka

My answer : 92976930
Expected answer : 92974217

如您所见，输入很大，我无法调试我的代码有什么问题。

标签： javaalgorithm

解决方案

问题出在这一行：

int diff = Math.abs(rev[i]-nums[i]);

您假设差异中整数的符号无关紧要，但确实如此。例如：

[21,12]

在这里，这两个数字作为数组本身的元素都有它们的反面，并且它们不是很好的一对，因为(21 - 12) != (12 - 21). 请注意，符号在这里很重要，对此的答案是，0但你的返回1是不正确的。

解决方案：

只需删除绝对值检查。你的计算应该遵循nums[i] - rev(nums[i]) = nums[j] - rev(nums[j])但你正在做相反的事情，比如将两边乘以-1（这也可以）。所以，只要做

int diff = rev[i]-nums[i];

旁注：您可以通过在 for 循环迭代期间为每个元素本身计算来完全删除rev数组。rev

推荐阅读