Link
给你一个以二进制形式表示的数字 \(s\)。请你返回按下述规则将其减少到 \(1\) 所需要的步骤数：
如果当前数字为偶数，则将其除以 \(2\)。
如果当前数字为奇数，则将其加上 \(1\)。
题目保证你总是可以按上述规则将测试用例变为 \(1\)。
思考操作对每位数字带来了什么影响。
假设我们有一个一般的 \(s\)，假定 \(s = 11001100\)。
- 除以 \(2\)：\(11001100 \to 1100110\)
- 除以 \(2\)：\(1100110 \to 110011\)
- 加上 \(1\)：\(110011 \to 110100\)
- 除以 \(2\)：\(110100 \to 11010\)
- 除以 \(2\)：\(11010 \to 1101\)
- 加上 \(1\)：\(1101 \to 1110\)
- 除以 \(2\)：\(1110 \to 111\)
- 加上 \(1\)：\(111 \to 1000\)
- 除以 \(2\)：\(1000 \to 100\)
- 除以 \(2\)：\(100 \to 10\)
- 除以 \(2\)：\(10 \to 1\)
- 结束
一个很重要的发现是：要删掉一个末尾的 \(1\)，需要先加上 \(1\) 把它变成 \(0\)，再除以 \(2\)。这样需要两次操作。
由于进位，加上的这个 \(1\) 可以看成是加给了 \(s\) 的最后一个 \(0\)。整个串的末尾从 \(\cdots 011\cdots11\) 变成了 \(\cdots 100 \cdots 00\)。之后，原先是 \(1\) 的位置只需要一直除以 \(2\) 就能够删干净。
现在看看删掉 \(1\) 之后极长的一段 \(0\) 发生的变化。原本是 \(00\cdots0011\cdots11\) 的串，由于末尾 \(1\) 的存在，先加 \(1\) 变为 \(00\cdots0100\cdots00\)，忽略原先是 \(1\) 的位置，变成 \(00\cdots01\)。这时要加 \(1\) 再除以 \(2\)，消掉一个字符，又回到 \(00\cdots01\) 的形式。
我们以加上 \(1\) 除以 \(2\) 为一个循环，可以认为每个 \(0\) 都需要两次操作。最后一个 \(0\) 在先前的操作中会先一步变为 \(1\)，和若干 \(1\) 子串（如果存在）结合，实际上又回到了前述情形。注意一开始我们就加了一次 \(1\)，实际上循环是形如加-加-除-加-除的，要多加一次。
现在我们得出结论：所有的 \(1\) 都需要 \(1\) 次操作，所有的 \(0\) 都需要 \(2\) 次操作（除非其处于最后一个 \(1\) 的后面，此时只需要 \(1\) 次操作），加上 \(1\) 次额外的操作即为答案。
边界条件是 \(100\cdots00\)，这时这个 \(1\) 不需要 \(1\) 次操作，并且这个额外的操作也不存在，因为一直除以 \(2\) 就能够抹去，剩下 \(1\)。
时间复杂度和空间复杂度均为 \(O(n)\)。
class Solution {
public:int numSteps(string s) {return std::count(s.begin(), s.end(), '0') + s.find_last_of('1') + 2 * (std::count(s.begin(), s.end(), '1') != 1);}
};