字符串

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

方法一：暴力解

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        n = len(s)
        # rk为左指针，ans为无重复子串长度
        rk, ans = -1, 0
        flag = 0    # 循环中无重复子串长度
        for i in range(n):
            rk = i
            flag = 0
            while rk < n and s[rk] not in occ:
                occ.add(s[rk])
                flag = flag + 1
                rk = rk + 1
            ans = flag if flag > ans else ans
            occ.clear()
        return ans

方法二：

每次循环没必要把集合里的元素全部删除，可以每次只删除上一轮循环的最左边结点

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        n = len(s)
        # rk为左指针，ans为无重复子串长度
        rk, ans = 0, 0
        flag = 0    # 循环中无重复子串长度
        for i in range(n):
            if i > 0:
                occ.remove(s[i - 1])
                flag = flag - 1
            while rk < n and s[rk] not in occ:
                occ.add(s[rk])
                rk = rk + 1
                flag = flag + 1
            ans = flag if flag > ans else ans
        return ans

4、最长回文子串

本题使用的动态规划的思想，也就是说只有 s[i+1:j-1]s[i+1:j−1] 是回文串，并且 ss 的第 ii 和 jj 个字母相同时，s[i:j]s[i:j] 才会是回文串。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:  # 如果字符串长为1
            return s
        
        max = 1
        left = 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):
                right = L + i - 1
                if right >= n:
                    break
                
                if s[i] != s[right]:
                    dp[i][right] = False
                else:
                    if right - i < 3:
                        dp[i][right] = True
                    else:
                        dp[i][right] = dp[i + 1][right - 1]

                if dp[i][right] and L > max:
                    max = L
                    left = i
        return s[left:left+max]

6、Z字形变换

使用二维矩阵进行模拟：

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        n = len(s)
        if numRows == 1 or numRows >= n:
            return s
        t = 2 * numRows - 2
        col = (n + t - 1) // t * (numRows - 1)
        matrix = [[''] * col for _ in range(numRows)]
        x, y = 0, 0
        for i, ch in enumerate(s):
            matrix[x][y] = ch
            if i % t < numRows - 1:
                x = x + 1
            else:
                x = x - 1
                y = y + 1
        ans = ''
        for i in range(numRows):
            for j in range(col):
                if matrix[i][j]:
                    ans = ans + matrix[i][j]

        return ans

7、字符串转换整数

class Solution:
    def myAtoi(self, s: str) -> int:
        flag = False
        if s == '':
            return 0
        for i, ch in enumerate(s):
            if ch != ' ':
                s = s[i:]
                break

        if s[0] == '-':
            flag = True
            s = s[1:]
        elif s[0] == '+':
            s = s[1:]
        a = 0
        ans = 0
        for i, ch in enumerate(s):
            if ch.isdigit() == False:
                break
            a = int(ch)
            ans = ans * 10 + a
        if flag:
            ans = -1 * ans
        if ans > 2 ** 31 - 1:
            return 2 ** 31 - 1
        elif ans < -(2 ** 31):
            return -(2 ** 31)
        else:
            return ans

14、最长公共前缀

想法为横向对比，按照列表顺序开始逐步算法前x个字符串的最长前缀，直至得到最终的最长前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        flag = strs[0]	# 前几个字符串的最长前缀
        a = ""	# 本字符串与flag的最长前缀
        ans = ""
        n = len(strs)
        if n == 1:	# 如果只有一个字符串，那就直接输出
            return strs[0]
        for i, s in enumerate(strs):
            if i == 0:	# 如果是第一个字符串那就跳过
                continue
            for j, ch in enumerate(s):	# 本字符串与flag进行比对
                if j < len(flag) and ch == flag[j]:
                    a = a + ch
                else:
                    break
            flag = a
            a = ""
            if i == n - 1:	# 如果是最后一个结点，那就是最终最长前缀了
                ans = flag
        return ans

17、电话号码的字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == '':
            return []

        phoneMap = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',   
        }
        
        def backtrack(index: int):	# 回溯
            if index == len(digits):
                combinations.append(''.join(combination))
            else:
                digit = digits[index]
                for ch in phoneMap[digit]:
                    combination.append(ch)
                    backtrack(index + 1)
                    combination.pop()

        combination = list()
        combinations = list()
        backtrack(0)

        return combinations

20、有效的括号

采用了栈的思想，将符号依次入栈进行判断

class Solution:
    def isValid(self, s: str) -> bool:
        stack = list()
        for ch in s:
            if ch == ')':
                if stack == []:
                    return False
                temp = stack.pop()
                if temp != '(':
                    return False
            elif ch == '}':
                if stack == []:
                    return False
                temp = stack.pop()
                if temp != '{':
                    return False
            elif ch == ']':
                if stack == []:
                    return False
                temp = stack.pop()
                if temp != '[':
                    return False
            else:
                stack.append(ch)
        if stack:
            return False
        return True

21、合并两个有序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode(0, None)
        temp = head
        first = list1
        second = list2
        while first and second:
            if first.val <= second.val:
                temp.next = first
                temp = temp.next
                first = first.next
            elif first.val > second.val:
                temp.next = second
                temp = temp.next
                second = second.next
        
        temp.next = first if first else second
        
        return head.next

22、括号生成

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                S.append('(')
                backtrack(S, left + 1, right)
                S.pop()
            if right < left:
                S.append(')')
                backtrack(S, left, right + 1)
                S.pop()
        backtrack([], 0, 0)
        return ans