这是2018年网易校招的一道题，做起来很简单的，不过我可能心不在焉了吧，也遇到了一些小问题，我们一起来看一下吧。
www.nowcoder.com/practice/3fbd8fe929ea4eb3a254c0ed34ac993a
一. 题目
如果一个01串任意两个相邻位置的字符都是不一样的,我们就叫这个01串为交错01串。例如: "1","10101","0101010"都是交错01串。
小易现在有一个01串s,小易想找出一个最长的连续子串,并且这个子串是一个交错01串。小易需要你帮帮忙求出最长的这样的子串的长度是多少。
下面是一个示例参考：
示例参考
二. 分析
由于采用在线编程来写的代码，没有什么报错标红，所以写一点就要自测一下。
首先简单分析一下。
要找最大01串，010是，01010也是，只要交错的就OK。
那么这样就好办了，遍历一遍，依次比较前后两个字符，不同就计数，如果相同，就算本次计数结束，并且缓存下来本次计数数据，将计数器置0，最后输出所记录的最大的数即可。
下面是我的提交，还是我把每一段都标注字母，下面分析。
import java.util.Scanner;
//网易2018校招 - 01串 优化版
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
// A
//双指针
char c;
char c_next;
//临时变量
int sum_temp = 1;
int sum = 1;
// B
//一个循环搞定呀！
for(int i = 0;i < s.length() - 1;i++){
// C
//取值
c = s.charAt(i);
c_next = s.charAt(i + 1);
//D
//判断并计数
if(c != c_next){
sum_temp += 1;
}else{
//记录下来本轮运算结果
if(sum_temp > sum){
sum = sum_temp;
}
sum_temp = 1;
}
}
//E
//输出结果
System.out.println(sum > sum_temp ? sum : sum_temp);
}
}
上面的代码被我用注释分成了ABCDE五部分。
我在做这道题的时候是没有思考，边写边做的，在核心的D部分出了点小问题。
我们依次来看：
输入及A ：
输入，从控制台读取内容保存到s串中，注意手动导包。
A部分我声明了4个变量，两个用于读取字符串比较（我都叫他双指针法，在链表中常用）
另外两个用于保存最大值，因为每个字符串中包含的最大01串有很多，所以我们要不断比较哪个是最大的，于是加了sum_temp用于计数，sum用于持久存储。
B ：
是一个循环，要分析该串必须要遍历一次，为了双指针不发生越界，限制i < length - 1 。
C：
双指针取值，用于比较。
D ：
D是核心部分，用于计数。
举个栗子看看运行过程。
1110101111010101
按照题目要求，这里面有2个01串
第一个是0101 第二个是010101，显然第二个长，输出长度6
下面我简单用s[x]来代表s串中第x+1位数字，如s[0] = 1, s[1] = 1。
第一轮：
1.首先取 s[0]与s[1] 比较后相等 进入else对sum和sum_temp赋值（但是操作后都是默认值1）
2. 取s[1] 与 s[2] 比较后相等 赋值不变。
3. 取s[2] = 1 与 s[3] = 0 比较后不等，sum_temp计数加1，继续下一轮。
4. 同3
5. 同3
6. 同3
7. 经过刚才的运算，sum_temp已经变成了4，也就是第一个01串的长度，
8. 继续比较s[6] 和 s[7] 发现相等就把 调整sum的值（当然是要确保sum是当前的最大值）
9. 继续比较，后面的我就不说了
这里我遇到的问题就是最后的else进不去，就是对于以01或者10结束的这种串，最后的01长度只会记录到sum_temp中，而无法记录到sum中。
在这里坑了我好久，当时短路了可能，也没个纸笔画画什么的，我当时想的方法是把这个串最后加一个 同位，比如010变成0100。
然后最后就顺其自然的可以进去else。
当然这个方法太笨拙了，如果用String操作，就更费运行时间了。
后来想到了何不直接比sum和sum_temp呢？
然后就写了这个sum_temp版了。
三. 运行
下面是我的思路优化到最佳后的算法。
看了一下排行榜第一名 Java 用6ms……
都是BUPT的大佬。
梦寐以求的BUPT，估计我也无缘了，继续奋斗吧。
四. 秀儿操作
下面我们分享秀儿操作吧。
1号秀儿 - 来自BUPT的tjn123大佬，他提交的时候是6ms，我测试了一下11ms，是很低的了，我们来看下代码。
int work(String inputStr) {
//s的长度
int len = inputStr.length() ;
//s <= 1 直接返回1
if (len <= 1) return len ;
//初始化一下
int curLen = 1 ;
int maxLen = 1 ;
int pos = 1 ;
char lastC = inputStr.charAt(0) ;
//一个while
while(pos < len) {
//取一个当前的字符
char c = inputStr.charAt(pos) ;
//比较
if (c==lastC) {
curLen = 1 ;
} else {
curLen = curLen + 1 ;
}
lastC = c ;
maxLen = Math.max(maxLen, curLen);
pos++ ;
}
return maxLen ;
}
举个栗子来看下吧。
1011100101 应该返回4
第一轮：s[0] = 1 不等于 s[1] curLen+1 lastC重新赋值前进一位，maxLen也经过运算取到了合适的值。
第二轮： s[1] = 0 不等于 s[2] curLen+1 lastC重新赋值前进一位,当前是curLen = 3 大，maxLen被赋值为3,这个串就计算出来了。
第三轮： s[2] = 1 等于 s[3] = 1 curLen一下回到解放前=1，
第四轮：还是解放前
……下面的不要再说了
分析下来发现我俩的算法好像一样啊？
到底是什么让我们产生了差距呢？？？
我怀疑是charAt调用次数的问题。
所以我打算优化一下我的代码，稍等片刻。
我回来了，经测试不是chatAt次数的问题，而是输入的问题。
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ;
String s = null ;
try {
s = br.readLine() ;
} catch(Exception e) {
}
这位BUPT的大神是用BufferedReader来进行输入的。
速度可不是一般快呀！
内存也省了不少呀。
这里就出来一个问题了，我们不如挖个坑，去讨论一下BufferedReader与Scanner的性能比较吧。
2号秀儿 的js的正则处理
正则表达式永远学不会的看到这个一脸懵逼。
感兴趣的可以研究研究哦。
//javascript语言处理这样的问题很简单，使用正则表达式
var str=readline();
var reg=/0?(10)*1?/g;
var relArr=str.match(reg);
var max=0;
for(var i=0;i<relArr.length;i++){
if(relArr[i].length>max){
max=relArr[i].length;
}
}
print(max);
更多的可以去题目下面看。
好了，就这样。
五. 总结
觉得刷题也挺有意思的嘛，就是太费时间了，需要思考，需要写，最后我还有整理的习惯，一上午就能刷一道题加写文章。
不过要是有长进的话，也值咯。
网友评论