Last Updated on 2022-03-23 by Clay
題目
There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:
- multiply the number on display by
2, or - subtract
1from the number on display.
Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.
Example 1:
Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.
Example 2:
Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.
Example 3:
Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.
Constraints:
1 <= x, y <= 109
我們有一個起始值 startValue 以及一個目標值 target，而我們能做的操作只有將 startValue x2 或是 -1 —— 最終要讓 startValue 等於 target，而我們要回傳需要操作的最少步驟。
解題思路
Greedy 解法
這題比較取巧的是，如果想要使用貪婪解法，我們必須將目標值 target 視為起點，反向操作去逼近起始值 startValue。
這是因為如果我們真的拿起起始值去操作、以逼近目標值 target，可能會存在著『先減去部分值再乘以二』比『直接乘以二再減去差值』操作步驟更少的情況（反過來的情況也是有的）；這樣一來，我們就得不斷地同時評估兩種操作的可能性。
但若是使用 target 逼近 startValue，操作就變得單純：
- 如果 target 小於 startValue：回傳當前累積操作次數 + startValue - target（因為兩者的差需要不斷 +1 的操作）
- 如果 target 是偶數：直接除以 2
- 如果 target 是奇數：先加 1 使其變成偶數
因為最快的逼近方法就是除以 2，所以最快的逼近方法，自然就是在每次可以除以 2 時進行此操作，故為貪婪解。
Greedy 解法複雜度
因為只需要儲存操作次數，故空間複雜度為 O(1)；而我看到大部分此解法的時間複雜度都寫 O(log(n))，我想是可以視為大部分的逼近都是靠除 2 來達成的。
| Time complexity | O(log n) |
| Space complexity | O(1) |
Greedy 解法 C++ 範例程式碼
class Solution {
public:
int brokenCalc(int startValue, int target) {
// Init
int opt = 0;
while (startValue < target) {
if (target % 2 == 1) {
++target;
}
else {
target /= 2;
}
// Step
++opt;
}
return opt + startValue - target;
}
};Greedy 解法 Python 範例程式碼
class Solution:
def brokenCalc(self, startValue: int, target: int) -> int:
# Init
opt = 0
# Operatings
while startValue < target:
if target % 2 == 1:
target = target + 1
else:
target = target // 2
# Step
opt += 1
# Return opt + distance
return opt + startValue - target