mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
63 lines
2.1 KiB
Markdown
Executable File
63 lines
2.1 KiB
Markdown
Executable File
# [397. Integer Replacement](https://leetcode.com/problems/integer-replacement/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given a positive integer n and you can do operations as follow:
|
||
|
||
1. If n is even, replace n with `n/2`.
|
||
2. If n is odd, you can replace n with either `n + 1` or `n - 1`.
|
||
|
||
What is the minimum number of replacements needed for n to 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
|
||
|
||
|
||
## 题目大意
|
||
|
||
给定一个正整数 n，你可以做如下操作：
|
||
|
||
1. 如果 n 是偶数，则用 n / 2 替换 n。
|
||
2. 如果 n 是奇数，则可以用 n + 1 或 n - 1 替换 n。
|
||
|
||
问 n 变为 1 所需的最小替换次数是多少？
|
||
|
||
|
||
## 解题思路
|
||
|
||
|
||
- 题目给出一个整数 `n`，然后让我们通过变换将它为 1，如果 `n` 是偶数，可以直接变为 `n/2`，如果是奇数，可以先 `n+1` 或 `n-1`，问最终变为 1 的最少步骤。
|
||
- 当 n 为奇数的时候，什么时候需要加 1 ，什么时候需要减 1 ，通过观察规律可以发现，除了 3 和 7 以外，所有加 1 就变成 4 的倍数的奇数，都适合先加 1 运算，比如 15:
|
||
|
||
15 -> 16 -> 8 -> 4 -> 2 -> 1
|
||
15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1
|
||
|
||
111011 -> 111010 -> 11101 -> 11100 -> 1110 -> 111 -> 1000 -> 100 -> 10 -> 1
|
||
111011 -> 111100 -> 11110 -> 1111 -> 10000 -> 1000 -> 100 -> 10 -> 1
|
||
|
||
- 对于 7 来说，加 1 和减 1 的结果相同，可以不用管，对于 3 来说，减 1 的步骤更少，所以需要先去掉这种特殊情况。
|
||
- 最后如何判断某个数字加 1 后是 4 的倍数呢？这里有一个小技巧，由于之前判断了其是奇数了，那么最右边一位肯定是 1，如果其右边第二位也是 1 的话，那么进行加 1 运算，进位后右边肯定会出现两个 0，则一定是 4 的倍数。于是就可以判断出来了。剩下的情况就是偶数的情况，如果之前判定是偶数，那么直接除以 2 (右移一位)即可。
|
||
|