0%

leetcodeDay7

今日leetcode两题分别是实现strStr()和数数并说,系简单难度的字符串算法题

实现strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

解答

该题是字符串的模式匹配,简单的方法直接分别遍历字符串和子串然而一一对比就行了,简单粗暴

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func strStr(haystack string, needle string) int {
hLen := len(haystack)
nLen := len(needle)
if nLen > hLen {
return -1
} else if nLen == 0 {
return 0
}

for i := 0; i < hLen-nLen+1; i++ {
isStr := false
for j := 0; j < nLen; j++ {
if needle[j] != haystack[i+j] {
break
} else if j == nLen-1 {
isStr = true
}
}
if isStr {
return i
}
}
return -1
}

我用上述代码就顺利通过了…然而,解答该题真正应使用的算法应该是KMP算法,也是绝大多数文件编辑器的查找功能所使用的算法.该算法以后再议

数数并说

报数序列是指一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作 “one 1” (“一个一”) , 即 11。
11 被读作 “two 1s” (“两个一”), 即 21。
21 被读作 “one 2”, “one 1” (”一个二” , “一个一”) , 即 1211。

给定一个正整数 n ,输出报数序列的第 n 项。

注意:整数顺序将表示为一个字符串。

示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

解答

挺有意思的题,大致意思是一个数值型的字符串,算出该字符串连续数字的个数.例如”2222”,读出来就是”4个2”,那么答案输出就是”42”;再如”112441”,读出来是”2个1,1个2,2个4,1个1”,那么输出为”21122411”

该题是一个序列,第一项为”1”,然后每一项都是前一项的报数.那么我们不妨设两个函数,一个用来求报数,另外一个则通过循环求序列的每一项

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 countAndSay(n int) string {
res:="1"
for i:=2;i<=n;i++{
res=say(res)
}
return res
}

func say(s string) string {
sslice := make([]byte, 0)
tmp := s[0]
count := 0
for i := 0; i < len(s); i++ {
if s[i] == tmp {
count++
} else {
sslice = append(sslice, []byte(strconv.Itoa(count)+string(tmp))...)
tmp = s[i]
count = 1
}
if i == len(s)-1 {
sslice = append(sslice, []byte(strconv.Itoa(count)+string(tmp))...)
}
}
return string(sslice)
}

在字符串拼接这方面我做的似乎还是太冗余了…多次转换,一点也不优雅,不知道go语言有什么更简便的方法我没有学到,如果是python的话那简直无脑加就行了233