倍数求和"/>
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;}
}
更多推荐
2652.倍数求和
发布评论