leetcode刷题,使用python
1, 无重复字符的最长子串 —— 0003 字符串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 哈希集合，记录每个字符是否出现过
occ = set()
n = len(s)
# 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
rk, ans = -1, 0
for i in range(n):
if i != 0:
# 左指针向右移动一格，移除一个字符
occ.remove(s[i-1])
while rk + 1 < n and s[rk + 1] not in occ:
# 不断地移动右指针
occ.add(s[rk+1])
rk += 1
# 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1)
return ans
s = Solution()
print(s.lengthOfLongestSubstring("abcabcbb"))
print(s.lengthOfLongestSubstring("aabaab!bb"))
2, 最长回文子串—— 005字符串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
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]
s = Solution()
print(s.longestPalindrome("babad"))
3, z字形变换——0006 字符串
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：
输入：s = "A", numRows = 1
输出："A"
class Solution:
def convert(self, s: str, numRows: int) -> str:
n, r = len(s), numRows
if r == 1 or r >= n:
return s
t = r * 2 - 2
c = (n + t - 1) // t * (r - 1)
mat = [[''] * c for _ in range(r)]
x, y = 0, 0
for i, ch in enumerate(s):
mat[x][y] = ch
if i % t < r - 1:
x += 1 # 向下移动
else:
x -= 1
y += 1 # 向右上移动
return ''.join(ch for row in mat for ch in row if ch)
s = Solution()
ss = "PAYPALISHIRING"
numRows = 3
print(s.convert(ss, 3))
4, 字符串转换整数——0008 自动机
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
INT_MAX = 2**31 - 1
INT_MIN = -2**31
class Automaton:
def __init__(self):
self.state = 'start'
self.sign = 1
self.ans = 0
self.table = {
'start': ['start', 'signed', 'in_number', 'end'],
'signed': ['end', 'end', 'in_number', 'end'],
'in_number': ['end', 'end', 'in_number', 'end'],
'end': ['end', 'end', 'end', 'end'],
}
def get_col(self, c):
if c.isspace():
return 0
if c == '+' or c == '-':
return 1
if c.isdigit():
return 2
return 3
def get(self, c):
self.state = self.table[self.state][self.get_col(c)]
if self.state == 'in_number':
self.ans = self.ans * 10 + int(c)
self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
elif self.state == 'signed':
self.sign = 1 if c == '+' else -1
class Solution:
def myAtoi(self, str : str) ->int:
automaton = Automaton()
for c in str:
automaton.get(c)
return automaton.sign * automaton.ans
S = Solution()
str = "-43"
print(S.myAtoi(str))
5, 最长公共前缀——0014 纵向扫描 分治法
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
from typing import List
class Solution:
# 纵向扫描
def longestCommonPrefix(self, strs:List[str]) -> str:
if not strs:
return ""
length, count = len(strs[0]), len(strs)
for i in range(length):
c = strs[0][i]
for j in range(1, count):
if i==len(strs[j]) or strs[j][i] != c:
return strs[0][:i]
return strs[0]
# 分治
def longestCommonPrefix2(self, strs: List[str]) -> str:
def lcp(start, end):
if start == end:
return strs[start]
mid = (start+end) // 2
lcpLeft, lcpRight = lcp(start, mid), lcp(mid+1, end)
minLength = min(len(lcpLeft), len(lcpRight))
for i in range(minLength):
if lcpLeft[i] != lcpRight[i]:
return lcpLeft[:i]
return lcpLeft[:minLength]
return "" if not strs else lcp(0, len(strs)-1)
S = Solution()
strs = ["flower","flow","flight"]
print(S.longestCommonPrefix(strs))
print(S.longestCommonPrefix2(strs))
6, 电话号码的字母组合—— 0017 回溯法
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
from typing import List
class Solution:
def letterCombinations(self, digits:str)->List[str]:
if not digits:
return list()
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 letter in phoneMap[digit]:
combination.append(letter)
backtrack(index+1)
combination.pop()
combination = list()
combinations = list()
backtrack(0)
return combinations
S = Solution()
digits = "23"
print(S.letterCombinations(digits))
7, Find the Index of the First Occurrence in a String - 0028 KMP算法
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
# https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
class Solution:
def getNext(self, next, s):
j = -1
next[0] = j
for i in range(1, len(s)):
while j>=0 and s[i] != s[j+1]:
j = next[j]
if s[i] == s[j+1]:
j += 1
next[i] = j
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
next = [0] * len(needle)
self.getNext(next, needle)
j = -1
for i in range(len(haystack)):
while j>=0 and haystack[i] != needle[j+1]:
j = next[j]
if haystack[i] == needle[j+1]:
j += 1
if j == len(needle) - 1:
return i - len(needle) + 1
return -1
S = Solution()
haystack = "sadbutsad"
needle = "sad"
print(S.strStr(haystack, needle))
haystack = "leetcode"
needle = "leeto"
print(S.strStr(haystack, needle))
