397 Integer Replacement
397. Integer Replacement
1. Question
Given a positive integernand you can do operations as follow:
If n is even, replace n with
n/2
.If n is odd, you can replace n with either
n+ 1
orn- 1
.
What is the minimum number of replacements needed fornto become 1?
Example 1:
Input:
8
Output:
3
Explanation:
8 ->4 ->2 ->1
Example 2:
Input:
7
Output:
4
Explanation:
7 ->8 ->4 ->2 ->1
or
7 ->6 ->3 ->2 ->1
2. Implementation
(1) BFS
class Solution {
public int integerReplacement(int n) {
Queue<Long> queue = new LinkedList<>();
Set<Long> visited = new HashSet<>();
queue.add((long)n);
visited.add((long)n);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
long curNum = queue.remove();
if (curNum == 1) {
return level;
}
if (curNum % 2 == 0 && !visited.contains(curNum / 2)) {
queue.add(curNum / 2);
visited.add(curNum / 2);
}
else {
if (!visited.contains(curNum + 1)) {
queue.add(curNum + 1);
visited.add(curNum + 1);
}
if (!visited.contains(curNum - 1)) {
queue.add(curNum - 1);
visited.add(curNum - 1);
}
}
}
++level;
}
return -1;
}
}
3. Time & Space Complexity
BFS: 时间复杂度?, 空间复杂度?
Last updated
Was this helpful?