02.字符串
# 01.有效的括号
# 事例1
输入:s = "()[]{}"
输出:true
# 事例2
输入:s = "(]"
输出:false
1
2
3
4
5
6
2
3
4
5
6
# 1.1 python
def isValid(s):
d = {
")": "(",
"]": "[",
"}": "{",
}
stack = []
for ch in s:
if ch in d: # 如果字符串是 右边括号
# 如果右括号和栈顶元素不能成对匹配,那么证明匹配失败,返回False
if not stack or stack[-1] != d[ch]:
return False
stack.pop() # 如果 栈顶元素 和 当前元素能够成对匹配,弹出栈顶元素
else:
stack.append(ch) # 如果是左侧括号,直接入栈
return not stack
s1 = "([]{})"
s2 = "([(])"
print(isValid(s1)) # True
print(isValid(s2)) # False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 1.2 golang
package main
import (
"fmt"
)
func isValid(s string) bool {
d := map[string]string{
")": "(",
"]": "[",
"}": "{",
}
stack := []string{}
for _,ch := range s {
strCh := string(ch)
v,ok := d[strCh]
if ok { // 如果字符串是 右边括号
// 如果右括号和栈顶元素不能成对匹配,那么证明匹配失败,返回False
if len(stack) == 0 || len(stack) >= 1 && stack[len(stack)-1] != v {
return false
} else {
stack = stack[:len(stack)-1] // 如果 栈顶元素 和 当前元素能够成对匹配,弹出栈顶元素
}
} else {
stack = append(stack, strCh) // 如果是左侧括号,直接入栈
}
}
return len(stack) == 0
}
func main() {
s := "{[()]}"
v := isValid(s)
fmt.Println(v) // true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 02.回文数
# 2.1 题目描述
给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。
输入:x = 121
输出:true
输入:x = -121
输出:false
1
2
3
4
2
3
4
# 2.2 python
- 方法1
def huiwen(x):
x = str(x) # 将数字转换为字符串
left, right = 0, len(x) - 1 # 左右两个指针分别指向字符串两端
while left < right and x[left] == x[right]: # 左右指针未相遇且值相等就继续循环
left = left + 1
right = right - 1
# 跳出循环 left == right 证明为奇数回文, x[left] == x[right]为偶数回文,否则不是回文
return left == right or x[left] == x[right]
print( huiwen(121) ) # True
print( huiwen(-121) ) # False
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 2.3 golang
package main
import (
"fmt"
"strconv"
)
func isPalindrome(x int) bool {
s := strconv.Itoa(x) // 将数字转换为字符串
left, right := 0, len(s) - 1 // 左右两个指针分别指向字符串两端
for left < right && s[left] == s[right] { // 左右指针未相遇且值相等就继续循环
left = left + 1
right = right - 1
}
// 跳出循环 left == right 证明为奇数回文, x[left] == x[right]为偶数回文,否则不是回文
return left == right || s[left] == s[right]
}
func main() {
x := 121
v := isPalindrome(x)
fmt.Println(v) // true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 03.字符串相加
# 3.1题目描述
- 给定两个字符串形式的非负整数
num1
和num2
,计算它们的和 - 计算进位:
- 计算 carry = tmp // 10,代表当前位相加是否产生进位;
- 添加当前位:
- 计算 tmp = n1 + n2 + carry,并将当前位 tmp % 10 添加至 res 头部;
- 索引溢出处理:
- 当指针 i或j 走过数字首部后,给 n1,n2 赋值为 0,相当于给 num1,num2 中长度较短的数字前面填 0,以便后续计算。
- 当遍历完 num1,num2 后跳出循环,并根据 carry 值决定是否在头部添加进位 1,最终返回 res 即可。
"1234" "123" ==> "1357"
1
# 3.2 python
def addStrings(num1, num2):
res = ""
# 设定 i,j 两指针分别指向 num1,num2 尾部, 两数相加进位为0
i, j, carry = len(num1) - 1, len(num2) - 1, 0
while i >= 0 or j >= 0:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
tmp = n1 + n2 + carry
carry = tmp // 10 # 进位
res = str(tmp % 10) + res # 取余就是当前位的值,并加入字符串右面
i, j = i - 1, j - 1 # 指针向右移动一位
if carry: # 如果循环结束还存在井位,在头部添加进位 1
res = '1' + res
return res
print( addStrings("1234", "123") ) # "1357"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 3.3 golang
package main
import (
"fmt"
"strconv"
)
func addStrings(num1 string, num2 string) string {
res := ""
i,j,carry := len(num1)-1, len(num2)-1, 0 // 设定 i,j 两指针分别指向 num1,num2 尾部, 两数相加进位为0
for i >= 0 || j >= 0{ // 只要两个数字有一个没有遍历完就继续循环
n1, n2 := 0, 0 // 当前字符串遍历完了值为0,否则为当前遍历的值
if i >= 0 { // i指针大于0,证明还没遍历完,就使用当前遍历的值
n1,_ = strconv.Atoi(string(num1[i]))
}
if j >= 0 {
n2,_ = strconv.Atoi(string(num2[j]))
}
tmp := n1 + n2 + carry
carry = tmp / 10 // 井位
res = strconv.Itoa(tmp % 10) + res // 取余就是当前位的值,并加入字符串右面
i, j = i - 1, j - 1 // 指针向右移动一位
}
if carry > 0 {
res = "1" + res
}
return res
}
func main() {
num1 := "123"
num2 := "123"
v := addStrings(num1, num2) // 246
fmt.Println(v)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 04.最长公共前缀
# 4.1 题目描述
- 最长公共前缀 (opens new window)
- 编写一个函数来查找字符串数组中的最长公共前缀。
- 如果不存在公共前缀,返回空字符串
""
。
输入:strs = ["flower","flow","flight"]
输出:"fl"
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
1
2
3
4
5
6
2
3
4
5
6
# 4.2 python
- 标签:链表
- 当字符串数组长度为 0 时则公共前缀为空,直接返回
- 令最长公共前缀 ans 的值为第一个字符串,进行初始化
- 遍历后面的字符串,依次将其与 ans 进行比较,两两找出公共前缀,最终结果即为最长公共前缀
- 如果查找过程中出现了 ans 为空的情况,则公共前缀不存在直接返回
- 时间复杂度:O(s),s 为所有字符串的长度之和
def longest(strs):
first = strs[0] # 令最长公共前缀 ans 的值为第一个字符串,进行初始化
for i in range(1,len(strs)):
j = 0
# 遍历后面的字符串,依次将其与 ans 进行比较,两两找出公共前缀,最终结果即为最长公共前缀
while j < len(first) and j < len(strs[i]):
if first[j] != strs[i][j]:
break
j = j+1
# 如果查找过程中出现了 ans 为空的情况,则公共前缀不存在直接返回
if j == 0:
return ""
first = strs[0][:j]
return first
strs = ["flower","flow","flight"]
print( longest(strs) ) # fl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 2.3 golang
package main
import (
"fmt"
)
func longestCommonPrefix(strs []string) string {
// 令最长公共前缀 ans 的值为第一个字符串,进行初始化
first := strs[0]
for i := 1; i < len(strs); i++ {
j := 0
// 遍历后面的字符串,依次将其与 ans 进行比较,两两找出公共前缀,最终结果即为最长公共前缀
for j < len(first) && j < len(strs[i]) {
if first[j] != strs[i][j]{
break
}
j = j + 1
}
first = strs[0][:j]
}
return first
}
func main() {
strs := []string{"flower","flow","flight"}
v := longestCommonPrefix(strs)
fmt.Println(v) // fl
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 05.实现 strStr()
# 5.1 题目描述
给定一个 haystack 字符串和一个 needle字符串
在 haystack 字符串中找出needle字符串出现的第一个位置 (从0开始)。
如果不存在,则返回 -1。
# 示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
# 示例 2:
输入: haystack = "aaaaa", needleneedle = "bba"
输出: -1
1
2
3
4
5
6
7
2
3
4
5
6
7
# 5.2 python
- 暴力破解
def strStr(haystack, needle):
L, n = len(needle), len(haystack) # L短字符串长度,n长字符串长度
for start in range(n - L + 1):
if haystack[start: start + L] == needle:
return start
return -1
print( strStr( '', '' ) ) # 0
print( strStr( 'hello', 'll' ) ) # 2
print( strStr( 'aaaaa', 'bba' ) ) # -1
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 5.3 golang
package main
import (
"fmt"
)
func strStr(haystack string, needle string) int {
L,n := len(needle), len(haystack) // L短字符串长度,n长字符串长度
for start :=0; start < n-L+1; start++ { // 从长字符串的开始位置依次与短字符串比较
if haystack[start: start + L] == needle {
return start
}
}
return -1
}
func main() {
haystack := "hello"
needle := "ll"
v := strStr(haystack, needle)
fmt.Println(v) // 2
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 06.反转字符串中的单词 III
# 6.1 题目描述
给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
输入:"Let's take LeetCode contest"
输出:"s'teL ekat edoCteeL tsetnoc"
1
2
2
# 6.2 python
利用栈的先进后出的结构很容易做到字符反转
但一串英文单词中,单词的个数总是比空格的字数多一个,在处理的时候很不方便
- 如:wordA(空格)wordB(空格)wordC
- 我们不妨在原字符串末尾补充一个空格,让每一小节都变成“单词+空格”
- 遇见空格就是我们判断出栈的前提条件
- 于是我们只要利用切片返回第一个字符后面的string就可以了
def reverseWords(s):
stack = [] # 使用列表模拟栈
new_s = "" # new_s 新字符串
s = s + " " # 原字符串末尾补充一个空格,让每一小节都变成“单词+空格”
for i in s:
stack.append(i) # 只要没有遇到空格就依次进栈
if i == " ": # 如果遇到空格依次出栈,这样就实现了反转
while(stack):
new_s += stack.pop()
return new_s[1:]
print( reverseWords( "I love you" ) ) # I evol uoy
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 6.3 方法2:利用字符串切片
def reverseWords(s):
s = s[::-1] # uoy evol I
s = s.split() # ['uoy', 'evol', 'I']
s.reverse() # ['I', 'evol', 'uoy']
s = " ".join(s) # I evol uoy
return s
print( reverseWords( "I love you" ) ) # I evol uoy
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 6.4 golang
package main
import (
"fmt"
)
func reverseWords(s string) string {
stack := []string{} // 使用切片模拟栈
new_s := "" // new_s 新字符串
s = s + " " // 原字符串末尾补充一个空格,让每一小节都变成“单词+空格”
for _,i := range s {
strI := string(i)
stack = append(stack, strI) // 只要没有遇到空格就依次进栈
if strI == " " { // 如果遇到空格依次出栈,这样就实现了反转
for j := len(stack)-1; j >= 0; j-- {
new_s += string((stack[j]))
}
stack = []string{} // 将栈清空
}
}
return new_s[1:]
}
func main() {
s := "I love you"
v := reverseWords(s)
fmt.Println(v) // I evol uoy
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 07.二进制求和
# 7.1 题目描述
- 二进制求和 (opens new window)
- 给你两个二进制字符串,返回它们的和(用二进制表示)。
- 输入为 非空 字符串且只包含数字
1
和0
。
输入: a = "11", b = "1"
输出: "100"
输入: a = "1010", b = "1011"
输出: "10101"
1
2
3
4
2
3
4
# 7.2 python
- 将长度较小的字符串定义为b;
- 二进制字符表示为"1110"的形式,即需要从后向前对其进行索引遍历;
- 每一轮需要更新res和进位carry;
- 依次遍历b,再遍历a。
- 并且在最后的返回时,查看是否还有carry进位没有使用到。
def addBin(num1,num2):
i,j = len(num1)-1, len(num2)-1 # 设定 i,j 两指针分别指向 num1,num2 尾部
carry = 0 # 两数相加进位为0
ret = '' # 结果
while i >= 0 or j>=0:
n1 = int(num1[i]) if i>=0 else 0
n2 = int(num2[j]) if j>=0 else 0
tmp = n1 + n2 + carry
ret = str(tmp%2) + ret # 取余 就是当前位的值,并加入字符串右面
carry = tmp // 2 # 井位
i,j = i-1,j-1 # 指针向右移动一位
if carry: # 如果循环结束还存在井位,在头部添加进位 1
ret = '1' + ret
return ret
print( addBin('11','10') ) # '101' =》 5
# '11' =》3 '10' =》2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 7.2 golang
package main
import (
"fmt"
"strconv"
)
func addBinary(a string, b string) string {
i,j := len(a)-1, len(b) - 1 // 设定 i,j 两指针分别指向 num1,num2 尾部
carry := 0 // 两数相加进位为0
ret := ""
for i >= 0 || j >= 0 {
n1, n2 := 0,0
if i>=0 {
n1,_ = strconv.Atoi(string(a[i]))
}
if j>=0 {
n2,_ = strconv.Atoi(string(b[j]))
}
tmp := n1 + n2 + carry
ret = strconv.Itoa(tmp % 2) + ret // 取余 就是当前位的值,并加入字符串右面
carry = tmp / 2 // 井位
i,j = i-1, j-1 // 指针向右移动一位
}
if carry > 0{ // 如果循环结束还存在井位,在头部添加进位 1
ret = "1" + ret
}
return ret
}
func main() {
a := "1010"
b := "1011"
v := addBinary(a, b)
fmt.Println(v) // 10101
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 08.最长回文串
# 8.1 题目描述
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如
"Aa"
不能当做一个回文字符串。
输入: "abccccdd
输出: 7
解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
1
2
3
2
3
# 8.2 python
- 对于每个字符,假设它出现了
v
次,我们可以使用该字符v / 2 * 2
次 - 比如 v=5 那么
5 / 2 * 2 = 4
def longestStr(s):
d = {} # 使用字典记录每个字符串出现的次数
for k in s:
if d.get(k) is None: # 如果字符串第一次出现,设置次数为1
d[k] = 1
else:
d[k] = d[k] + 1 # 如果已经记录过,就将出现次数加一
tag = False
ret = 0
for v in d.values():
if v % 2 ==1: # 获取当前字符串出现次数是否存在计算个,奇数个可以有一个放到中间也是回文
tag = True
ret = ret + v // 2 * 2
return ret+1 if tag else ret
s = 'abcccccdd'
print( longestStr(s) ) # 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 8.3 golang
package main
import (
"fmt"
)
func longestPalindrome(s string) int {
d := map[string]int{} // 使用字典记录每个字符串出现的次数
for _,v := range s {
sStr := string(v)
_,ok := d[sStr]
if !ok { // 如果字符串第一次出现,设置次数为1
d[sStr] = 1
}else {
d[sStr] += 1 // 如果已经记录过,就将出现次数加一
}
}
tag := false
ret := 0
for _,v := range d {
if v % 2 == 1 { // 获取当前字符串出现次数是否存在计算个,奇数个可以有一个放到中间也是回文
tag = true
}
ret = ret + v / 2 * 2
}
if tag { // 如果存在奇数个,最大回文数加一
ret = ret + 1
}
return ret
}
func main() {
s := "abccccdd"
v := longestPalindrome(s)
fmt.Println(v) // 7
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 09.字符串压缩
# 9.1 题目描述
- 字符串压缩,利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。
- 若“压缩”后的字符串没有变短,则返回原先的字符串。
- 你可以假设字符串中只包含大小写英文字母(a至z)。
输入:"aabcccccaaa"
输出:"a2b1c5a3"
输入:"abbccd"
输出:"abbccd"
解释:"abbccd"压缩后为"a1b2c2d1",比原字符串长度更长。
1
2
3
4
5
6
2
3
4
5
6
# 9.2 python
- 我们从左往右遍历字符串,用 ch记录当前要压缩的字符,cnt记录 ch出现的次数
- 如果当前枚举到的字符 s[i]等于ch,我们就更新 cnt的计数,即
cnt = cnt + 1
- 否则我们按题目要求将 ch以及cnt 更新到答案字符串ans 里,即
ans = ans + ch + cnt
,完成对 ch字符的压缩 - 随后更新 ch为 s[i],cnt 为 1,表示将压缩的字符更改为 s[i]
- 在遍历结束之后,我们就得到了压缩后的字符串ans,并将其长度与原串长度进行比较。
- 如果长度没有变短,则返回原串,否则返回压缩后的字符串。
def compressString(S):
ch = S[0] # ch记录当前要压缩的字符
ans = '' # ans拼接新字符串
cnt = 0 # cnt记录 ch出现的次数
for c in S:
if c == ch: # 当前枚举到的字符 s[i]等于ch,就加一
cnt += 1
else: # 否则我们按题目要求将 ch以及cnt 更新到答案字符串ans 里
ans += ch + str(cnt) # `ans = ans + ch + cnt`,完成对 ch字符的压缩
ch = c
cnt = 1
ans += ch + str(cnt) # 跳出for循环后更新最后一部分
return ans if len(ans) < len(S) else S
s = "aabcccccaaa"
print( compressString(s) ) # a2b1c5a3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 9.3 golang
package main
import (
"fmt"
"strconv"
)
func compressString(S string) string {
if len(S) <= 1 {
return S
}
ch := string(S[0]) // ch记录当前要压缩的字符
ans := "" // ans拼接新字符串
cnt := 0 // cnt记录 ch出现的次数
for _,c := range S {
strC := string(c)
if strC == ch { // 当前枚举到的字符 s[i]等于ch,就加一
cnt += 1
}else { // 否则我们按题目要求将 ch以及cnt 更新到答案字符串ans 里
ans += ch + strconv.Itoa(cnt) // `ans = ans + ch + cnt`,完成对 ch字符的压缩
ch = strC
cnt = 1
}
}
ans += ch + strconv.Itoa(cnt)
if len(S) > len(ans) {
S = ans
}
return S
}
func main() {
S := "aabcccccaaa"
v := compressString(S)
fmt.Println(v) // a2b1c5a3
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 10.反转字符串
# 10.1 python
'''第一种:使用字符串切片'''
s = 'Hello World'
print(s[::-1]) # dlroW olleH
'''第二种:使用列表的reverse方法'''
l = list(s)
l.reverse()
print( "".join(l) ) # dlroW olleH
'''第三种:使用reduce'''
from functools import reduce
result = reduce(lambda x,y:y+x,s)
print( result ) # dlroW olleH
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 10.2 golang
package main
func Reverse(s string) string {
r := []rune(s)
for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r)
}
func main() {
a := "Hello, Wrold"
println(Reverse(a)) // dlorW ,olleH
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 11.统计单词次数
- 统计指定文件中单词出现数量,并找到出现次数最多的前无个
import re
def wordCount(path,n):
d = {}
with open(path, encoding="utf-8") as f:
data = f.read()
# words = ['version', '3', 'services', .... ]
words = [s.lower() for s in re.findall("\w+", data)]
for word in words:
d[word] = d.get(word, 0) + 1
return sorted(d.items(), key=lambda item: item[1], reverse=True)[:n]
if __name__ == '__main__':
pt = r'C:\tmp\drf_demo\book\models.py'
most_common_5 = wordCount(pt,5)
print(most_common_5) # [('mysql', 5), ('root', 3), ('db', 3), ('environment', 2), ('3306', 2)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 12.最长子串
# 12.1 题目要求
- 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度
- 以(a)bcabcbb 开始的最长字符串为 (abc)abcbb;
- 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
- 以 ab(c)abcbb开始的最长字符串为ab(cab)cbb
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3
1
2
3
2
3
# 12.2 python
- 我们使用两个指针表示字符串中的某个子串(或窗口)的左右边界
- 在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置
- 然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符
- 在移动结束后,这个子串就对应着 以左指针开始的,不包含重复字符的最长子串
- 我们记录下这个子串的长度;
s = "abcabcbb"
def longestSubstring(s):
occ = set() # 哈希集合,记录每个字符是否出现过
n = len(s)
result = 0 # 记录最大子串长度
for L in range(n):
R = L
# 字符串遍历完成或者出现重复字符串结束
while R < n and s[R] not in occ:
occ.add(s[R])
R += 1 # 不断地移动右指针
occ = set()
result = max(result, R - L)
return result
r = longestSubstring(s)
print(r) # 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 12.3 golang
package main
func lengthOfLongestSubstring(s string) int {
occ := map[string]bool{} // 哈希集合,记录每个字符是否出现过
n := len(s)
result := 0 // 记录最大子串长度
for L := 0; L < n; L++ {
R := L
for R < n {
strC := string(s[R])
_,ok := occ[strC]
if ok { // 字符串遍历完成或者出现重复字符串结束
break
}
occ[strC] = true
R += 1 // 不断地移动右指针
}
occ = map[string]bool{}
if R - L > result { // 比较获取新的最大子串长度
result = R - L
}
}
return result
}
func main() {
s := "abcabcbb"
println(lengthOfLongestSubstring(s)) // 3
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 13.最长回文子串
# 13.1 题目要求
给你一个字符串 s,找到 s 中最长的回文子串。
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
1
2
3
2
3
# 13.2 python:中心扩散法
- 本题最容易想到的一种方法应该就是 中心扩散法
- 从每一个位置出发,向两边扩散即可,遇到不是回文的时候结束
class Solution:
def subscript(self, s, left, right):
# 左指针大于等于0,右指针小于字符串长度,并且左右对称位置“值”相等,就继续循环
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
def longestString(self, s):
start, end = 0, 0 # 最开始,初始化左右位置都为 0号位置
for i in range(len(s)):
left1, right1 = self.subscript(s, i, i) # 第一个字符串找左右下标
left2, right2 = self.subscript(s, i, i + 1) # 第二个字符串找左右下标
if right1 - left1 > end - start:
start, end = left1, right1
if right2 - left2 > end - start:
start, end = left2, right2
return s[start: end + 1]
s = 'babad'
print(Solution().longestString(s))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 13.3 golang
package main
func longestPalindrome(s string) string {
start, end := 0, 0 // 最开始,初始化左右位置都为 0号位置
for i :=0; i < len(s); i++ {
left1, right1 := subscript(s, i, i) // 第一个字符串找左右下标
left2, right2 := subscript(s, i, i + 1) // 第二个字符串找左右下标
if right1 - left1 > end - start {
start, end = left1, right1
}
if right2 - left2 > end - start {
start, end = left2, right2
}
}
return s[start: end+1]
}
func subscript(s string, left, right int) (int, int) {
// 左指针大于等于0,右指针小于字符串长度,并且左右对称位置“值”相等,就继续循环
for left >= 0 && right < len(s) && s[left] == s[right] {
left -= 1
right += 1
}
return left+1, right-1
}
func main() {
s := "babad"
println(longestPalindrome(s)) // bab 或 aba
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10