LeetCode 991. 坏了的计算器

Categories:

题目描述
思路分析
1. 解法一：逆向贪心（推荐）
相似题目

题目描述

✅ 991. 坏了的计算器

思路分析

解法一：逆向贪心（推荐）

核心思路：

从 target 反向操作到 startValue。

若 target 为奇数，只能 +1；为偶数则 /2 更优。

最后补上差值即可。

复杂度分析：

时间复杂度：O(log target)。

空间复杂度：O(1)。

class Solution {
    public int brokenCalc(int startValue, int target) {
        int ops = 0;
        while (target > startValue) {
            if ((target & 1) == 1) {
                target++;
            } else {
                target >>= 1;
            }
            ops++;
        }
        return ops + (startValue - target);
    }
}

func brokenCalc(startValue int, target int) int {
	ops := 0
	for target > startValue {
		if target%2 == 1 {
			target++
		} else {
			target /= 2
		}
		ops++
	}
	return ops + (startValue - target)
}

相似题目

题目	难度	考察点
69. x 的平方根	简单	二分
754. 到达终点数字	中等	数学
65. 有效数字	困难	字符串解析
670. 最大交换	中等	贪心
171. Excel 表列序号	简单	数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/77741792