专栏首页用户6093955的专栏leetcode1558题解【贪心】

leetcode1558题解【贪心】

leetcode1558.得到目标数组的最少函数调用次数

题目链接

算法

贪心

时间复杂度O(nlogN)N为数组中最大的那个数。

1.题意就是给定一个函数,该函数有两种功能,一种就是将数组中的所有数同乘以2,另一种就是将数组中的某个数加1。给定一个数组nums,让你将初始值全为0的数组arr通过调用给定的函数来变成nums。问最少调用次数。

2.刚开始模拟了一番,但因为考虑的方法不对(至于哪里不对呢,就是一开始我就把数组的值都加1了一遍,然后再同乘以2,最后再一个个补1,这么做显然不利于减少次数。至于当时为啥这么想,估计是脑子抽了),最终无果。

3.接下来步入正题,我们可以这么想。当初始值都为0时,我们可以使部分值首先加1(即最终要变成的较大的值),让它们首先乘以2,不断乘,乘到一定程度再处理。但这么做有个问题,让哪部分值先变成1呢?还有就是乘到哪种程度呢?

这个地方的确是个难点,不太容易想。如果直接模拟的话不太容易。

数组中谁乘2的次数最多,当然是目标值最大的那个数乘的次数最多,其他目标值较小的就相对来说乘的次数较少。我们可以贪心地让那些乘的次数较少的包含在乘的次数最多里面,至于它具体是怎么乘的,我们不用考虑太多,这就是贪心算法的好处。

如何计算每个数最终乘的次数,我们可以分情况讨论:

为了方便,我们可以从目标值向初始值变化。

  • 对于奇数,可以先让其变为偶数(变为偶数这个过程即减1,这个需要单独记录),然后再除2,每除一次就记录一次。
  • 对于偶数,就除2,每除一次就记录一次。可能除着除着就变成奇数了,比如250,这时候就执行上一步。

最终,数组中的值就都变成0了。

4.总之,这道题的基本思路就是求出目标数组中最大值变成0需要除2的次数,以及该数组中每个数需要减1的次数(什么时候减,就是为奇数的时候减),二者相加即为答案。

C++代码

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int len = nums.size();
        int res = 0;
        int mx = 0;     //记录乘以2的最大次数
        for(int i = 0; i < len; i++){
            int cnt = 0;
            while(nums[i]){
                if(nums[i] % 2 == 1){
                    nums[i] -= 1;      //把它变成偶数
                    res++;
                }
                if(nums[i] > 0){
                    nums[i] /= 2;
                    ++cnt;
                }
            }
            mx = max(mx, cnt);
        }
        res += mx;
        return res;
    }
};

思路来源

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【lower_bound、upperbound讲解、二分查找、最长上升子序列(LIS)模版】

    注意此模板只适用于查找a中是否存在v,存在的话则返回其中一个符合条件的位置,并不一定只有那一个位置,这个视情况而定。

    _DIY
  • CF: Long Number

    分析1:题目原文中有这么一句“You can perform the following operation no more than once: choose...

    _DIY
  • 蓝桥杯突击复习准备——部分算法汇总

    当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 II (AC代码,思路在代码中)

    _DIY
  • 剑指Offer LeetCode 面试题39. 数组中出现次数超过一半的数字

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-sh...

    TrueDei
  • 0631-6.2-如何确认一个Parquet文件是否被压缩

    1.使用Hive的desc命令查看Parquet表hive_table_test_parquet的底层文件格式是否被压缩。

    Fayson
  • 二分查找总结

    二分查找是在每次匹配后,将查找的空间一分为二的算法,二分查找应该是有序的数组进行查找.

    黑白格
  • Leetcode: Repeated DNA Sequences

    All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, fo...

    卡尔曼和玻尔兹曼谁曼
  • Shell 中的中括号用法总结

    需要注意的是 [ 与 ] 与操作数之间一定要有一个空格,否则会报错。比如下面这样就会报错:

    编程范 源代码公司
  • spring-boot-plus1.1.0发布-集成Spring Boot Admin管理和监控应用

    geekidea
  • 用Spring Boot Admin来监控我们的微服务

    【转载请注明出处】:https://blog.csdn.net/huahao1989/article/details/108039738

    后端老鸟

扫码关注云+社区

领取腾讯云代金券