3228. 將 1 移動到末尾的最大操作次數

思路

想要有最多的操作次數，先移動左邊的1是最好的選擇，
因為移動左邊就可以被後面的1擋住，後面的1前進十，左邊的1就可以多一次操作。
所以在遇到1時，就將它往後移動到不能再移動為止，並且紀錄下出現次數。
若可以移動，答案加上出現次數。

有個更簡潔判斷能不能移動的方式，在遇到0時，
先判斷前一個是不是1，如果是，相當於它可以前進到這裡來，
否則忽略（也就是整段0只看與1相接的那一個，因為只需要知道1能不能前進就行）

程式碼

1. 模擬

class Solution {
public:
    int maxOperations(string s) {
        int n = s.size();
        int cnt1 = 0;
        int res = 0;
        for(int i = 0; i < n; ++i) {
            if(s[i] == '1') {
                bool isMovable = false;
                int j = i + 1; // 紀錄終點
                while(j < n && s[j] == '0') { // 可以前進
                    isMovable = true;
                    ++j; 
                }
                i = j - 1; // 需要注意 for 迴圈的 ++i
                ++cnt1; // 紀錄 1 的出現次數
                if(isMovable) {
                    res += cnt1; // 前面的每個數字`1`都能往前
                }
            }
        }
        return res;
    }
};

2. 優化

class Solution {
public:
    int maxOperations(string s) {
        int n = s.size();
        int res = 0, cnt1 = 0;
        for(int i = 0; i < n; ++i) {
            if(s[i] == '1') {
                ++cnt1;
            }
            else if(i > 0 && s[i - 1] == '1') {
                res += cnt1;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$