class Solution: def editDistance(self , str1: str, str2: str) -> int: n1 = len(str1) n2 = len(str2) dp = [[0 for _ in range(n1+1)] for _ in range(n2+1)] for i in range(1, n1+1): dp[0][i] = dp[0][i-1] + 1 for i in range(1, n2+1): dp[i][0] = dp[i-1][0] + 1 for i in range(1, n2+1): for j in range(1,...

class Solution: def restoreIpAddresses(self , s: str) -> List[str]: if len(s) < 4 or len(s) > 12: return None res = [] path = [] def backrack(idx): if len(path) == 4 and idx == len(s): res.append('.'.join(path)) return for i in range(1, 4): if idx+i > len(s): continue sub = s[idx:idx+i] ...

class Solution: def huiwen(self, A, i, j): while i >= 0 and j < len(A) and A[i] == A[j]: i -= 1 j += 1 return j - i - 1 def getLongestPalindrome(self , A: str) -> int: res = 1 for i in range(len(A) - 1): res = max(res, max(self.huiwen(A, i, i), self.huiwen(A, i, i+1))) return res 解题思路遍历字符串，...

class Solution: def build(self, l1, r1, l2, r2, pre, med): if l1 > r1 or l2 > r2: return None inRoot = med.index(pre[l1]) root = TreeNode(pre[l1]) left = inRoot - l2 root.left = self.build(l1+1, l1+left, l2, inRoot - 1, pre, med) root.right = self.build(l1+left+1, r1, inRoot+1, r2, pre, med) r...

class Solution: def solve(self , IP: str) -> str: # write code here if '.' in IP: ip = IP.split('.') for i in ip: if len(i) > 3 or len(i) < 1: return "Neither" if i[0] == '0' and i[-1] != '0': return "Neither" for j in i: if (not '0' <= j <='9'): return "Neith...

class Solution: def longestCommonPrefix(self , strs: List[str]) -> str: target = "" minL = 5001 # 找到最短的字符串 for i in strs: if len(i) < minL: minL = len(i) target = i while target: count = 0 for i in range(len(strs)): if target not in strs[i]: break else: count += 1 if count == len(str...

class Solution: def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]: for i in range(n): for j in range(i): mat[i][j], mat[j][i] = mat[j][i], mat[i][j] for i in range(n): mat[i].reverse() return mat 解题思路找规律可以发现，将矩阵顺时针旋转九十度等于先将矩阵转置，再将每一行翻转。复杂度时间复杂度为O（N^2）；空间复杂度为O（1）。

class Solution: def spiralOrder(self , matrix: List[List[int]]) -> List[int]: # write code here if len(matrix) == 0: return None left = 0 right = len(matrix[0]) - 1 up = 0 down = len(matrix) - 1 res = [] while left <= right and up <= down: for i in range(left, right+1): res.append(matrix[up...

class Solution: def solve(self , n: int, m: int, a: List[int]) -> List[int]: # write code here m = m% n a.reverse() b = a[:m] b.reverse() c = a[m:] c.reverse() a[:m] = b a[m:] = c return a 解题思路先整体翻转；再翻转左边的前m个元素；再翻转右边的n-m哥元素；最后将这两个子数组拼起来，得到最终的结果。复杂度时间复杂度为O（N）空间复杂度为O（N）。

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 计算成功举办活动需要多少名主持人 # @param n int整型 有n个活动 # @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间 # @return int整型 # class Solution: def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int: start = [] end = [] f...

class Solution: def candy(self , arr: List[int]) -> int: # write code here candy = [1 for _ in range(len(arr))] for i in range(1, len(arr)): if arr[i-1] < arr[i]: candy[i] = candy[i-1]+1 res = candy[-1] i = len(arr) - 2 while i >= 0: if arr[i] > arr[i+1] and candy[i] <= candy[i+1]: ca...

class Solution: def minWindow(self , S: str, T: str) -> str: # 检查是否所有的元素都包含在滑动窗口内 def check(hash): for _, val in hash.items(): if val < 0: return False return True left = 0 right = 0 res = "" hash = {} count = len(S) for i in range(len(T)): if T[i] in hash: hash[T[i]] -= 1 else: hash...

class Solution: def maxWater(self , arr: List[int]) -> int: # write code here left = 0 right = len(arr) - 1 res = 0 maxL = 0 maxR = 0 while left < right: maxL = max(maxL, arr[left]) maxR = max(maxR, arr[right]) if maxL < maxR: res += maxL - arr[left] left += 1 else: res += maxR - arr[right]...

class Solution: def maxArea(self , height: List[int]) -> int: # write code here if len(height) < 2: return 0 left = 0 right = len(height) - 1 res = 0 while left < right: water = (right-left)*min(height[left], height[right]) res = max(res, water) if height[left] < height[right]: # 贪心思想 le...