首页 > 编程语言 >算法学习每日一题数位不同的组合

算法学习每日一题数位不同的组合

时间:2024-09-01 08:54:22浏览次数:9  
标签:组合 nums int 元素 long 算法 ans 数位

Problem: 3153. 所有数对中数位不同之和

思路

本题关键在于如何处理数位不同的个数,其实就是组合问题,两个不同数字的不同数位只能算一对,所以我们不妨把后方元素与前方元素数位不同算作一对,保持单调性避免重复计数。

那么后方元素不同的数位应该如何统计呢,我们不妨使用哈希表,一维表示统计的数位位数,二维表示数位0~9。

某一数位位数下数位与前方元素不同的个数,就是当前遍历到的所有元素数目 - 该数位相同的元素个数(存储在哈希表中)。

Code

class Solution {
public:
    long long sumDigitDifferences(vector<int>& nums) {
        long long ans = 0;
        vector<vector<int>> cnt(to_string(nums[0]).length(), vector<int>(10));
        for(int k = 0; k < nums.size(); k++)
        {
            int x = nums[k];
            for(int i = 0; x; x /= 10, i++)
            {
                ans += k - cnt[i][x % 10]++;
            }
        }
        return ans;
    }
};

标签:组合,nums,int,元素,long,算法,ans,数位
From: https://blog.csdn.net/2302_77423323/article/details/141713722

相关文章

  • 【数模资料包】最新数模国赛word+latex模版|数模常用的算法python+matlab代码
     【2024最全国赛研赛数模资料包】C君珍贵国一数模资料|最新数模国赛word+latex模版|数模常用的算法python+matlab代码国赛指:高教社杯全国大学生数学建模竞赛,研赛指:华为杯研究生数学建模竞赛。资料内容具体看文末卡片以下是三个相关的资料内容:1C君珍贵国一数模资料2最......
  • 双指针算法详解
      我的主页:2的n次方_       1.双指针算法双指针算法是一种在数组或字符串中常用且高效的算法技术,它通过维护两个指针(或索引)来遍历数据结构,从而解决某些问题。这种算法能够减少不必要的重复遍历,降低时间复杂度,并且往往能够使得代码更加简洁易懂。根据指针......
  • 代码随想录算法day5 - 哈希表1
    题目1242.有效的字母异位词给定两个字符串*s*和*t*,编写一个函数来判断*t*是否是*s*的字母异位词。字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语,通常只使用所有原始字母一次。示例1:输入:s="anagram",t="nagaram"输出:true示例2:......
  • 手把手教你使用C语言实现堆栈数据结构算法-两种方式(链表+数组)
    堆栈定义栈(stack)是一种遵循先入后出逻辑的线性数据结构,常见操作入栈,出栈,访问栈图片来源:https://www.hello-algo.com/栈的实现栈遵循先入后出的原则,因此我们只能在栈顶添加或删除元素。然而,数组和链表都可以在任意位置添加和删除元素,因此栈可以视为一种受限制的数组或链表......
  • python实现椭圆曲线加密算法(ECC)
    目录椭圆曲线加密算法(ECC)简介ECC的数学基础椭圆曲线的定义ECC的基本操作ECC加密和解密流程Python面向对象实现ECC加密和解密代码解释场景应用:安全通信总结椭圆曲线加密算法(ECC)简介椭圆曲线加密算法(EllipticCurveCryptography,ECC)是一种基于椭圆曲线数学结构的......
  • python实现数字签名算法 (DSA)
    目录数字签名算法(DSA)介绍DSA的数学基础DSA签名生成和验证流程Python面向对象实现DSA签名和验证代码解释场景应用:电子合同签署总结数字签名算法(DSA)介绍数字签名算法(DigitalSignatureAlgorithm,DSA)是一种基于公钥加密的数字签名标准。它被广泛用......
  • 「代码随想录算法训练营」第五十天 | 图论 part8
    目录拓扑排序题目:117.软件构建dijkstra(朴素版)题目:47.参加科学大会dijkstra算法和prim算法的区别dijkstra(堆优化版)题目:47.参加科学大会拓扑排序拓扑排序概括来说就是给出一个有向无环图,把这个有向无环图转成线性的排序,就叫拓扑排序。使用广度优先搜索(BFS)即可。如上图,当我们......
  • 代码随想录算法训练营,8月31日 | 24. 两两交换链表中的节点,19.删除链表的倒数第N个节点
    24.两两交换链表中的节点题目链接:24.两两交换链表中的节点文档讲解︰代码随想录(programmercarl.com)视频讲解︰两两交换链表中的节点日期:2024-08-31做前思路:用上虚拟头指针,从头开始,先指向2再到1,再到3,但要注意保留原本的结点。Java代码如下:classSolution{publicListN......
  • 分享一个js 抢红包随机算法,其他语言思路也一样
    直接调用这个方法就行传递q(金额)和r(人数就行)保证人均最少一分钱当剩余金额大于80%的时候,会在金额20%的区间内取大红包随机分配;基础分配规则为,按照每人可以随机5次的要求,得出每次随机的金额,随机分给其中一人functionfen(q,r){//q=红包金额单位元,最小0.01r=分配人数if......
  • 基于分解的多目标进化算法MOEA/D
    本文基于MOEA/D论文进行部分翻译、解释,是学习笔记的一部分。结构和原文完全相同,大家可以用于辅助阅读论文。如有错误,欢迎指出,感谢!原文:MOEA/D:AMultiobjectiveEvolutionaryAlgorithmBasedonDecomposition. QingfuZhang,SeniorMember,IEEE,andHuiLiAbstract......