這次的算法題寫的比較low,效率非常低,不過和我一起做這個(gè)算法題的小伙伴們用的暴搜沒通過所有的測試,這我還是比較欣慰的,哈哈哈哈瑰谜。。渤早。
題目:
查找字符串中最長的非重復(fù)子串的長度,例如abcabc最長的非重復(fù)子串的長度就是3(abc/bca/cab),再例如bbb最長的非重復(fù)子串就是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;
}
//設(shè)置起始點(diǎn)
for (long i = 0; i < len; i++) {
//從起始點(diǎn)開始遍歷，有點(diǎn)像冒泡
for (long j = i; j < len; j++) {
//從創(chuàng)建的容器里找有沒有重復(fù)的
for (long x = i; x <=j; x++) {
//有重復(fù)的
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;
}
//最后一個(gè)沒找到，加到數(shù)組里
if (x==j) {
tempStr[x] = s[j];
long tempSum = j - i + 1;
sum = tempSum > sum ? tempSum: sum;
//如果遍歷到最后一個(gè)字符了,就直接發(fā)返回結(jié)果
if (j == (len - 1)){
return (int)sum;
}
}
}
//剪枝條件，如果有重復(fù)的，就進(jìn)行下一次循環(huán)對比
if (stop) {
stop = 0;
break;
}
}
}
return (int)sum;
}
我的思路其實(shí)就是各種遍歷,通過剪枝來減少遍歷的次數(shù)。還有就是關(guān)于下面代碼我要說明一下嗤攻，因?yàn)樵谖译娔X上沒寫這兩個(gè)for循環(huán)也是OK的,但提交到網(wǎng)站上就出錯(cuò)過不了暴区。偷俭。淹遵。
for (long i = 0;i < len;i++) {
tempStr[i] = 0;
}
上面這段代碼是進(jìn)行了一個(gè)初始化的過程,如果搜到與容器內(nèi)重復(fù)的字符，還要將容器執(zhí)行一遍上述代碼，這是一步low的操作耐床，但如果不寫這一段，執(zhí)行起來就會(huì)出現(xiàn)莫名其妙的錯(cuò)誤偎箫，在OC 里初始化一個(gè)對象，沒賦初值的屬性是nil或者0，這是runtime 里有專門代碼來做的,但在C里沒初始化就是個(gè)野指針,無法確定初值是什么，所以不寫那一段在我電腦上也許OK,提交到網(wǎng)站上就出錯(cuò)了想许。漱凝。阵苇。
