部分遇到的LeetCode原题题解
LeetCode 42. 接雨水
class Solution: def trap(self, height: List[int]) -> int: left = 0 right = len(height)-1 left_max = right_max = 0 s = 0 while left <= right: if left_max < right_max: s += max(0, left_max - height[left]) left_max = max(left_max, height[left]) left += 1 else: s += max(0, right_max - height[right]) right_max = max(right_max, height[right]) right -= 1 return s
LeetCode 62. 不同路径
class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[1]*n] + [[1] + [0]*(n-1) for _ in range(m-1)] for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m-1][n-1]
LeetCode 74. 搜索二维矩阵
从右上角开始遍历（左下角也可以）：
- 如果要搜索的 target 比当前元素大，那么让行增加；
- 如果要搜索的 target 比当前元素小，那么让列减小；
class Solution(object): def searchMatrix(self, matrix, target): if not matrix&nbs***bsp;not matrix[0]: return False rows = len(matrix) cols = len(matrix[0]) row, col = 0, cols - 1 while True: if row < rows and col >= 0: if matrix[row][col] == target: return True elif matrix[row][col] < target: row += 1 else: col -= 1 else: return False
