Golang字符串注意点⚠️#
对字符串 range的时候，v并不是byte类型而是rune（底层为int32）
1
2
3
4
| s := "hello world"
for _, v := range s {
fmt.Printf("%c, %T", v, v)
}
|
字符串直接取某一位，比s[0]，类型为byte（底层为uint8）
1
2
3
4
| s := "hello world"
for i := 0; i < len(s); i++ {
fmt.Printf("%c, %T", s[i], s[i])
}
|
详细原理，见Go语言字符类型（byte和rune）
面试题 01.09. 字符串轮转#
字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。
示例1:
1
2
| 输入：s1 = "waterbottle", s2 = "erbottlewat"
输出：True
|
示例2:
1
2
| 输入：s1 = "aa", "aba"
输出：False
|
提示：
字符串长度在[0, 100000]范围内。
说明:
你能只调用一次检查子串的方法吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-rotation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
翻转之后的S2，拼接起来肯定是首位相连的，判断是否包含S1
1
2
3
4
5
6
7
| func isFlipedString(s1 string, s2 string) bool {
if len(s1) != len(s2) {
return false
}
return strings.Contains(s2+s2, s1)
}
|
自己实现Contains，用KMP算法
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
| func getNext(s string) []int {
next := make([]int,len(s))
next[0] = -1
i, j := 0,-1
for i< len(s)-1 {
if j==-1 || s[i]==s[j] {
i++
j++
next[i] = j
} else {
j = next[j]
}
}
return next
}
func KMPSearch(target string,text string) int {
i, j := 0, 0
next := getNext(target)
for ; j< len(text); {
if i==len(target)-1 && target[i]==text[j] {
return j-i
}
if j==-1 || target[i]==text[j] {
i++
j++
} else {
i = next[i]
}
}
return -1
}
|
415. 字符串相加#
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
注意：
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
通过次数27,747提交次数55,789
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
就是大数加法问题，每一位相加，保留个位，十位数进位（如有）
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
| func addStrings(num1 string, num2 string) string {
i, j := len(num1)-1, len(num2)-1
var t byte = 0 // 每一位相加结果
var ret []byte // 结果
for i >=0 || j >= 0 || t != 0 {
if i >= 0 {
// '9' - '0' = 9
t += num1[i]-'0'
i--
}
if j >= 0 {
t += num2[j]-'0'
j--
}
// 18%10 + '0' = 8
ret = append(ret, t%10+'0')
t /= 10 // 18 / 10 = 1
}
l := len(ret)-1
for i:=0; i <= l; i++ {
ret[i], ret[n] = ret[n], ret[i]
l--
}
return string(ret)
}
// 执行用时 :0 ms, 在所有 Go 提交中击败了100.0%的用户
// 内存消耗 :2.5 MB, 在所有 Go 提交中击败了80.49%的用户
|
187. 重复的DNA序列#
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。
示例：
1
2
| 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]
|
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-dna-sequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目意思是两次或以上的重复字串
窗口往前滑动窗口，用map计数，大于2时放入结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func findRepeatedDnaSequences(s string) []string {
if len(s) <= 10 {
return []string{}
}
// 辅助map和窗口｜最多有 len(s)-10+1 种情况
sub := make(map[string]int, len(s)-9)
// 11: 0-10/1-11
for i := 0; i < len(s)-9; i++ {
sub[s[i:i+10]]++
}
ret := []string{}
for k, v := range sub {
if v > 1 {
ret = append(ret, k)
}
}
return ret
}
// 执行用时 :16 ms, 在所有 Go 提交中击败了91.38%的用户
// 内存消耗 :7.2 MB, 在所有 Go 提交中击败了79.17%的用户
|
1209. 删除字符串中的所有相邻重复项 II#
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
本题答案保证唯一。
示例 1：
1
2
3
| 输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。
|
示例 2：
1
2
3
4
5
6
| 输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释：
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"
|
示例 3：
1
2
| 输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"
|
提示：
1 <= s.length <= 10^5
2 <= k <= 10^4
s 中只含有小写英文字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
栈节点分别存储 字符值val 和 字符数量num
遍历目标字符串s
- 栈空 或
栈顶.val != s[i] 入栈，否则 栈顶.num++ 栈顶.num = k 时 出栈
最后栈中的元素拼起来就是结果字符串
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
38
39
40
41
42
43
44
45
46
47
48
49
| // 删 pbbcggttciiippooaais 2
// bb pcggttciiippooaais
// gg pcttciiippooaais
// tt pcciiippooaais
// cc piiippooaais
// ii pippooaais
// pp piooaais
// oo piaais
// aa piis
// ii ps
type node struct {
val rune
num int
}
func removeDuplicates(s string, k int) string {
var stk []node
for _, v := range s {
if len(stk)==0 || stk[len(stk)-1].val != v {
stk = append(stk, &node{
val: v,
num: 1,
})
} else {
stk[len(stk)-1].num++
}
for len(stk) > 0 {
// 重复元素，出栈
if stk[len(stk)-1].num == k {
stk = stk[:len(stk)-1]
} else {
break
}
}
}
ret := make([]rune, 0, len(stk))
for _, v := range stk {
for v.num > 0 {
ret = append(ret, v.val)
v.num--
}
}
return string(ret)
}
// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :4.5 MB, 在所有 Go 提交中击败了100.00%的用户
|
14. 最长公共前缀#
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “"。
示例 1:
1
2
| 输入: ["flower","flow","flight"]
输出: "fl"
|
示例 2:
1
2
3
| 输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
|
说明:
所有输入只包含小写字母 a-z 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
先找出最短的字符串st（结果肯定是以这个为基准）
再用指针对 每一个字符串的第 k 位和 st的第k位进行对比，不同的时候就return
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
| func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
// 先找到最短的
min := math.MaxInt32
var st string
for _, v := range strs {
if len(v) < min {
min = len(v)
st = v
}
}
if len(st) == 0 {
return ""
}
for k := range st {
for j := 0; j < len(strs); j++ {
if strs[j][k] != st[k] {
return st[:k]
}
}
}
return st
}
|
Difficulty: 简单
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
1
2
3
4
5
| 输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
|
示例 2:
1
2
3
| 输入: "aba"
输出: False
|
示例 3:
1
2
3
4
5
| 输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
|
Solution 1#
Language: Go
模拟：
- 创建临时字符串tmp记录对比串，往主串前滑动。
- 对比成功就往前，否则把s[i]接到tmp后面
- 结果：“abaababaab” 不通过
- 原因：需要回溯，而不是不匹配就继续增加
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
| func repeatedSubstringPattern(s string) bool {
if len(s) < 2 {
return false
}
tmp := string(s[0])
i := 1
for i < len(s) {
if len(tmp)+i < len(s) {
if tmp != s[i:len(tmp)+i] {
i++
tmp = s[:i]
} else {
i += len(tmp)
}
}
if len(tmp)+i == len(s) {
if s[i:] == tmp {
return true
} else {
return false
}
}
if len(tmp)+i > len(s) {
return false
}
}
return true
}
// 执行用时 :4 ms, 在所有 Go 提交中击败了96.64%的用户
// 内存消耗 :6 MB, 在所有 Go 提交中击败了100.00%的用户
|
Solution 2#
思路：新建ss=s+s，把ss的首元素和尾元素去掉，剩下的部分如果还含有s，则返回true。
假设ss是由s重复N次而成， 则 s+s 则有子串s重复2N次，现在ss=Ns， S+S=2Ns 因此s在(s+s)[1:-1]中必出现一次以上
1
2
3
| func repeatedSubstringPattern(s string) bool {
return strings.Contains((s+s)[1:2*len(s)-1], s)
}
|
Difficulty: 简单
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
1
2
3
| canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
|
Solution#
创建字典，遍历magazine 记录 magazine 内字母的数目
遍历 ransomNote，每过一个字母就消耗字典内的一个计数。
计数 <1 或 不存在计数的时候返回false
Language: Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func canConstruct(ransomNote string, magazine string) bool {
if len(ransomNote) > len(magazine) {
return false
}
dic := make(map[byte]int, len(magazine))
for _, v := range magazine {
dic[byte(v)]++
}
for _, v := range ransomNote {
if v, ok := dic[byte(v)]; !ok || v < 1 {
return false
}
dic[byte(v)]--
}
return true
}
// 执行用时 :12 ms, 在所有 Go 提交中击败了65.64%的用户
// 内存消耗 :6.4 MB, 在所有 Go 提交中击败了50.00%的用户
|
