字符串

3. 无重复字符的最长子串 💯

3. 无重复字符的最长子串

# 这道题主要用到思路是：滑动窗口

# 什么是滑动窗口？

# 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

# 如何移动？

# 我们只要把队列的左边的元素移出就行了，直到满足题目要求！

# 一直维持这样的队列，找出队列出现最长的长度时候，求出解！

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        window = set()
        cur_len = 0
        max_len = 0
        for i in range(len(s)):
            cur_len += 1
            while s[i] in window:
                window.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:
                max_len = cur_len
            window.add(s[i])
        return max_len

    def lengthOfLongestSubstring2(self, s: str) -> int:
        left = 0
        right = 0
        res = 0
        window = dict()
        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1

            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1

            res = max(res, right - left + 1)

            right += 1
        return res

    def lengthOfLongestSubstring3(self, s):
        left, right = 0, 0
        charset = set()
        res = 0
        while left < len(s) and right < len(s):
            if s[right] in charset:
                if s[left] in charset:
                    charset.remove(s[left])
                left += 1
            else:
                charset.add(s[right])
                right += 1
                res = max(res, len(charset))
        return res

5. 最长回文子串

最长回文子串

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True

        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break

                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]

125. 验证回文串

125. 验证回文串

# 描述：给定一个字符串 s。

# 要求：判断是否为回文串（只考虑字符串中的字母和数字字符，并且忽略字母的大小写）。

class Solution:
    # 双指针
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        while left < right:
            if not s[left].isalnum():
                left += 1
                continue
            if not s[right].isalnum():
                right -= 1
                continue

            if s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            else:
                return False
        return True

    def isPalindrome2(self, s: str) -> bool:
        s1 = "".join(ch.lower() for ch in s if ch.isalnum())
        return s1 == s1[::-1]

151. 反转字符串中的单词 💯

反转字符串中的单词

class Solution:
    # 移除多余空格
    def trim(self, s):
        left = 0
        right = len(s) - 1
        while left <= right and s[left] == " ":
            left += 1
        while left <= right and s[right] == " ":
            right -= 1
        res = []
        while left <= right:
            if s[left] != " ":
                res.append(s[left])
            elif res[-1] != " ":
                res.append(s[left])
            left += 1
        return res

    # 翻转字符串数组
    def reverse(self, s, left, right):
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        return None

    # 翻转每个单词
    def reverse_each_word(self, l):
        start = 0
        end = 0
        n = len(l)
        while start < n:
            while end < n and l[end] != " ":
                end += 1
            self.reverse(l, start, end - 1)
            start = end + 1
            end += 1
        return None

    def reverseWords(self, s: str) -> str:
        l = self.trim(s)
        self.reverse(l, 0, len(l) - 1)
        self.reverse_each_word(l)
        return "".join(l)

344. 反转字符串 💯

反转字符串 【双指针】

# 使用两个指针 left，right。left 指向字符数组开始位置，right 指向字符数组结束位置。
# 交换 s[left] 和 s[right]，将 left 右移、right 左移。
# 如果遇到 left == right，跳出循环

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

class Solution:
    def reverseString(self, s):
        left = 0
        right = len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

    # 使用额外空间
    def reverseString2(self, s):
        res = []
        for i in range(len(s) - 1, -1, -1):
            res.append(s[i])
        return res

415. 字符串相加 💯

415. 字符串相加

# 描述：给定两个字符串形式的非负整数 num1 和num2。

# 要求：计算它们的和，并同样以字符串形式返回。

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        i = len(num1) - 1
        j = len(num2) - 1
        # 进位
        carry = 0
        while i >= 0 or j >= 0:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            tmp = n1 + n2 + carry
            carry = tmp // 10
            res = str(tmp % 10) + res
            i -= 1
            j -= 1
        return "1" + res if carry else res

# 用一个数组存储按位相加后的结果，每一位对应一位数。
# 然后分别使用一个指针变量，对两个数 num1、num2 字符串进行反向遍历，将相加后的各个位置上的结果保存在数组中，这样计算完成之后就得到了一个按位反向的结果。
# 最后返回结果的时候将数组反向转为字符串即可。

    def addStrings2(self, num1: str, num2: str) -> str:
        carry = 0
        res = []
        n1 = len(num1) - 1
        n2 = len(num2) - 1
        while carry > 0 or n1 >= 0 or n2 >= 0:
            num1_d = int(num1[n1]) if n1 >= 0 else 0
            num2_d = int(num2[n2]) if n2 >= 0 else 0
            n1 -= 1
            n2 -= 1
            num = num1_d + num2_d + carry
            res.append(str(num % 10))
            carry = num // 10

        return "".join(res[::-1])

459. 重复的子字符串

459. 重复的子字符串

# 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return True if s in (s + s)[1:-1] else False

541. 反转字符串 II

反转字符串 II

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        res = list(s)
        for i in range(0, len(res), k * 2):
            res[i:i + k] = reversed(res[i:i + k])
        return "".join(res)

    def reverseStr(self, s: str, k: int) -> str:
        def reverse_str(alist):
            left = 0
            right = len(alist) - 1
            while left < right:
                alist[left], alist[right] = alist[right], alist[left]
                left += 1
                right -= 1
            return alist

        res = list(s)
        for i in range(0, len(res), k * 2):
            res[i: i + k] = reverse_str(res[i: i + k])
        return "".join(res)

剑指 Offer 05. 替换空格

剑指 Offer 05. 替换空格

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for i in s:
            if i == " ":
                res.append("%20")
            else:
                res.append(i)
        return "".join(res)

剑指 Offer 58 - II. 左旋转字符串

剑指 Offer 58 - II. 左旋转字符串

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]

    def reverseLeftWords2(self, s: str, n: int) -> str:
        res = []
        for i in range(n, len(s)):
            res.append(s[i])
        for i in range(n):
            res.append(s[i])
        return "".join(res)