第一题 实现 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. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
    第一项是数字 1
    形容前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
    形容前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
    形容前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
    形容前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
    要 形容 一个数字字符串，首先要将字符串宰割为 最小 数量的组，每个组都由间断的最多 雷同字符 组成。而后对于每个组，先形容字符的数量，而后形容字符，造成一个形容组。要将形容转换为数字字符串，先将每组中的字符数量用数字替换，再将所有形容组连接起来。

例如，数字字符串 "3322251" 的形容如下图：

示例 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<len(str){        c:=str[idx]        l:=idx        for j:=idx;j<len(str);j++{            if str[j]!=c{                break            }            l = j        }        n:=l-idx+1        res = append(res,byte(n)+'0')        res = append(res,c)        idx = l+1    }    return gen(string(res),n-1)}作者：hai-na-bai-chuan-11链接：https://leetcode-cn.com/problems/count-and-say/solution/jian-dan-di-gui-shi-xian-by-hai-na-bai-c-mrq4/起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

复杂度剖析

复杂度剖析

工夫复杂度：O(N×M)，其中 N 为给定的正整数M 为生成的字符串中的最大长度。

空间复杂度：O(M)。其中 M 为生成的字符串中的最大长度。

其余办法

https://leetcode-cn.com/probl...