二刷 leetcode（7）

左手的ㄟ右手 2022-05-20 01:51 149阅读 0赞

28. 实现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()][strStr] 以及 Java的 [indexOf()][indexOf] 定义相符。

代码展现几种方法：

class Solution:
        def strStr(self, haystack, needle):
            """
            :type haystack: str
            :type needle: str
            :rtype: int
            """
            # if needle == "":
            #     return 0
            # n = len(haystack)
            # m = len(needle)
            # for i in range(n):
            #     if haystack[i] == needle[0]:
            #         if i + m > n:
            #             return -1
            #         if haystack[i: i+m] == needle:
            #             return i
            # return -1
            
            #### 运用python函数的find方法
            return haystack.find(needle)

38. 报数

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

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"

代码：下面的那种是别人写的代码，有注释容易理解。

class Solution:
        def countAndSay(self, n):
            """
            :type n: int
            :rtype: str
            """
            sequence = [1]
            for _ in range(n-1):
                next = []
                for num in sequence:
                    if not next or next[-1] != num:
                        next += [1, num]
                    else:
                        next[-2] += 1
                sequence = next
                
            return "".join(map(str, sequence))

class Solution:  
        def countAndSay(self, n):  
            """  
            :type n: int  
            :rtype: str  
            """  
            b='1'   #将第一行的1换成字符类型，便于下一行的读出  
            for i in range (n-1):    #(n-1)是因为第一行不需要处理，直接可以读出  
                a,c,count=b[0],'',0   #a用来读取上一行的第一个字符，c用来存放读出的内容(char)，count用来统计  
                for j in b:     
                    if a==j:  
                        count+=1  
                    else:  
                        c+=str(count)+a   #注意一定要将count转换为字符型，否则两个数就会相加（变成数学公式）。  
                        a=j  
                        count=1  
                c+=str(count)+a  
                b=c  
            return b  
    
    sol = Solution()
    print(sol.countAndSay(3))

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 `""`。

示例 1:

输入: ["flower","flow","flight"]
    输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 `a-z` 。

代码：

class Solution:
        def longestCommonPrefix(self, strs):
            """
            :type strs: List[str]
            :rtype: str
            """
            #### the first method
            # if len(strs) == 0:
            #     return ""
            # mins = min(strs)
            # maxs = max(strs)
            # for i, char in enumerate(mins):
            #     if char != maxs[i]:
            #         return mins[:i]
            # return mins
            
            #### the second method
            if len(strs) == 0:
                return ""
            prefix = strs[0]
            for i in range(1, len(strs)):
                s = strs[i]
                while not s.startswith(prefix):
                    prefix = prefix[:-1]
            return prefix

python中startswith()函数的使用说明：

str.startswith(str, beg=0,end=len(string));

*  str -- 检测的字符串。
 *  strbeg -- 可选参数用于设置字符串检测的起始位置。
 *  strend -- 可选参数用于设置字符串检测的结束位置。

返回值：如果检测得到就返回True, 没有检测到就返回False.

[strStr]: https://baike.baidu.com/item/strstr/811469
[indexOf]: https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf%28java.lang.String%29