LeetCode中级算法-数组和字符串（2）
无重复字符的最长字串
[题目]
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
[输入1]
s = "abcabcbb"[返回1]
3 "bcb"[输入2]
s = "bbbbb"[返回2]
1 "b"[解法]
使用双指针，同时从字符串的开始位置向后移动，慢指针遍历字符串中第i个元素的时候，快指针向后推进，直到发现一个已经遍历过的字符，则停下来，此时快慢指针之间的字符串的没有重复的，快指针继续向前移动，子字符串中就会有重复字符，此时移动一位慢指针，之后快指针继续推进，这样遍历完整个字符串，就可以找到最长的无重复子字符串，时间复杂度为O(2N) = O(N)。
[代码实现]
package main
import "fmt"
func main() {
input := "pwwkew"
resItem, resLen := computeResult(input)
fmt.Println("result:", resItem, resLen)
}
func computeResult(input string) (string, int) {
index := 0
filter := map[byte]int {}
maxLen := 0
maxStr := ""
for i := 0; i < len(input); i++ {
for index < len(input) - 1 {
fmt.Println(i, index, string(input[index + 1]))
if _, exists := filter[input[index + 1]]; exists {
delete(filter, input[i])
break
} else {
index++
filter[input[index]] = 1
}
}
currLen := index - i + 1
maxLen = Max(maxLen, currLen)
if currLen == maxLen {
maxStr = string(input[i: index + 1])
}
}
return maxStr, maxLen
}
func Max(a int,b int) int {
if a > b {
return a
}
return b
}最长回文子串
[题目]
给定一个字符串 s，找到 s 中最长的回文子串。
[输入1]
s = "babad"[返回1]
"bab"[输入2]
s = "cbbd"[返回2]
"bb"[解法]
使用“中心扩散法”，遍历字符串中的第i个字母，以第i个字母为中心设置两个指针，同时向左向右移动，直到左右指针指向的字符不同，两个指针之间的子字符串是回文字符串。需要注意的是，回文字符串的中心点有可能是两个甚至多个相同的字符，因为在设置左右指针前，需要寻找到回文字符串最大的中心。
[代码实现]
package main
import "fmt"
// 给定一个字符串 s，找到 s 中最长的回文子串。
func main() {
input := "babad"
result := computeResult(input)
fmt.Println("result:", result)
}
func computeResult(input string) string {
maxLen := 0
maxStr := ""
for i := 1; i < len(input) - 1; i++ {
left := i
right := i
// 保证当前位置i在真正匹配之前左边或者右边有与位置i上字母相同的
for left > 0 && right < len(input) - 1 {
if input[left - 1] == input[i] {
left--
} else if input[right + 1] == input[i] {
right++
} else {
break
}
}
// 循环比对left和right位置上的字母都相等
for left > 0 && right < len(input) - 1 && input[left - 1] == input[right + 1] {
left--
right++
}
currLen := right - left + 1
maxLen = Max(maxLen, currLen)
if maxLen == currLen {
maxStr = input[left:right + 1]
}
}
return maxStr
}
func Max(a int,b int) int {
if a > b {
return a
}
return b
}递增的三元子序列
[题目]
给定一个为排序的数组，判断这个数组中是否存在长度为3的递增子序列。
[输入1]
[1,2,3,4,5][返回1]
true[输入2]
[5,4,3,2,1][返回2]
false[解法]
遍历输入的数组，遍历第i个元素的时候，设置一个指针向后推移，并判断指针指向元素是否大于指针前一位元素，是则继续向后推进，否则从当前指针开始继续向后推移，在推移的的过程中计数最大长度的子序列。
[代码实现]
package main
import "fmt"
func main() {
input := []int {1,2,3,4,5}
//input := []int {5,4,3,2,1}
result := computeResult(input)
fmt.Println("result:", result)
}
func computeResult(input []int) bool {
index := 1
exists := false
for i := 0; i < len(input); i++ {
index = i + 1
if exists {
break
}
for index < len(input) {
if input[index - 1] < input[index] {
if index - i + 1 == 3 {
exists = true
break
}
index++
} else {
i = index
break
}
}
}
return exists
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-12-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
