问题描述
给定一个整数，要求算出该整数经过多少次最小变化可以到达1，变化的规则：如果是奇数，可以加一或减一，如果是偶数，直接除2。题目链接：**点我**
样例输入输出
输入：8
输出：3
解释：变化路径：8 -> 4 -> 2 -> 1
输入：7
输出：4
解释：变化路径：7 -> 8 -> 4 -> 2 -> 1 或 7 -> 6 -> 3 -> 2 -> 1
问题解法
直接使用深度搜索算法进行搜索，在搜索过程中对已经搜索过的结果进行存储，以免后续进行重复搜索。由于可能存在 2 ^ 31 -1，如果对其进行加一，可能会超过边界，所以使用 n / 2 + 1 和 n / 2 来替换 n + 1 和 n - 1 的操作，在获得结果后加二即可得到相同的结果。
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
| class Solution {
public int integerReplacement(int n) {
return search(n, new HashMap<>());
}
private int search(int n, Map<Integer, Integer> map) {
if (n == 1) {
return 0;
}
if (map.containsKey(n)) {
return map.get(n);
}
int result;
if (n % 2 == 0) {
result = search(n / 2, map) + 1;
} else {
int temp1 = search(n / 2 + 1, map);
int temp2 = search(n / 2, map);
result = Math.min(temp1, temp2) + 2;
}
map.put(n, Math.min(result, map.getOrDefault(n, Integer.MAX_VALUE)));
return map.get(n);
}
}
|