397. Integer Replacement

, ,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int integerReplacement(int n) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 0);
        return dfs(map, n);
    }

    private int dfs(Map<Integer, Integer> map, int n) {
        Integer replacement = map.get(n);
        if (replacement != null) {
            return replacement;
        }

        if ((n & 1) == 0) {
            replacement = 1 + dfs(map, n >>> 1);
        } else {
            replacement = 1 + Math.min(dfs(map, n + 1), dfs(map, n - 1));
        }

        map.put(n, replacement);
        return replacement;
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int integerReplacement(int n) {
        Map<Integer, Integer> cacheMap = new HashMap<>();

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        int steps = 0;

        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                int x = queue.poll();
                if (x == 1) {
                    return steps;
                }
                Integer replacement = cacheMap.get(x);
                if (replacement != null) {
                    continue;
                }
                cacheMap.put(x, steps);
                if ((x & 1) == 0) {
                    queue.offer(x >>> 1);
                } else {
                    queue.offer(x + 1);
                    queue.offer(x - 1);
                }
            }

            steps++;
        }

        return -1;
    }
}

Bit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int integerReplacement(int n) {
        int count = 0;
        while (n != 1) {
            if ((n & 1) == 0) {
                n >>>= 1; // 注意此处无符号右移，以处理 Integer.MAX_VALUE + 1 后溢出的情况
            } else {
                // n 为奇数，二进制表示中最低位为 1
                // 如果 +1，进位的效果取决于较低位是否为 1，如：01 -> 10, 11 -> 100
                // 如果 -1，则最低位的 bit 变为 0

                //  3: 011, 注意 3 为特例
                // +1: 100, 3 -> 4 -> 2 -> 1
                // -1: 010, 3 -> 2 -> 1

                if (n == 3) {
                    n--; // 此时 n 置为 2
                } else if ((n & 0b10) != 0) {
                    n++; // 此时 +1 可使 1 的个数减少
                } else {
                    n--; // 此时将最低位的 bit 变为 0
                }
            }
            count++;
        }

        return count;
    }
}

References

397. Integer Replacement