【golang】leetcode初级-实现|【golang】leetcode初级-实现 strStr()&外观数列
第一题 实现 strStr()
题目信息
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回-1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
示例 3：
输入：haystack = "", needle = ""
输出：0
提示：
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成
相关标签
双指针
字符串
字符串匹配
解题思路
首先想到的当然是最暴力的解法，遍历haystack字符串，每当读到字符与needle首字符相同的则将其后续与needle进行一次比较，直到haystack的剩余长度小于needle为止。
然而，该算法时间复杂度较高，还有很多可优化的空间
这里我们引入KPM算法
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
代码
暴力解法
func strStr(haystack, needle string) int {
n, m := len(haystack), len(needle)
outer:
for i := 0;
i+m <= n;
i++ {
for j := range needle {
if haystack[i+j] != needle[j] {
continue outer
}
}
return i
}
return -1
}作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。kmp算法
func strStr(haystack, needle string) int {
n, m := len(haystack), len(needle)
if m == 0 {
return 0
}
pi := make([]int, m)
for i, j := 1, 0;
i < m;
i++ {
for j > 0 && needle[i] != needle[j] {
j = pi[j-1]
}
if needle[i] == needle[j] {
j++
}
pi[i] = j
}
for i, j := 0, 0;
i < n;
i++ {
for j > 0 && haystack[i] != needle[j] {
j = pi[j-1]
}
if haystack[i] == needle[j] {
j++
}
if j == m {
return i - m + 1
}
}
return -1
}作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。复杂度分析
暴力解法
复杂度分析
时间复杂度：O(n×m)，其中 n 是字符串 haystack 的长度，m 是字符串 needle 的长度。最坏情况下我们需要将字符串 needle 与字符串haystack 的所有长度为 m 的子串均匹配一次。
空间复杂度：O(1)。我们只需要常数的空间保存若干变量。
KMP解法
复杂度分析
时间复杂度：O(n+m)，其中 n 是字符串 haystack 的长度，m 是字符串 needle 的长度。我们至多需要遍历两字符串一次。
空间复杂度：O(m)，其中 m 是字符串 needle 的长度。我们只需要保存字符串 needle 的前缀函数。
运行结果
文章图片
文章图片
我们可以看到
KPM算法大大优化了时间复杂度
第二题 外观数列 题目信息
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
- 1
- 11
- 21
- 1211
- 111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
文章图片
示例 1：
输入：n = 1
输出："1"
解释：这是一个基本样例。
示例 2：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示：
1 <= n <= 30
解题思路
简简单单一个递归函数解决问题
写个求第n项的函数，参数为第n-1项返回的字符串
代码
func countAndSay(n int) string {
return gen("1",n-1)
}func gen(str string,n int) string{
if n==0{
return str
}idx:=0
res:=[]byte{}
for idx复杂度分析
复杂度分析
时间复杂度：O(N×M)，其中 N 为给定的正整数M 为生成的字符串中的最大长度。
空间复杂度：O(M)。其中 M 为生成的字符串中的最大长度。
其他方法
【【golang】leetcode初级-实现|【golang】leetcode初级-实现 strStr()&外观数列】https://leetcode-cn.com/probl...
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长