这次的算法题写的比较low,效率非常低,不过和我一起做这个算法题的小伙伴们用的暴搜没通过所有的测试,这我还是比较欣慰的,哈哈哈哈。。。
题目:
查找字符串中最长的非重复子串的长度,例如abcabc最长的非重复子串的长度就是3(abc/bca/cab),再例如bbb最长的非重复子串就是b,长度为1(注意空串).
代码:
int lengthOfLongestSubstring(char* s) {
//记录字符串s的长度
unsigned long len = strlen(s);
//如果字符串为空字符串或者字符串长度为1，则返回字符串长度即可
if (len <=1) return (int)len;
long sum = 0,stop = 0;
//定义字符串
char tempStr[len];
//给定义的字符串分配空间
for (long i = 0;i < len;i++) {
tempStr[i] = 0;
}
//设置起始点
for (long i = 0; i < len; i++) {
//从起始点开始遍历，有点像冒泡
for (long j = i; j < len; j++) {
//从创建的容器里找有没有重复的
for (long x = i; x <=j; x++) {
//有重复的
if (tempStr[x]==s[j]) {
long tempSum = j-x;
sum = tempSum > sum ? tempSum: sum;
stop = 1;
for (long k = 0;k < len;k++) {
tempStr[k] = 0;
}
break;
}
//最后一个没找到，加到数组里
if (x==j) {
tempStr[x] = s[j];
long tempSum = j - i + 1;
sum = tempSum > sum ? tempSum: sum;
//如果遍历到最后一个字符了,就直接发返回结果
if (j == (len - 1)){
return (int)sum;
}
}
}
//剪枝条件，如果有重复的，就进行下一次循环对比
if (stop) {
stop = 0;
break;
}
}
}
return (int)sum;
}
我的思路其实就是各种遍历,通过剪枝来减少遍历的次数。还有就是关于下面代码我要说明一下，因为在我电脑上没写这两个for循环也是OK的,但提交到网站上就出错过不了。。。
for (long i = 0;i < len;i++) {
tempStr[i] = 0;
}
上面这段代码是进行了一个初始化的过程,如果搜到与容器内重复的字符，还要将容器执行一遍上述代码，这是一步low的操作，但如果不写这一段，执行起来就会出现莫名其妙的错误，在OC 里初始化一个对象，没赋初值的属性是nil或者0，这是runtime 里有专门代码来做的,但在C里没初始化就是个野指针,无法确定初值是什么，所以不写那一段在我电脑上也许OK,提交到网站上就出错了。。。
