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

今天和大家聊的问题叫做 整数替换，我们先来看题面：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));
        }
    }
};

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