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

0%