quick and right coding
昨天看了下邹博的PPT，邹博是负责July团队负责字符串一块的，包括Manachester算法，KMP，BP，字符串排列(其实是回溯法了)等等，
有一个不太重要的地方，就是邹博的代码比较短，而且看起来逻辑比较漂漂，而我的经常逻辑复杂，还写半天，还经常出bug，于是写点总结。
先拿最长回文子串朴素O(n^2)代码这个case来看，遍历回文串中心，我代码可能有问题，以为不需要首尾两个字符了，因为肯定是1了，但是忘记考虑偶数长回文子串了，如果后面Index=1(0-base)的没有考虑01为中心的偶长传可能就会有问题了，
末尾也是一样的。自己漏考虑。
int maxdrome_centre(string str)
{
if(str.size()==0) return 0;
int maxlen=1,max;
for(int i=1;i<str.size()-1;i++)
{
max=1;
for(int j=1;j<=(str.size()-1)/2;j++)//two
{
if(i-j>=0 && i+j <=str.size()-1)
{
if(str[i-j] == str[i+j])
max+=2;
else
break;
}
else
break;
}
if(max>maxlen)
maxlen=max;
max=1;
if(str[i]==str[i+1])
{
max++;
for(int j=1;j<=(str.size()-2)/2;j++)
{
if(i-j>=0 && i+1+j<=str.size()-1 )
{
if(str[i-j]==str[i+1+j])
max+=2;
else
break;
}
else
break;
}
if(max>maxlen)
maxlen=max;
}
}
return maxlen;
}
看看这个代码里面，还嵌套了break，for条件判断之后，里面又判断了越界问题，其实是有重复的，for里面的条件其实没有必要，完全可以用if里面的替换掉，因为只要头尾都每越界，就可以一直两边extend，于是如果越界了，还break，如果写到for
条件里，刚好不用break了，里面如果长度相等就extend，没有的话break，这个是比较合理的，也需要的。而且这个max没必要每次加2，因为完全可以根据j计算出来。
因此代码修改后变成如下的：
int maxdrome_centre(string str)
{
if(str.size()==0) return 0;
int maxlen=1;//total max, at least 1
for(int i=0;i<=str.size()-1;i++)
{
for(int j=1;i-j>=0 && i+j <=str.size()-1;j++)//odd
{
if(str[i-j] != str[i+j])
break;
}
max=2*j+1;
if(max>maxlen)
maxlen=max;
for(int j=0;(i-j>=0) && (i+j+1) <=str.size()-1;j++)//odd
{
if(str[i-j] != str[i+j+1])
break;
}
max=2*j++2;
if(max>maxlen)
maxlen=max;
}
return maxlen;
}
这个逻辑几乎和邹博一样了，所以总结一下自己coding的一些不好的思维和设计逻辑的习惯
1.不要去根据不等式去计算i或者j的范围，这是计算机做的事情，例如i-j>=0 i+j<=str.size()-1 这个我有时候可能回想着推出i j范围，然后写在条件语句，这个其实直接写会比较好，计算机会处理好的
2.写逻辑语句要想清楚是否两个条件有重叠有包含关系，只要选那个更严格的条件就可以了，否则逻辑更复杂，例如我for里面先去限制j最大只能extend (n-1)/2长度，再在里面加if限制两边越界，其实越界包含了前者，
只需要这个条件，因此直接放到for条件里，这样少了break，还有计算长度直接有j决定，所以不需要里面每次max+2，当然这个问题会轻一点，但是没想到不应该。
3.另外后面偶数长度还先加if判断是否第一个成立，完全可以放到循环里面，不然逻辑复杂，易出bug，还有一个内部的max没必要，因为每次都是计算当期的与总的比较，不是两次max比较，也没想清楚。
总之代码写的还是naive，还是要多读别人的代码，例如fawkes，adhoc，邹博等，现在要求代码要写的快，逻辑简单清晰，精炼，越垄长的容易bug