1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int numSteps(String s) {
        int steps = 0;
        boolean hasCarry = false;
        for (int i = s.length() - 1; i > 0; i--) {
            char currLetter = s.charAt(i);
            if (hasCarry) {
                if (currLetter == '0') {
                    currLetter = '1';
                    hasCarry = false;
                } else {
                    currLetter = '0';
                }
            }
            if (currLetter == '0') {
                steps += 1;
            } else {
                steps += 2;
                hasCarry = true;
            }
        }
        return hasCarry ? steps + 1 : steps;
    }
}

首先记录当前是否有carry. 然后我们从后往前遍历. 先把carry补到当前的位置上. 然后看更新后的位置的数字是什么. 是0就只向右移动一位即可, 否则就是 + 1然后移动一位. + 1的话需要更新carry.

时间复杂度: O(n)
空间复杂度: O(1)