力扣397. 整数替换

2024-04-11 18:16:01

力扣397. 整数替换

这是原题：
给定一个正整数 n ，你可以做如下操作：
如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
n 变为 1 所需的最小替换次数是多少？
同时还给出了三个示例：
示例 1：
输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1
示例 2：
输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1
示例 3：
输入：n = 4
输出：2

对于这道题，我个人觉得还是有点难度的。因为这个想法显得不是那么的好想，我记得之前有次面试题也大概是这种，但是意思是有一堆硬币，一次可以消耗一个或者两个，然后如果硬币数是二的倍数就可以花掉一半的硬币，如果是三的倍数就可以花掉三分之一的硬币，求最快消耗完这些硬币需要多少次？但是这个题目可能比今天的会更加难一些，反正我当时是没有写出来的。嘤嘤嘤~~

今天这个题目和我上面这个题目还是有很大程度的相同的，如果有兴趣的小伙伴也可以试一试哟。我们开始进入今天的题目

解法一：递归枚举

我们可以尽量的枚举出每一种可能出现的情况，然后对这些情况求出最小值。这段话显得非常的官方，反正我当时是听懵的，咋枚举啊，有的时候到底是加一还是减一,其实我当时简单的认为减一肯定没毛病，但是回头想想，比如15这个数吧，你就得加一，然后15->16->8->4->2->1，对吧，所以说这样的思维就难去编码，甚至难以有自己的想法！

所以这里，给出第一种思路——递归枚举
我们可以假设一个数：

如果这个数是1的话，那说明完成了任务，需要0步转化。
如果这个数是2的倍数的话，需要n/2这个数字的转化数加1。
如果这个数是不是1且不是2的倍数的话，那么我们可以认为这个数可以经过+1成为一个2的倍数再转化为(n+1)/2，或者我们可以认为这个数字经过-1成为一个2的倍数再转化为(n-1)/2注意：这里需要进行两步转化，因为加一或者减一需要一次转化，然后除以二有需要一次转化,转化之后我们取这个数加一或减一再除以二得到的数需要转化数的较小值。然后之后的数进行递归调用就好咯！我觉得这里可能会有点靓仔不是很理解，我把代码贴上就一目了然啦！

class Solution {
public:
    int integerReplacement(int n) {
        if(n==1) return 0;
        if(n%2==0) return 1+ integerReplacement(n/2);
        return 2+min(integerReplacement(n/2), integerReplacement(n/2+1));
    }
};

看完代码之后是不是显得明白了很多呢?

解法二：递归枚举+记忆化

解法二就是在解法一的基础上再加上了具有记忆化的功能。
我们怎么来实现记忆化呢？？？
我们可以通过哈希表来存储该数字对应的最小转化数，避免了一些重复计算

class Solution {
public:
    unordered_map<int,int> map;
    int integerReplacement(int n) {
        if(n==1) return 0;
        if(map.count(n)){
            return map[n];
            //因为我们得到的是每个数字的最小转化数，所以map里也是该数字对应的最小转化数
        }
        if(n%2==0) return map[n]=1+ integerReplacement(n/2);
        return map[n]=2+min(integerReplacement(n/2), integerReplacement(n/2+1));
    }
};

好了，希望大家可以有些收获吧，拜拜~

插一嘴：

还有一种方法是贪心，但是证明方法过于精妙，我就不弄出来了？
（因为我也没看懂！！！）

码农公寓