题解 | 最长区间

解题思路

这是一个字符串循环移位问题，需要找到所有可能的移位中最长的连续1序列。

关键点：

将字符串复制一遍可以处理所有移位情况
使用双指针技术查找连续1序列
注意结果不能超过原字符串长度

算法步骤：

复制字符串拼接到原串后面
使用双指针遍历查找连续1
取最大长度和原串长度的较小值

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMaxConsecutiveOnes(string s) {
        string doubled = s + s;
        int maxLen = 0;
        int start = 0;
        int n = s.length();
        
        while (start < doubled.length()) {
            if (doubled[start] == '1') {
                int end = start;
                while (end < doubled.length() && doubled[end] == '1') {
                    end++;
                }
                maxLen = max(maxLen, end - start);
                start = end;
            } else {
                start++;
            }
        }
        
        return min(maxLen, n);
    }
};

int main() {
    string s;
    cin >> s;
    
    Solution solution;
    cout << solution.findMaxConsecutiveOnes(s) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int findMaxConsecutiveOnes(String s) {
            String doubled = s + s;
            int maxLen = 0;
            int start = 0;
            
            while (start < doubled.length()) {
                if (doubled.charAt(start) == '1') {
                    int end = start;
                    while (end < doubled.length() && doubled.charAt(end) == '1') {
                        end++;
                    }
                    maxLen = Math.max(maxLen, end - start);
                    start = end;
                } else {
                    start++;
                }
            }
            
            return Math.min(maxLen, s.length());
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        Solution solution = new Solution();
        System.out.println(solution.findMaxConsecutiveOnes(s));
        
        sc.close();
    }
}

class Solution:
    def find_max_consecutive_ones(self, s: str) -> int:
        doubled = s + s
        max_len = 0
        start = 0
        
        while start < len(doubled):
            if doubled[start] == '1':
                end = start
                while end < len(doubled) and doubled[end] == '1':
                    end += 1
                max_len = max(max_len, end - start)
                start = end
            else:
                start += 1
                
        return min(max_len, len(s))

# Read input and solve
s = input().strip()
solution = Solution()
print(solution.find_max_consecutive_ones(s))

算法及复杂度

算法：双指针扫描
时间复杂度： $\mathcal{O(n)}$ ，其中 $n$ 是字符串长度
空间复杂度： $\mathcal{O(n)}$ ，用于存储复制后的字符串