乐趣区

关于golang:golangleetcode初级实现-strStr外观数列

jiezi

第一题 实现 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…

退出移动版