2652.倍数求和

倍数求和"/>

2652.倍数求和

2652. 倍数求和 - 力扣（LeetCode）

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

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

示例 1：

输入：n = 7
输出：21
解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21 。

示例 2：

输入：n = 10
输出：40
解释：在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40 。

示例 3：

输入：n = 9
输出：30
解释：在 [1, 9] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9 。数字之和为 30 。

提示：

• 1 <= n <= 103

思路解析

枚举，直接从一开始暴力求解

完整代码

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

思路

用的堆，主要思想是贪心，每次计算第i次就是第i次的分数除3，这个k≤105k \leq 10^5k≤105，意味着可以直接模拟。思路很明显，每次贪最大的数，而为了高效获得最大值，可以将所有数都放入到大根堆中。每次分数加上堆顶的元素，并弹出堆顶valvalval，将其变为ceil(val3)ceil(\frac{val}{3})ceil(3val​)后再放回堆中，以保持堆顶始终是最大值，重复这个过程kkk次即可。

完整代码

class Solution {public long maxKelements(int[] nums, int k) {PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b) -> b - a);for (int num : nums) {q.offer(num);}long ans = 0;for (int i = 0; i < k; ++i) {int x = q.poll();ans += x;q.offer((x + 2) / 3);}return ans;}
}