这是 LeetCode 上的「397. 整数替换」,难度为「中等」。
Tag : 「DFS」、「BFS」、「贪心」
给定一个正整数 n
,你可以做如下操作:
n
是偶数,则用 n / 2
替换 n
。n
是奇数,则可以用 n + 1
或 n - 1
替换 n
。n
变为
所需的最小替换次数是多少?
示例 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
提示:
运用 DFS
进行求解。为防止重复处理某些数值,可以使用「哈希表」进行记忆化。
代码:
class Solution {
Map<Long, Integer> map = new HashMap<>();
public int integerReplacement(int n) {
return dfs(n * 1L);
}
int dfs(long n) {
if (n == 1) return 0;
if (map.containsKey(n)) return map.get(n);
int ans = n % 2 == 0 ? dfs(n / 2) : Math.min(dfs(n + 1), dfs(n - 1));
map.put(n, ++ans);
return ans;
}
}
同理,也可以使用 BFS
进行求解。同样使用「哈希表」记录步数,进行防止重复处理。
代码:
class Solution {
public int integerReplacement(int n) {
if (n == 1) return 0;
Map<Long, Integer> map = new HashMap<>();
Deque<Long> d = new ArrayDeque<>();
d.addLast(n * 1L);
map.put(n * 1L, 0);
while (!d.isEmpty()) {
long t = d.pollFirst();
int step = map.get(t);
long[] ns = t % 2 == 0 ? new long[]{t / 2} : new long[]{t + 1, t - 1};
for (long x : ns) {
if (x == 1) return step + 1;
if (!map.containsKey(x)) {
map.put(x, step + 1);
d.addLast(x);
}
}
}
return -1;
}
}
上述两种做法,我们不可避免地在每个回合枚举了所有我们可以做的决策:主要体现在对
为奇数时的处理,我们总是处理
和
两种情况。
我们可以从二进制的角度进行分析:给定起始值
,求解将其变为
的最小步数。
)而言,我们只能进行一种操作,其作用是将当前值
其进行一个单位的右移;
)而言,我们能够进行 +1
或 -1
操作,分析两种操作为
产生的影响:
+1
操作而言:最低位必然为 ,此时如果次低位为
的话, +1
相当于将最低位和次低位交换;如果次低位为
的话,+1
操作将将「从最低位开始,连续一段的
」进行消除(置零),并在连续一段的高一位添加一个
;
-1
操作而言:最低位必然为 ,其作用是将最低位的
进行消除。
因此,对于
为奇数所能执行的两种操作,+1
能够消除连续一段的
,只要次低位为
(存在连续段),应当优先使用 +1
操作,但需要注意边界
时的情况(此时选择 -1
操作)。
代码:
class Solution {
public int integerReplacement(int _n) {
long n = _n;
int ans = 0;
while (n != 1) {
if (n % 2 == 0) {
n >>= 1;
} else {
if (n != 3 && ((n >> 1) & 1) == 1) n++;
else n--;
}
ans++;
}
return ans;
}
}
这是我们「刷穿 LeetCode」系列文章的第 No.397
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。