2652. 倍数求和

2652. 倍数求和

    • 题目
    • 方法-【枚举】 & 题目特征-【求计算在给定范围内满足某种条件的整数之和】
    • 方法-【容斥原理】 & 题目特征-【计算满足多个条件的元素之和,并且需要避免重复计数】

题目

题目链接:https://leetcode.cn/problems/sum-multiples/description/

给你一个正整数 n ,请你计算在 [1,n] 范围内能被 3、5、7 整除的所有整数之和。

返回一个整数,用于表示给定范围内所有满足约束条件的数字之和。

方法-【枚举】 & 题目特征-【求计算在给定范围内满足某种条件的整数之和】

class Solution {
public:int sumOfMultiples(int n) {int sum = 0;for (int i = 1; i <= n; i++) if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) sum += i;return sum;}
};

方法-【容斥原理】 & 题目特征-【计算满足多个条件的元素之和,并且需要避免重复计数】

举个例子,当我们想要计算一共有多少只动物,但有些动物同时属于几个类别,我们可以使用容斥原理。

假设我们有三个类别的动物:猫、狗和兔子,并且我们有以下信息:

  • 喜欢猫的人数10
  • 喜欢狗的人数15
  • 喜欢兔子的人数8

我们想要找到同时喜欢三种动物的人数。

如果我们简单地将每个类别的动物数量相加,我们会得到10 + 15 + 8 = 33只动物。但这样计算会有重复计数的问题,因为有些动物同时属于多个类别。

为了避免重复计数,我们可以使用容斥原理。根据容斥原理,我们需要:

  • 将每个类别的动物数量相加;
  • 减去同时属于两个类别的动物数量;
  • 加上同时属于三个类别的动物数量。

因此,我们可以计算:10 + 15 + 8 - (猫 & 狗的数量) - (狗 & 兔子的数量) - (猫 & 狗 & 兔子的数量) = 1只动物。

通过应用容斥原理,我们得到了正确的结果,即一共有1只动物,避免了重复计数的问题。

这个题目和答案是乱写的,主要看题目特征和方法的匹配 — 之所以使用 xx方法(容斥原理),是因为题目有 xx 特征。

在 2652 这题:

  • 集合 A:能被 2 整除的数;
  • 集合 B:能被 3 整除的数;
  • 集合 C:能被 5 整除的数。

我们希望计算在给定范围内满足这些条件的数的总数,同时避免重复计数。

那我们需要容斥原理才能做到全面完整、不重不漏的计数。

具体看官网题解:

f(n, m) 表示在区间 [1, n] 内能被 m 整除的整数之和。

f(n, m) 函数计算方法:

class Solution {
private: int f(int n, int k){int cnt = n / k;                  // cnt * k 为小于等于n的最大数字return (k + cnt * k) * cnt / 2;   // 等差数列求和公式}
public:int sumOfMultiples(int n) {return f(n, 3) + f(n, 5) + f(n, 7) - f(n, 3*5) - f(n, 3 * 7) - f(n,5*7) + f(n, 3 * 5 * 7);}
};

或者

class Solution {
public:int sumOfMultiples(int n) {int sum = 0;int div3 = n / 3;int div5 = n / 5;int div7 = n / 7;int div15 = n / 15;int div21 = n / 21;int div35 = n / 35;int div105 = n / 105;sum = 3 * div3 * (div3 + 1) / 2+ 5 * div5 * (div5 + 1) / 2+ 7 * div7 * (div7 + 1) / 2- 15 * div15 * (div15 + 1) / 2- 21 * div21 * (div21 + 1) / 2- 35 * div35 * (div35 + 1) / 2+ 105 * div105 * (div105 + 1) / 2;return sum;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/160506.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Idea集成Docker

1、前言 上一节中&#xff0c;我们介绍了Dockerfile的方式构建自己的镜像。但是在实际开发过程中&#xff0c;一般都会和开发工具直接集成&#xff0c;如Idea。今天就介绍下idea和Docker如何集成。 2、开启docker远程 要集成之前&#xff0c;需要我们本机能够访问docker服务…

每日一题 2652. 倍数求和(简单)

最简单的做法&#xff0c;遍历求和&#xff0c;时间O(n) class Solution:def sumOfMultiples(self, n: int) -> int:return sum([i if (i % 3 0) or (i % 5 0) or (i % 7 0) else 0 for i in range(n 1)])如果只求在 [1,n] 内能被m整除的数之和&#xff0c;那么 ans (…

[MQ]Win平台RocketMQ安装启动

1、下载 官网下载地址&#xff1a;https://rocketmq.apache.org/zh/download 2、解压ZIP包 解压rocketmq-all-x.x.x-bin-release.zip到目录。 比如我解压到了E:\Env\MQ_rocket\rocketmq-all-5.1.4-bin-release 3、配置环境变量 ROCKETMQ_HOME 4、RocketMQ JVM内存配置 这个需要…

3dmax中的 (Corona 9)cr渲染器怎么渲染?cr渲染器使用教程

Corona 9渲染器在3ds Max和Cinema 4D中应用广泛&#xff0c;是一款高效且功能强大的渲染器&#xff0c;得到了许多用户的好评。 Corona 9有以下几个主要的特点&#xff1a; 出色的渲染速度&#xff1a;Corona 9被证明是一个快速且高效的渲染引擎&#xff0c;它能够在保证高质…

虹科 | 解决方案 | 虹科Pico振动异响(NVH)诊断方案

车辆行驶过程中的偶发性异响&#xff08;比如经过颠簸路面时的吱嘎声&#xff09;和某一特定车速/转速下持续/周期性出现的异响&#xff0c;要将故障重现并定位故障点&#xff0c;对维持技师来讲是个重大的挑战。传统的测试方法是使用底盘听诊器&#xff0c;车辆一边在路上跑&a…

一文带你认识高速低侧栅极驱动器 FAN3111ESX 带你深入了解其特点及应用

FAN3111ESX一款低端驱动器产品&#xff0c;是外部 DC 2 至 5 V 参考输入、单通道同相输出、1.4 A 峰值灌电流、1.4 A 源电流低端栅极驱动器。 FAN3111ESX 1A栅极驱动器为驱动一个在低侧开关应用中的 N沟道增强型 MOSFET 而设计。 对于使用低压控制器和其它和驱动器相比使用更…

云计算是什么?学习云计算能做什么工作?

很多人经常会问云计算是什么&#xff1f;云计算能干什么&#xff1f;学习云计算能做什么工作&#xff1f;其实我们有很多人并不知道云计算是什么&#xff0c;小知今天来给大家讲讲学习云计算能做什么。 中国的云计算行业目前正处于快速发展阶段&#xff0c;随着互联网和数字化…

JMeter连接数据库

一. 下载数据库驱动jar包 https://jdbc.postgresql.org/download/ 二. 将数据库驱动放到jmeter的lib目录下 三. 在jmeter中引用这个jar包 四. 添加一个jdbc数据库连接配置 五. 添加一个jdbc request来查询sql并将查询结果赋值给一个变量 六. 将查询结果用于其他请求

防雷接地的作用和施工案例方案

防雷接地是一种防止雷电对建筑物、设备和人员造成危害的措施&#xff0c;它通过将建筑物或设备的金属部件与大地电位相连&#xff0c;使雷电流能够安全地泄放到地下&#xff0c;从而避免电击、火灾、爆炸等事故的发生。 地凯科技防雷接地系统一般由三个部分组成&#xff1a;接…

基于Java的教学评价管理系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09; 代码参考数据库参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&am…

一个标准的异常枚举类可以如何定义

一个标准的异常枚举类可以如何定义&#xff1f; 首先&#xff0c;使用enum关键字定义一个枚举类型。在枚举类型中&#xff0c;定义各种异常类型&#xff0c;每个异常类型用一个枚举常量表示。为每个异常类型添加一个构造方法&#xff0c;用于初始化异常类型的信息。可以为异常…

python 之enumerate()函数

文章目录 enumerate() 是 Python 中的一个内置函数&#xff0c;它用于在遍历可迭代对象&#xff08;如列表、元组、字符串等&#xff09;时同时获取每个元素的索引和值。这个函数非常有用&#xff0c;因为它允许您在迭代过程中轻松地访问元素的索引&#xff0c;而不需要手动维护…

linux centos7提示 cannot found font installed on the system.calibri

主图 目录 1.问题描述2.问题解决2.1安装Microsoft Core Fonts2.2手动安装字体文件&#xff1a;2.3查看当前系统基本型细腻 总结参考 文章所属专区 超链接 1.问题描述 linux centos7提示 cannot found font installed on the system.calibri &#xff0c;linux系统找不到cali…

Adobe Premiere Pro 和 After Effects 安装出错的解决路径

在有点年头的电脑上安装Premiere Pro 和 After Effects 遇到了前所未有的的麻烦&#xff0c;请了某宝上的小哥进行远程安装&#xff0c;两个软件倒是可以用了&#xff0c;但Win11系统无法正常关机&#xff0c;用了几天系统除了关机时会蓝屏几十秒&#xff0c;其他没有发现毛病&…

node多版本管理器nvm

node多版本管理器nvm 1、为何要使用node版本管理器2、nvm安装步骤2-1、卸载系统中的node2-2、下载nvm2-3、安装 3、维护node版本3-1、安装指定版本node3-2、查看本机已安装的所有node版本3-3、切换本机node版本 1、为何要使用node版本管理器 在日常开发中&#xff0c;难免会遇…

云服务器ip使用细节(公网、私有)

场景&#xff1a; 当我们对tcp服务器进行监听的时候&#xff0c;可能需要用到ip地址&#xff0c;比如使用httplib::Service::listen(ip, port)&#xff0c;而当我们访问tcp服务器时也需要ip地址 但这两个ip是不同的&#xff01; 每个云服务器通常都会有一个公网IP地址和一个私有…

Go语言入门心法(六): HTTP面向客户端|服务端编程

Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一:go语言面向web编程认知 Go语言的最大优势在于并发与性能,其性能可以媲美C和C,并发在网络编程中更是至关重要 使用http发送请…

Git 速通以及常用指令!!

参考视频 01 - Git - 教程简介_哔哩哔哩_bilibili 在需要使用git的文件夹打开git bash&#xff0c;指令如下↓ 当然图形化界面也很香&#xff01;github desktop也很舒服&#xff01; 查看文件 版本号 git cat-file -p 版本号 仓库操作 在当前文件夹下创建git仓库 git ini…

使用Proxyman抓取Android的https请求

使用Proxyman抓取Android的https请求 有时&#xff0c;您可能需要测试您的移动应用程序并检查与其关联的所有网络请求。在网络上&#xff0c;此任务非常简单&#xff0c;只需按Ctrl Shift I打开开发人员工具即可。从那里&#xff0c;您可以导航到网络选项卡并检查与网页相关的…

【黑马程序员】机器学习

&#xff08;一&#xff09;机器学习概述 一、机器学习算法分类 1、监督学习&#xff1a; &#xff08;1&#xff09;目标值是类别&#xff1a;分类问题 k-近邻算法、贝叶斯分类、决策树与随机森林、逻辑回归 &#xff08;2&#xff09;目标值是连续型的数据&#xff1a;回归…