[数据结构与算法]leetcode每日一题-397:整数替换

leetcode每日一题-397:整数替换

链接

整数替换

题目

分析

直接dfs枚举所有情况即可。

代码

C++

class Solution {
public:
    
    int res = INT_MAX;

    int integerReplacement(int n) {
        dfs(n, 0);
        return res;
    }

    // 这里用longlong是因为INT_MAX+1会爆int
    void dfs(long long  n, int deep)
    { 
        if(n == 1)
        {
            res = min(res, deep);
            return ;
        }

        if(n % 2 == 0)
        {
            dfs(n / 2, deep + 1);
        }
        else
        {
            dfs(n + 1, deep + 1);

            dfs(n - 1, deep + 1);
        }
    }
};

Java

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

作者：LeetCode-Solution