​LeetCode刷题实战397:整数替换

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 整数替换,我们先来看题面:
https://leetcode-cn.com/problems/integer-replacement/

Given a positive integer n, you can apply one of the following operations:

If n is even, replace n with n / 2.

If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

示例

给定一个正整数 n ,你可以做如下操作:

如果 n 是偶数,则用 n / 2替换 n 。
如果 n 是奇数,则可以用 n + 1或n - 1替换 n 。

n 变为 1 所需的最小替换次数是多少?

解题

解法:递归
当n==1时,return 0;
将int型的值传给m时,需要将m的类型申明为long long型。因为如果int 型的n为2147483647时,m=(n+1)/2的过程中n+1就会溢出。
int, long int都是4个字节的有符号数,最大值为2147483647.
可以将int型的实参传递给long long型的形参。

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

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文:

LeetCode1-380题汇总,希望对你有点帮助!

LeetCode刷题实战381:O(1) 时间插入、删除和获取随机元素

LeetCode刷题实战382:链表随机节点

LeetCode刷题实战383:赎金信

LeetCode刷题实战384:打乱数组

LeetCode刷题实战385:迷你语法分析器

LeetCode刷题实战386:字典序排数
LeetCode刷题实战387:字符串中的第一个唯一字符
LeetCode刷题实战388:文件的最长绝对路径
LeetCode刷题实战389:找不同
LeetCode刷题实战390:消除游戏
LeetCode刷题实战391:完美矩形
LeetCode刷题实战392:判断子序列
LeetCode刷题实战393:UTF-8 编码验证
LeetCode刷题实战394:字符串解码
LeetCode刷题实战395:至少有 K 个重复字符的最长子串
LeetCode刷题实战396:旋转函数
(0)

相关推荐