【leetcode】 397 integer replacement

发表于 | 分类于 ，

一个数 k 以 k / 2 , k - 1 , k + 1 替换，求等于 1 需要的次数


描述

给定一个正整数，进行如下操作：
若为偶数：除以2
若为奇数：可以选择 +1 或者 -1
问最小需要多少次操作可以等于 1

样例

样例1

1
2
输入: 7
输出: 4

样例2

1
2
输入: 8
输出: 3

思路

首先考虑深度优先搜索，遇到的第一个问题是 k + 1，这样的递归很难求解，设想一下，假如要求a [ 3 ] 首先要求得 a [ 4 ]，而 a [ 4 ] 又要 a [ 5 ] 求得，显然无法得到正确结果。于是想办法消去 k + 1，发现一个数 2 的幂因数多的有优势，比如 35 ，加 1 为 36，减 1 为 34,前者能分解出 2 个 2，后者只能分解出一个 2，所以此时需要选加 1 。但是又遇到了问题，假设要求的数是 3 ，按这种理论，4含有 2 个 2，2只含有 1 个 2 ，此刻会选择 4 ，结论很荒谬。所以还要加上判断较小的那个数是不是 2 的幂次方。但是这样一来会超时，计算一千万要很久。可以这样想，加了 1 还是要通过除以 2 才能继续缩小，何不将这一步加进去，也就是合并之前两个单独的步骤为 1 步。考虑减法，输入 3 减 1 除以 2 可以完成目标，所以减法和除法也可以合并成一个操作。做这道题开始考虑了用循环迭代做，发现需要迭代一千万次，也是很久很久的。考虑一下递归，好比有目的的求解，可以快上很多。

& 的优先级比 == 高，判断一个数是不是 2 的幂次方 (number&(number-1))==0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
private:
    map<int, int> visited;

public:
    int integerReplacement(int n) {
        if (n == 1) { return 0; }
        if (visited.count(n) == 0) {
            if (n & 1 == 1) {
                visited[n] = 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
            }
            else {
                visited[n] = 1 + integerReplacement(n / 2);
            }
        }
        return visited[n];
    }
};

参考

原题链接
参考代码