北京电子商务app网站建设大兴,深圳品牌策划公司排行,千里博客 wordpress,东莞推广优化公司2023每日刷题#xff08;五#xff09;
Leetcode—2530.执行K次操作后的最大分数 向上取整思想
参考了这篇文章 有人肯定会问#xff0c;这个向上取整为什么是这样来的。接下来我简单讲解一下。 数学式#xff1a; x y 数学式#xff1a;\frac{x}{y} 数学式#xff1a…2023每日刷题五
Leetcode—2530.执行K次操作后的最大分数 向上取整思想
参考了这篇文章 有人肯定会问这个向上取整为什么是这样来的。接下来我简单讲解一下。 数学式 x y 数学式\frac{x}{y} 数学式yx有以下两种情况
x能整除y则 x y \frac{x}{y} yx就是向上取整和向下取整结果一致的情况不需要额外转换。也就是说 x y \frac{x}{y} yx的向上取整和向下取整都是它本身例如 6 3 2 \frac{6}{3}2 362 6 3 \frac{6}{3} 36向下取整和向上取整结果都一样即为2x不能整除y则 x y \frac{x}{y} yx是向下取整结果不符合我们的需求。例如 5 2 2 \frac{5}{2}2 252,但是我们需要它的向上取整的值就不能直接用/。
解释一下 ( x y − 1 ) / y (x y - 1) / y (xy−1)/y
如果x能整除y那么 ( x y − 1 ) / y (x y - 1) / y (xy−1)/y的结果就等价于 x / y x / y x/y例如 6 3 2 \frac{6}{3}2 362如果x不能整除y那么 ( x y − 1 ) / y (x y - 1) / y (xy−1)/y结果就是向上取整的值。例如 x 5 , y 2 x5,y2 x5,y2,则 ( 5 2 − 1 ) / 2 3 (5 2 - 1) / 2 3 (52−1)/23即为 5 2 \frac{5}{2} 25向上取整的值。
你也可以这么理解
若x能整除y例如x2y,所以向上整除为2若x不能整除y例如x2y1也可以是 [ 2 y 1 , 3 y ) \left[2y1, 3y\right) [2y1,3y)所以 ( x y − 1 ) / y ( 2 y 1 y − 1 ) 3 (x y - 1) / y (2y 1 y - 1) 3 (xy−1)/y(2y1y−1)3
直接法实现代码
void max(int *nums, int numsSize, int *e) {int i 0;int max nums[0];int cnt 0;for(i 1; i numsSize; i) {if(max nums[i]) {max nums[i];cnt i;}}*e cnt;
}long long maxKelements(int* nums, int numsSize, int k){int i 0;long long ans 0;int cur 0;for(; i k; i) {max(nums, numsSize, cur);ans nums[cur];nums[cur] (nums[cur] 2) / 3;}return ans;
}测试结果 因为我的时间复杂度太大了即 O ( k n ) O(kn) O(kn)主要是也没要求时间复杂度啊。。。接下来用最大堆的方法做也就是大根堆
最大堆实现代码
void swap(int *a, int *b) {int tmp *a;*a *b;*b tmp;
}void downAdjustHeap(int* heap, int low, int high) {// 相当于双亲为i,左孩子为2*i1,右孩子为2*i2,因为这里数组从下标0开始int i low, j i * 2 1;while(j high) {if(j 1 high heap[j 1] heap[j]) {j j 1;}if(heap[j] heap[i]) {swap(heap[j], heap[i]);i j;j j * 2 1;} else {break;}}
}void createHeap(int* arr, int n) {// 建立大顶堆int i;for(i n / 2 - 1; i 0; i--) {downAdjustHeap(arr, i, n - 1);}
}long long maxKelements(int* nums, int numsSize, int k){// 建立大顶堆,即最大堆createHeap(nums, numsSize);long long ans 0;int i;for(i 0; i k; i) {ans nums[0];// 向上取整nums[0] (nums[0] 2) / 3;downAdjustHeap(nums, 0, numsSize - 1);}return ans;
}测试结果 之后我会持续更新如果喜欢我的文章请记得一键三连哦点赞关注收藏你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ↖(▔▽▔)↗感谢支持
