一) 這裡用GOLANG實作了一個查找最長不重複子串的算法,在暴力查詢的基礎上作了優化,雖然速度還是比較慢,但是有助于了解後邊進階的算法,值得一記。
暴力查詢的優化思路:
1)如果我們已經查找到的最大子串長度比剩下沒有for到的子串還長,那最大子串不可能會在發生改變了,我們就不往下找了,傳回這個最大子串長度;
2)這個是最重要的:在我們發現某一個字元在子串中重複時,比如" abcdccefgd"中, i = 0, 在j = 4的時候會發現 4位上的字元'c'和前面位置2上的'c'重複。此時,我們不是i++了,而是 把i 挪到位置2後面的3上,從那裡開始找子串。如果我們不這麼做,而是繼續i++, i = 1 和 i = 2 這兩個也會在j=4處發現重複,從這裡退出,最大不重複子串也仍然是i = 0時得到的那個數。
這個算法還可以優化,可以考慮提前配置設定一個數組來記錄該把 i挪到哪裡,而不是用函數調用的方法,往下看。
func lengthOfLongestSubstring(s string) int {
sLen := len(s)
var maxSubLen, lastPos int
for i := 0; i < sLen - 1; i++ {
//第二個for,如果剩下的字元串長度都沒有已經找到的maxSubLen長,那我們就可以不去找了
if maxSubLen < sLen-i {
for j := i+1; (j < sLen) ; j++ {
lastPos = findCharInSubStringPosition(s[i:], j-i)
if lastPos < 0 {
//j位置上的字元沒有在s[i:j]中重複,可以測試一下是否要更新maxSubLen
if j-i > maxSubLen {
maxSubLen = j-i
}
} else {
// j 位置上的字元在s[i:j]中重複,重複位置為i+lastPos,i就從i+lastPos後一位開始
// 因為若從i+1開始,那麼後面還是會在到達目前的j位置時,出現與i+lastPos重複的情況,
i = lastPos + i
//這裡我們把i挪到重複字元的第一個字元上,for結尾的i++幫我們挪到下一位
break
}
}
}
}
if sLen != 0 {
maxSubLen++ //計算過程中,都是用下标計算而已,真正的總數我們需要++一下
}
return maxSubLen
}
// 這個函數可以找到位置j處字元在 參數s中的位置,如果不存在,則傳回-1
func findCharInSubStringPosition(s string, j int) int {
for i := 0; i < j; i++ {
if s[i] == s[j] {
return i
}
}
return -1
}
借助外部的一個哈希表來儲存一些東西:
func lengthOfLongestSubstring(s string) int {
//隻支援ASCII碼,
tmp := [128]int{}
var start, maxSubstr, i int
sLen := len(s)
// nil string return 0
if sLen == 0 {
return 0
}
// initial hash tbl
for i := 0; i < len(tmp); i++ {
tmp[i] = -1
}
for i = 0; i < sLen; i++ {
if tmp[ s[i] ] >= start {
if s[i] != s[start] && i - tmp[s[i]] > maxSubstr {
maxSubstr = i - tmp[s[i]]
}
start = tmp[ s[i] ] + 1
}
if i - start > maxSubstr {
maxSubstr = i - start
}
tmp[ s[i] ] = i
}
//the last i++ isn't what we want
i--
if i - start > maxSubstr {
maxSubstr = i - start
}
return maxSubstr + 1
}
二)最長回文子串算法
最長回文子串,首先用暴力搜尋。接着進行改進,改進的是從母字元串往後面掃描,同時進行了優化,LeetCode上速度還行:
//最長回文子串 1
func longestPalindrome(s string) string {
var subLen, maxLen, pos int
var i, j int
sLen := len(s)
for i = 0; i < sLen; i++ {
for j = i+1; j <= sLen; j++ {
subLen = isPalindrome(s[i:j])
if ( subLen > 0) && subLen > maxLen {
maxLen = subLen
pos = i
}
}
}
return s[pos: pos+maxLen]
}
func isPalindrome(s string) int {
sLen := len(s)
for i := 0; i < sLen/2; i++ {
if s[i] != s[sLen - 1 -i] {
return -1
}
}
return sLen
}
//最長回文子串2
func longestPalindrome(s string) string {
var tmpLen, maxLen, pos int
var i, j int
sLen := len(s)
if sLen == 0 {
return ""
}
for i = 0; i < sLen; i++ {
if (sLen-i)*2 <= maxLen {
break
}
for j = i; j >= 0 && 2*i-j < sLen; j-- {
if s[j] != s[2*i-j] {
break
}
}
j++
tmpLen = 2*(i-j) + 1
if tmpLen > maxLen {
maxLen = tmpLen
pos = j
}
for j = 0; j <= i && i+j+1 < sLen; j++ {
if s[i-j] != s[i+j+1] {
break
}
}
if j != 0 {
j--
tmpLen = 2 * (j+1)
if tmpLen > maxLen {
maxLen = tmpLen
pos = i-j
}
}
}
return s[pos: pos+maxLen]
}