可以读通讯稿的组数

简介: 可以读通讯稿的组数

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

校运动会上,所有参赛同学身上都贴有他的参赛号码。某班参赛同学的号码记于数组 nums 中。假定反转后的号码称为原数字的「镜像号码」。如果 两位同学 满足条件:镜像号码 A + 原号码 B = 镜像号码 B + 原号码 A,则这两位同学可以到广播站兑换一次读通讯稿的机会,为同班同学加油助威。请返回所有参赛同学可以组成的可以读通讯稿的组数,并将结果对10^9+7取余。

注意:

  • 镜像号码中如存在前置零,则忽略前置零。
  • 同一位同学可有多次兑换机会。
    示例 1:
输入:nums = [17,28,39,71]
输出:3
解释:
共有三对同学,分别为 [17,28]、[17,39]、[28,39]。其中:
第一对同学:17 + 82 = 71 + 28;
第二对同学:17 + 93 = 71 + 39;
第三对同学:28 + 93 = 82 + 39。

示例 2:

输入:nums = [71, 60]
输出:1
解释:
共有一对同学,为 [71, 60]。
因为 71 + 6 = 17 + 60,此处 60 的镜像号码为 6,前导零被忽略。

提示:

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

思路分析

首先我们要先理解一下题意,最主要的就是这个公式:镜像号码 A + 原号码 B = 镜像号码 B + 原号码 A,我们需要在所有号码中找到所有符合这个公式的组合数。

首先数据的规模为:

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

因此我们不能直接暴力进行匹配,暴力的话我们需要进行双重遍历,时间复杂度为 10^6 * 10^6 = 10 ^ 12,这样很明显会超时,所以我们需要重新想想有没有其他更加简便的方法来解决这道题。

我们假设有两个数 ab,令镜像a = a + x,镜像b = b + y,将其代入公式镜像号码 A + 原号码 B = 镜像号码 B + 原号码 A,我们可以得到:a + x + b = b + y + a,化简可以得到x = y,也就是说要想等式成立,只需要x = y即可。

所以我们可以使用一个哈希表来记录每一个原号码与镜像号码之差x的数量,后面再对每一个x进行组合即可得出答案,具体步骤如下:

  • 1、获取号码的镜像
const getReverse = function(t){
    let temp = '';
    for(let j = t.length - 1; j >= 0; j--){
        temp += t[j];
    }
    return temp
};
  • 2、统计每一个镜像与原号码之差的数量
let map = new Map();
for(let i = 0; i < nums.length; i++){
    let temp = getReverse(nums[i] + '');
    temp = temp - nums[i];
    map.set(temp,(map.get(temp) || 0) + 1);
}
  • 3、计算组合数
let res = 0;
for(let key of map.keys()){
    let ind = map.get(key);
    res += ind * (ind - 1) / 2;
    res %= 10 ** 9 + 7;
}

完整代码如下:

AC代码

/**
 * @param {number[]} nums
 * @return {number}
 */
 var numberOfPairs = function(nums) {
    let map = new Map();
    const getReverse = function(t){
        let temp = '';
        for(let j = t.length - 1; j >= 0; j--){
            temp += t[j];
        }
        return temp
    };
    for(let i = 0; i < nums.length; i++){
        let temp = getReverse(nums[i] + '');
        temp = temp - nums[i];
        map.set(temp,(map.get(temp) || 0) + 1);
    }
    let res = 0;
    for(let key of map.keys()){
        let ind = map.get(key);
        res += ind * (ind - 1) / 2;
        res %= 10 ** 9 + 7;
    }
    return res;
};

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

目录
相关文章
|
6月前
读操作
读操作
36 0
|
6月前
|
编解码 计算机视觉
读、写视频
【5月更文挑战第7天】读、写视频。
46 2
|
6月前
读取数值
读取数值。
39 5
|
6月前
|
关系型数据库 MySQL 数据库
【mysql】当前读和快照读,幻读和可重复读
【mysql】当前读和快照读,幻读和可重复读
362 0
|
数据库
数据库事务——快照读与当前读
数据库事务——快照读与当前读
165 0
|
SQL Java 数据库
【事务与并发】- 不同事务读取相同数据问题
在加了事务的接口中,不同的业务或者是出现并发的时候,发现了一些SQL读取问题,两个都被事务包裹的方法,各自是隔离的,如果一方的事务延时提交,就会导致另一方读取出来的数据相同,并不是修改后的数据。
126 0
|
消息中间件 JavaScript 小程序
MySQL 底层之 MVCC、回滚段、一致性读、锁定读
MySQL 底层之 MVCC、回滚段、一致性读、锁定读
|
程序员
读《第一次把事情做对》有感
上班的时候,领导在群里发了一个 PDF 书籍《第一次把事情做对》,被这个书籍名称吸引住了,因为作为程序员每天有开发新任务,解决旧任务的 BUG,第一次就把事情做的完全正确几乎不可能呀,觉得很有看的必要,这个简单读了一下,跟大家分享一些文中要点。
118 0