解题思路
这是一道字符串处理题目,主要思路如下:
-
特殊情况处理:
- 长度为1:结果为0
- 长度为2:如果两字符相同为0,不同为2
-
一般情况处理:
- 从头部开始统计连续黑白相间的长度(
headLen
) - 从尾部开始统计连续黑白相间的长度(
tailLen
) - 统计中间部分的最长黑白相间长度
- 如果首尾字符不同,可以考虑将头尾相连
- 从头部开始统计连续黑白相间的长度(
-
最终结果为以上所有可能长度的最大值
代码
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
while(cin >> s) {
int len = s.length();
// 特殊情况处理
if(len == 1) {
cout << "0" << endl;
continue;
}
if(len == 2) {
cout << (s[0] == s[1] ? "0" : "2") << endl;
continue;
}
// 计算头部连续长度
int headLen = 1, tailLen = 1;
int start = 0, end = len - 1;
for(; start < end; start++) {
if(s[start] == s[start + 1]) break;
headLen++;
}
// 如果扫描到结尾,说明整个串都是相间的
if(start == end) {
cout << headLen << endl;
continue;
}
// 计算尾部连续长度
for(; end > start; end--) {
if(s[end] == s[end - 1]) break;
tailLen++;
}
// 找出最大长度
int maxLen = max(headLen, tailLen);
int tempLen = 1;
// 处理中间部分
for(start++, end--; start < end; start++) {
if(s[start] == s[start + 1]) {
maxLen = max(maxLen, tempLen);
tempLen = 1;
} else {
tempLen++;
}
}
// 如果首尾字符不同,可以考虑连接
if(s[0] != s[len - 1]) {
maxLen = max(maxLen, headLen + tailLen);
}
cout << maxLen << endl;
}
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String s = sc.next();
int len = s.length();
// 特殊情况处理
if(len == 1) {
System.out.println(0);
continue;
}
if(len == 2) {
System.out.println(s.charAt(0) == s.charAt(1) ? 0 : 2);
continue;
}
// 计算头部连续长度
int headLen = 1, tailLen = 1;
int start = 0, end = len - 1;
for(; start < end; start++) {
if(s.charAt(start) == s.charAt(start + 1)) break;
headLen++;
}
// 如果扫描到结尾,说明整个串都是相间的
if(start == end) {
System.out.println(headLen);
continue;
}
// 计算尾部连续长度
for(; end > start; end--) {
if(s.charAt(end) == s.charAt(end - 1)) break;
tailLen++;
}
// 找出最大长度
int maxLen = Math.max(headLen, tailLen);
int tempLen = 1;
// 处理中间部分
for(start++, end--; start < end; start++) {
if(s.charAt(start) == s.charAt(start + 1)) {
maxLen = Math.max(maxLen, tempLen);
tempLen = 1;
} else {
tempLen++;
}
}
// 如果首尾字符不同,可以考虑连接
if(s.charAt(0) != s.charAt(len - 1)) {
maxLen = Math.max(maxLen, headLen + tailLen);
}
System.out.println(maxLen);
}
}
}
while True:
try:
s = input()
length = len(s)
# 特殊情况处理
if length == 1:
print(0)
continue
if length == 2:
print(0 if s[0] == s[1] else 2)
continue
# 计算头部连续长度
head_len = 1
tail_len = 1
start = 0
end = length - 1
while start < end:
if s[start] == s[start + 1]:
break
head_len += 1
start += 1
# 如果扫描到结尾,说明整个串都是相间的
if start == end:
print(head_len)
continue
# 计算尾部连续长度
while end > start:
if s[end] == s[end - 1]:
break
tail_len += 1
end -= 1
# 找出最大长度
max_len = max(head_len, tail_len)
temp_len = 1
# 处理中间部分
start += 1
end -= 1
while start < end:
if s[start] == s[start + 1]:
max_len = max(max_len, temp_len)
temp_len = 1
else:
temp_len += 1
start += 1
# 如果首尾字符不同,可以考虑连接
if s[0] != s[-1]:
max_len = max(max_len, head_len + tail_len)
print(max_len)
except EOFError:
break
算法及复杂度
- 算法:双指针 + 贪心
- 时间复杂度:
- 其中
为字符串长度,需要遍历一次字符串
- 空间复杂度:
- 只需要常数级别的额外空间存储计数器和指针