LeetCode 3153.所有数对中数位差之和:计数
【LetMeFly】3153.所有数对中数位差之和:计数
力扣题目链接:https://leetcode.cn/problems/sum-of-digit-differences-of-all-pairs/
车尔尼有一个数组 nums ,它只包含 正 整数,所有正整数的数位长度都 相同 。
两个整数的 数位不同 指的是两个整数 相同 位置上不同数字的数目。
请车尔尼返回 nums 中 所有 整数对里,数位不同之和。
示例 1:
输入:nums = [13,23,12]
输出:4
解释:
计算过程如下:
- 13 和 23 的数位不同为 1 。
- 13 和 12 的数位不同为 1 。
- 23 和 12 的数位不同为 2 。
所以所有整数数对的数位不同之和为 1 + 1 + 2 = 4 。
示例 2:
输入:nums = [10,10,10,10]
输出:0
解释:
数组中所有整数都相同,所以所有整数数对的数位不同之和为 0 。
提示:
2 <= nums.length <= 1051 <= nums[i] < 109nums中的整数都有相同的数位长度。
解题方法:计数
首先需要明确每一位互不干扰,因此每一位分开计算,然后加起来就好了。
对于每个数的每一位,假设有3个0、2个1和4个2,那么“不同数字的数目”是什么呢?
不同数字的数目为 3 × ( 2 + 4 ) + 2 × ( 3 + 4 ) + 4 × ( 3 + 2 ) = 3 × ( 9 − 3 ) + 2 × ( 9 − 2 ) + 4 × ( 9 − 4 ) 3\times(2+4)+2\times(3+4)+4\times(3+2) = 3\times(9-3)+2\times(9-2)+4\times(9-4) 3×(2+4)+2×(3+4)+4×(3+2)=3×(9−3)+2×(9−2)+4×(9−4)。
也就是说,统计一下每个数字出现的次数就好了。
- 时间复杂度 O ( n log M ) O(n\log M) O(nlogM),其中 M M M是每个数的最大范围
- 空间复杂度 O ( C ) O(C) O(C),其中 C = 10 C=10 C=10
AC代码
C++
typedef long long ll;
class Solution {
public:ll sumDigitDifferences(vector<int>& nums) {ll ans = 0;do {ll times[10] = {0};for (int& t : nums) {times[t % 10]++;t /= 10;}for (int i = 0; i < 10; i++) {ans += times[i] * (nums.size() - times[i]);}} while (nums[0]);return ans / 2;}
};
Go
package mainfunc sumDigitDifferences(nums []int) int64 {ans := int64(0)for nums[0] > 0 {times := make([]int, 10)for i, n := range nums {times[n % 10]++nums[i] /= 10}for i := 0; i < 10; i++ {ans += int64(times[i] * (len(nums) - times[i]))}}return ans / 2
}
Java
class Solution {public long sumDigitDifferences(int[] nums) {long ans = 0;while (nums[0] > 0) {long[] times = new long[10];for (int i = 0; i < nums.length; i++) {times[nums[i] % 10]++;nums[i] /= 10;}for (int i = 0; i < 10; i++) {ans += times[i] * (nums.length - times[i]);}}return ans / 2;}
}
Python
from typing import Listclass Solution:def sumDigitDifferences(self, nums: List[int]) -> int:ans = 0n = max(nums)while n: # while nums[0]的话可能会有[0, 1]的情况 # 后续更新:忽然发现题目限定是正数,有点过考虑了n //= 10times = [0] * 10for th, x in enumerate(nums):times[x % 10] += 1nums[th] //= 10for i in range(10):ans += times[i] * (len(nums) - times[i])return ans // 2
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/141729979
相关文章:
LeetCode 3153.所有数对中数位差之和:计数
【LetMeFly】3153.所有数对中数位差之和:计数 力扣题目链接:https://leetcode.cn/problems/sum-of-digit-differences-of-all-pairs/ 车尔尼有一个数组 nums ,它只包含 正 整数,所有正整数的数位长度都 相同 。 两个整数的 数位…...
Spring Boot 整合 Sentinel 实现流量控制
在微服务架构中,流量控制是保障系统稳定性和高可用性的关键技术之一。阿里巴巴开源的 Sentinel 是一款面向分布式系统的流量防护组件,旨在从流量控制、熔断降级、系统负载保护等多个维度保障服务的稳定性。本文将详细介绍如何在 Spring Boot 项目中整合 …...
Elasticsearch倒排索引
什么是倒排索引 倒排索引(Inverted Index)是一种将文档中的每个单词映射到包含该单词的文档列表上的数据结构 倒排索引的构建过程 文档1: “我爱吃苹果” 文档2: “我爱吃香蕉” 文档3: “我喜欢苹果和香蕉” 文档分词:将文档中的文本内容…...
速盾:ddos常用防御方法是什么?
DDoS攻击是一种通过向网络资源发送大量请求或大流量数据来使其过载的攻击手段。为了应对这种攻击,常用的防御方法可以分为三个层次:流量清洗、服务器升级和高防CDN。 流量清洗是一种基础的防御手段,它通过过滤和识别恶意流量来阻止DDoS攻击。…...
二分算法入门(简单题)
习题1 704. 二分查找 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], targ…...
在使用React Hooks中,如何避免状态更新时的性能问题?
在React Hooks中避免状态更新时的性能问题,可以采取以下一些最佳实践: 避免不必要的状态更新: 使用React.memo、useMemo、和useCallback来避免组件或其子组件进行不必要的渲染。 使用useMemo: 对于基于状态或props的复杂计算&…...
Pytest插件pytest-selenium-让自动化测试更简洁
在现代Web应用的开发中,自动化测试成为确保网站质量的重要手段之一。而Pytest插件 pytest-selenium 则为开发者提供了简单而强大的工具,以便于使用Python进行Web应用的自动化测试。本文将深入介绍 pytest-selenium 插件的基本用法和实际案例,…...
视觉语言模型(VLMs)知多少?
最近这几年,自然语言处理和计算机视觉这两大领域真是突飞猛进,让机器不仅能看懂文字,还能理解图片。这两个领域的结合,催生了视觉语言模型,也就是Vision language models (VLMs) ,它们能同时处理视觉信息和…...
重新修改 Qt 项目的 Kit 配置
要重新修改 Qt 项目的 Kit 配置,你可以按照以下步骤进行操作: 1. 打开 Qt Creator 首先,启动 Qt Creator,确保你的项目已经打开。 2. 进入项目设置 在 Qt Creator 中,点击菜单栏的 “Projects” 标签(通…...
【Spring Boot 3】【Web】自定义响应状态码
【Spring Boot 3】【Web】自定义响应状态码 背景介绍开发环境开发步骤及源码工程目录结构背景 软件开发是一门实践性科学,对大多数人来说,学习一种新技术不是一开始就去深究其原理,而是先从做出一个可工作的DEMO入手。但在我个人学习和工作经历中,每次学习新技术总是要花费…...
Locksupport凭证的底层原理
LockSupport的凭证(通常称为“许可”或“permit”)的底层原理主要涉及到Java的Unsafe类以及系统级的线程同步机制。LockSupport是Java 6(JSR166-JUC)引入的一个类,提供了基本的线程同步原语,其核心功能是通…...
Elasticsearch 再次开源
作者:来自 Elastic Shay Banon [D.N.A] Elasticsearch 和 Kibana 可以再次被称为开源了。很难表达这句话让我有多高兴。我真的激动得跳了起来。Elastic 的所有人都是这样的。开源已经融入我的 DNA,也融入了 Elastic 的 DNA。能够再次将 Elasticsearch 称…...
对称密码学
1. 使用OpenSSL 命令行 在 Ubuntu Linux Distribution (发行版)中, OpenSSL 通常可用。当然,如果不可用的话,也可以使用下以下命令安装 OpenSSL: $ sudo apt-get install openssl 安装完后可以使用以下命令检查 OpenSSL 版本&am…...
正则表达式优化建议
文章目录 优化正则表达式代码示例:注意事项: 一些常见的正则表达式陷阱 优化正则表达式是提高文本处理效率和准确性的重要步骤。以下是一些优化正则表达式的方法: 以下是整理归纳后的正则表达式优化技巧: 优化正则表达式 一、预…...
Oracle RAC关于多节点访问同一个数据的过程
一、说明 Oracle RAC 存在多个计算节点,但是使用的共享存储。那么多个节点共同访问同一个资源,怎么保证一致性。 白文的逻辑理解简述: 用户1访问rac1 ,通过rac1获取AA数据块后,会加上latch锁。用户2通过rac2访问AA数据…...
IPC$漏洞多位密码爆破方法
虽然不应该将其用于非法的密码破解行为,但从代码修改角度来说,如果要破解多位密码(比如 n 位),你可以按照以下方式调整: 破解多位纯数字密码 如果你想破解 6 位纯数字密码: FOR /L %%i IN (100000,1,999999) DO (net use \\target - ip\ipc$ /user:weak %%i &&…...
计算机网络(八股文)
这里写目录标题 计算机网络一、网络分层模型1. TCP/IP四层架构和OSI七层架构⭐️⭐️⭐️⭐️⭐️2. 为什么网络要分层?⭐️⭐️⭐️3. 各层都有那些协议?⭐️⭐️⭐️⭐️ 二、HTTP【重要】1. http状态码?⭐️⭐️⭐️2. 从输入URL到页面展示…...
Docker打包镜像
Docker打包镜像 前置工作 1.虚拟机中配置好docker环境,并导入nginx,mysql,jdk的镜像 2.下载docker for windows 用idea打包镜像和创建容器需要这个东西支持 下载安装包后执行,无脑回车即可 3.idea中配置docker连接 完成配置后&…...
RabbitMQ 基础架构流程 数据隔离 创建用户
介绍 publisher:消息发送者-exchange:交换机,复制路由的消息-queue:队列,存储消息consumer:消息的消费者 工作流程 publisher消息发送者 -> exchange 交换机 -> queue 队列 -> consumer 消息的消…...
win10系统下openssl证书生成和单向认证
文章目录 前言一、安装openssl二、创建证书目录和必要文件1、创建sslcertTest文件夹2、创建openssl.cnf文件3、创建必要文件 三、创建密钥和证书1、创建根证书私钥ca.key2、创建根证书请求文件ca.csr3、创建自签根证书ca.crt4、创建服务端私钥server.key5、创建服务端证书请求文…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
