LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.13
• 题目：3228.将1移动到末尾的最大操作次数
• 难度：中等
• 标签: 贪心 字符串 计数

1. 题目理解

问题描述：
给你一个二进制字符串 s。你可以对其执行任意次如下操作：选择下标 i（满足 i + 1 < s.length），若 s[i] == '1' 且 s[i + 1] == '0'，则将 s[i] 右移直到到达字符串末端或另一个 '1'。返回能执行的最大操作次数。

示例：

示例 1： 输入： s = "1001101" 输出： 4 解释： 可以执行以下操作： 选择下标 i = 0。结果字符串为 s = "0011101"。 选择下标 i = 4。结果字符串为 s = "0011011"。 选择下标 i = 3。结果字符串为 s = "0010111"。 选择下标 i = 2。结果字符串为 s = "0001111"。

示例 2： 输入： s = "00111" 输出： 0

2. 解题思路

核心观察

• 操作的本质是让 '1' 尽可能右移，每次操作的“触发条件”是 '1' 右侧紧邻 '0'，且操作次数由该 '1' 右侧的 '1' 数量决定（右侧有多少个 '1'，该 '0' 块就能被触发多少次操作）。
• 从右往左遍历字符串，统计每个 '0' 块左侧的 '1' 能触发的操作次数，可避免重复计算且保证时间效率。

算法步骤

1. 统计 '1' 的总数：若 '1' 数量为0或等于字符串长度，直接返回0（无操作空间）。
2. 从右往左遍历：维护当前右侧已统计的 '1' 数量 count1，遇到 '0' 且其左侧是 '1' 时，累加 count1 到结果中；遇到 '1' 时，递减 count1（因为该 '1' 已被统计，后续左侧的 '1' 右侧的 '1' 数量减少）。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
    public static int maxOperations(String s) {
        int count1=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='1'){
                count1++;
            }
        }
        if(count1==0||count1==s.length()){
            return 0;
        }
        int res=0;
        for (int i =  s.length()-1; i >=0; i--){
            if (i==0){
                break;
            }
            if (s.charAt(i)=='1'){count1--;}
            if (s.charAt(i)=='0'&&s.charAt(i-1)=='1'){
                res+=count1;
            }
            else {continue;}
        }
        return res;
    }
}

4. 代码优化说明

• 无需额外数据结构，仅通过一次从右往左的遍历和一次 '1' 数量统计，时间复杂度为 O(n)（n 为字符串长度），空间复杂度为 O(1)，已为最优解。

5. 复杂度分析

• 时间复杂度：O(n)。其中 n 是字符串 s 的长度，需一次遍历统计 '1' 数量，一次从右往左遍历字符串，均为线性时间。
• 空间复杂度：O(1)。仅使用常数级额外空间存储 count1 和 res。

6. 总结

本题通过贪心策略+从右往左遍历的思路，利用“右侧 '1' 数量决定操作次数”的规律，高效统计最大操作次数。核心在于理解每次操作的触发条件与右侧 '1' 数量的关联，避免模拟实际移动过程，从而将时间复杂度优化至线性级别，是典型的“通过规律推导替代暴力模拟”的算法题思路。