397 Integer Replacement

1. Question

Given a positive integernand you can do operations as follow:
  1. 1.
    If n is even, replace n withn/2.
  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: 时间复杂度?, 空间复杂度?