leetcode/
integer_replacement.rs

1//! # 397. 整数替换
2//!
3//! 难度 中等
4//!
5//! 给定一个正整数 `n` ，你可以做如下操作：
6//!
7//! 如果 `n` 是偶数，则用 `n / 2` 替换 `n` 。
8//! 如果 `n` 是奇数，则可以用 `n + 1` 或 `n - 1` 替换 `n` 。
9//! `n` 变为 `1` 所需的最小替换次数是多少？
10//!
11//!
12//!
13//! ## 示例 1：
14//!
15//! ```text
16//! 输入：n = 8
17//! 输出：3
18//! 解释：8 -> 4 -> 2 -> 1
19//! ```
20//!
21//! ## 示例 2：
22//!
23//! ```text
24//! 输入：n = 7
25//! 输出：4
26//! 解释：7 -> 8 -> 4 -> 2 -> 1
27//! 或 7 -> 6 -> 3 -> 2 -> 1
28//! ```
29//!
30//! ## 示例 3：
31//!
32//! ```text
33//! 输入：n = 4
34//! 输出：2
35//! ```
36//!
37//!
38//! ## 提示：
39//!
40//! * `1 <= n <= 231 - 1`
41//!
42//! See [leetcode](https://leetcode-cn.com/problems/integer-replacement/)
43
44pub struct Solution;
45
46impl Solution {
47    pub fn integer_replacement(n: i32) -> i32 {
48        let mut times = 0;
49        let mut n: i64 = n as i64;
50        while n > 1 {
51            n = match n % 2 {
52                0 => n / 2,
53                _ => {
54                    if n == 3 {
55                        n - 1
56                    } else {
57                        match n & 0b0000_0000_0000_0011 {
58                            0b0000_0000_0000_0011 => n + 1,
59                            0b0000_0000_0000_0001 => n - 1,
60                            _ => unreachable!(),
61                        }
62                    }
63                }
64            };
65            times += 1;
66        }
67        times
68    }
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test() {
77        let t = |n| Solution::integer_replacement(n);
78        assert_eq!(3, t(8));
79        assert_eq!(4, t(7));
80        assert_eq!(2, t(4));
81    }
82}
leetcode/integer_replacement.rs

leetcode/
integer_replacement.rs
