leetcode探索初级算法之字符串

1. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

# 反转字符串
# 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

# 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

# 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。


class Solution:
    def reverseString(self, s) -> None:
        s[:] = s[::-1]

2. 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

# 整数反转
# 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
# 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。


class Solution:
    def reverse(self, x: int) -> int:
        # 如果数字在-10到10的范围，直接返回原数字
        if -10 < x < 10:
            return x
        if x > 0:
            # 如果 x 为正数。直接反转
            x = int(str(x)[::-1])
        else:
            # 如果 x 为负数。去掉负号再反转
            x = - int(str(x)[:0:-1])
        # 判断是否溢出数字范围
        return x if -2 ** 31 < x < 2 ** 31 - 1 else 0

3. 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

# 字符串中的第一个唯一字符
# 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。


import collections


class Solution:
    def firstUniqChar(self, s: str) -> int:
        # 使用Python中自带的collections.Counter模块
        count = collections.Counter(s)
        # 遍历字符串
        for i in range(0, len(s)):
            # 如果出现次数为1，返回索引
            if count[s[i]] == 1:
                return i
        return -1

4. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

# 有效的字母异位词
# 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
import collections


class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # 使用Python中自带的collections.Counter模块
        count1 = collections.Counter(s)
        count2 = collections.Counter(t)
        if count1 == count2:
            return True
        else:
            return False

5. 验证回文字符串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

# 验证回文字符串
# 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
import re


class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 使用正则表达式，只要数字字符和字母，并小写
        s = ''.join(re.findall('[a-zA-Z0-9]', s)).lower()
        # 第一种解决方法，直接判断是否等于转置字符串
        # return s == s[::-1]
        # 第二种解决方法
        # 使用两个游标
        h, t = 0, len(s) - 1
        # 只要头游标小于尾游标
        while h <= t:
            if s[h] == s[t]:
                h += 1
                t -= 1
            else:
                return False
        return True

6. 字符串转换整数 (atoi)

本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

# 字符串转换整数 (atoi)
# 本题中的空白字符只包括空格字符 ' ' 。
# 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。


class Solution:
    def myAtoi(self, str: str) -> int:
        s = str.strip()
        if not len(s):
            return 0
        if s[0] not in ["+", "-"] and not s[0].isdigit():
            return 0
        res = s[0]
        for value in s[1:]:
            if not value.isdigit():
                break
            res += value
        if res == '+' or res == '-':
            return 0
        res = int(res)
        if res < -2 ** 31:
            return -2 ** 31
        elif res > 2 ** 31 - 1:
            return 2 ** 31 - 1
        else:
            return res

7. 实现 strStr() 函数

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
当 needle 是空字符串时我们应当返回 0 。

# 实现 strStr() 函数。
# 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
# 当 needle 是空字符串时我们应当返回 0 。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 如果needle是空字符串，返回0
        if needle == '':
            return 0
        m, n = len(haystack), len(needle)
        for i in range(m - n + 1):
            if haystack[i:i + n] == needle:
                return i
        else:
            return -1

8. 外观数列

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
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（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。

# 外观数列
# 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
#
# 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（1 ≤ n ≤ 30），输出外观数列的第 n 项。
#
# 注意：整数序列中的每一项将表示为一个字符串。


class Solution:
    def countAndSay(self, n: int) -> str:
        res = "1"
        for i in range(n - 1):
            res = self.getNext(res)
        return res

    def getNext(self, res):
        index, next_seq = 0, ""
        while index < len(res):
            count = 1
            while index < len(res) - 1 and res[index] == res[index + 1]:
                count += 1
                index += 1
            next_seq += str(count) + res[index]
            index += 1

        return next_seq

9. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

# 最长公共前缀
# 编写一个函数来查找字符串数组中的最长公共前缀。
#
# 如果不存在公共前缀，返回空字符串 ""。


class Solution:
    def longestCommonPrefix(self, strs):
        # 如果长度为0 ，返回空字符串
        if len(strs) == 0:
            return ''
        # 如果长度为1，返回第一个元素
        if len(strs) == 1:
            return strs[0]
        # 只需判断最长和最短的字符号串
        a = min(strs)
        b = max(strs)
        # 遍历最短的字符串
        for i in range(len(a)):
            if a[i] != b[i]:
                return a[:i]
        return a