📘 題目敘述
給你一個二進位表示的字串 s，代表一個正整數。請回傳把這個數字化簡到 1 需要幾步，規則如下：
- 如果目前數字是偶數：必須除以 2。
- 如果目前數字是奇數：必須加 1。
題目保證所有測資都能走到 1。
條件限制
1 <= s.length <= 500s只由'0'、'1'組成s[0] == '1'
🧠 解題思路
這題不能把 s 轉成整數直接模擬，因為 s.length 最多到 500 會爆。正確做法是直接用二進位的性質計步數。
先想兩個基本操作在二進位代表什麼：
- 除以 2：等價於右移一位（把最後一個 bit 去掉）。
- 奇數加 1：最後一位是
1，加一會產生進位（carry），進位會往左傳：遇到1會變0並繼續 carry；遇到0會變1並停止 carry。若一路都是1，最後會多出一個新的最高位。
我的程式不是真的去改字串，而是用「掃描 + 計數」來等價計算總步數。
做法分成兩段：
第一段先把「一定會做的除以 2 次數」算好。二進位長度是 n，不管中間怎麼加一，想把數字降到只剩最高位那個 1，至少要做 n-1 次右移，所以先 count = n - 1。
第二段從右往左掃描，用 check 表示「右邊是否已經進入 carry 狀態」。一旦 carry 狀態存在，後續遇到 0 會被進位翻成 1，等價於你在那個位置會多付出一次操作成本，所以看到 0 且 check == true 就 count++。最後只要整體曾經產生 carry（也就是 check == true），還會有固定的收尾成本，所以再 count += 2。
所有變數
count：答案步數累計器。一開始先放入基本右移次數s.size() - 1，後面再補上因為 carry 造成的額外步數與收尾步數。check：布林值，表示是否已經進入「carry 會往左傳」的狀態。一旦變成true就代表過程中曾經需要處理加一造成的進位效應。i：從右往左掃描的索引，掃到i > 0停止，因為最左邊那個 bit 最後會變成終點"1"的基準。
🪜 主要流程步驟
1. 初始化基本步數
count = s.size() - 1check = false
這一步的直覺是：不管你中間做了多少次 +1，要把長度為 n 的二進位降到只剩最高位，至少要右移 n-1 次，所以先把它加進去。
2. 從右往左掃描，補上 carry 造成的額外步數
用迴圈從 i = n-1 掃到 1：
當看到 s[i] == '1'：把 check = true，表示右側已經出現會引發加一與進位的狀態，之後進位效應會影響更左邊的位元。
當看到 s[i] == '0'：如果 check == true，代表右側存在 carry，這個 0 在進位影響下會被翻成 1，等價於需要多做一次操作，所以 count++。
3. 收尾固定成本
如果 check == true，最後要再補上固定的兩步，所以 count += 2。
⏱️ 複雜度
- 時間複雜度：
O(n)，只需要從右到左掃描一次字串。 - 空間複雜度：
O(1)，只使用常數個變數。
💻 程式碼實作
class Solution {
public:
int numSteps(string s) {
int count = s.size() - 1;
bool check = false;
for (int i = s.size() - 1; i > 0; i--) {
if (s[i] == '1') {
check = true;
} else {
if (check) {
count++;
}
}
}
if (check) {
count += 2;
}
return count;
}
};
🔗 題目連結
https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/