【LeetCode】整数替换 Java 题解

2021 年 11 月 19 日
本文字数：752 字
阅读完需：约 2 分钟

题目描述

给定一个正整数 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/integer-replacement著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是整数替换题目，题干通俗易懂，简洁明了，需要求的最小替换次数。
这个题目很容易想到的思路就是枚举数值变换的每一种情况，然后比较求出最小的替换次数。常用的算法就是搜索 DFS。利用递归函数方便地实现暴力枚举的算法。该类搜索算法的特点在于，将要搜索的目标分成若干“层”，每层基于前几层的状态进行决策，直到达到目标状态。
根据题目，递归函数的终止条件是 n == 1,在这里比较最小的替换次数。对于每一层，分别按照 n 是偶数，或者 n 是基数，分条件讨论写出代码。具体实现代码如下：

通过代码

class Solution {    int ans = Integer.MAX_VALUE;
    public int integerReplacement(int n) {        int step = 0;        dfs(n, step);        return ans;    }
    public void dfs(long n, int step) {        if (n == 1) {            ans = Math.min(ans, step);            return;        }        if (n % 2 == 0) {            dfs(n / 2, step + 1);        } else {            dfs(n + 1, step + 1);            dfs(n - 1, step + 1);        }    }}