397 Integer Replacement

Search…

397. Integer Replacement​
1. Question
Given a positive integernand you can do operations as follow:
1.If n is even, replace n withn/2.
2.If n is odd, you can replace n with eithern+ 1orn- 1.
What is the minimum number of replacements needed fornto become 1?
Example 1:
1
Input:
2
8
3
​
4
Output:
5
3
6
​
7
Explanation:
8
8 ->4 ->2 ->1
Copied!
Example 2:
1
Input:
2
​
3
7
4
​
5
​
6
Output:
7
​
8
4
9
​
10
​
11
Explanation:
12
​
13
7 ->8 ->4 ->2 ->1
14
or
15
7 ->6 ->3 ->2 ->1
Copied!
2. Implementation
(1) BFS
1
class Solution {
2
    public int integerReplacement(int n) {
3
        Queue<Long> queue = new LinkedList<>();
4
        Set<Long> visited = new HashSet<>();
5
​
6
        queue.add((long)n);
7
        visited.add((long)n);
8
        int level = 0;
9
​
10
        while (!queue.isEmpty()) {
11
            int size = queue.size();
12
​
13
            for (int i = 0; i < size; i++) {
14
                long curNum = queue.remove();
15
​
16
                if (curNum == 1) {
17
                    return level;
18
                }
19
​
20
                if (curNum % 2 == 0 && !visited.contains(curNum / 2)) {
21
                    queue.add(curNum / 2);
22
                    visited.add(curNum / 2);
23
                }
24
                else {
25
                    if (!visited.contains(curNum + 1)) {
26
                        queue.add(curNum + 1);
27
                        visited.add(curNum + 1);
28
                    }
29
​
30
                    if (!visited.contains(curNum - 1)) {
31
                        queue.add(curNum - 1);
32
                        visited.add(curNum - 1);
33
                    }
34
                }
35
​
36
            }
37
            ++level;
38
        }
39
        return -1;
40
    }
41
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度?, 空间复杂度?

317 Shortest Distance from All Buildings

407 Trapping Rain Water II

Last modified 2yr ago

Copy link

Contents

397. Integer Replacement

1. Question

2. Implementation

3. Time & Space Complexity

397. Integer Replacement​

1. Question

2. Implementation

3. Time & Space Complexity

397. Integer Replacement