class Solution:
def maxSubArray(self, nums: List[int]) -> int:
length = len(nums)
dp = [0 for i in range(length)]
for i in range(length):
dp[i] = max(dp[i - 1], 0) + nums[i]
return max(dp)
题解给出了一种省略dp数组的方法：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre = 0
res = nums[0]
for x in nums:
pre = max(pre+x ,x)
res = max(res, pre)
return res
第2天
1. 两数之和
找出数组中两个数之和等于target的两数下标。
暴力枚举可以
但时间较长，时间复杂度$O(N^2)$
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
88. 合并两个有序数组
两个有序数组，将第二个数组nums2合并到第一个数组nums1。
双指针
1.可以用双指针遍历两个数组：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
# 两个中存在空数组的时，直接返回
if m == 0:
nums1[:] = nums2[:]
return
if n == 0:
return
index1,index2 = 0,0
t = []
while index1<m and index2<n:
if nums1[index1] <= nums2[index2]:
t.append(nums1[index1])
index1 += 1
else:
t.append(nums2[index2])
index2 += 1
if index1 < m:
t += nums1[index1:m]
else:
t += nums2[index2:n]
nums1[:] = t[:]
class Solution:
def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
m,n = len(mat), len(mat[0])
if m*n != r*c:
return mat
arr = []
for row in mat:
for x in row:
arr.append(x)
arr_index = 0
newmat = [[0 for j in range(c)]for i in range(r)]
for i in range(r):
for j in range(c):
newmat[i][j] = arr[arr_index]
arr_index += 1
return newmat
官方提供了一种直接计算下标的方法：
class Solution:
def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]:
m, n = len(nums), len(nums[0])
if m * n != r * c:
return nums
ans = [[0] * c for _ in range(r)]
for x in range(m * n):
ans[x // c][x % c] = nums[x // n][x % n]
return ans
118. 杨辉三角
找规律题。可以直接按照生成的规律生成数组。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = [[]for _ in range(numRows)]
res[0] = [1]
for i in range(1,numRows):
res[i].append(1)
for j in range(0,len(res[i-1])-1):
res[i].append(res[i-1][j] + res[i-1][j+1])
res[i].append(1)
return res
第5天
36. 有效的数独
判断当前数独是否有效（不需要填充数独）
只要用3个二维数组维护9行、9列、9个九宫格。
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row = [[] * 9 for _ in range(9)]
col = [[] * 9 for _ in range(9)]
nine = [[] * 9 for _ in range(9)]
for i in range(len(board)):
for j in range(len(board[0])):
tmp = board[i][j]
if not tmp.isdigit():
continue
if (tmp in row[i]) or (tmp in col[j]) or (tmp in nine[(j // 3) * 3 + (i // 3)]):
return False
row[i].append(tmp)
col[j].append(tmp)
nine[(j // 3) * 3 + (i // 3)].append(tmp)
return True
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
#标记
m,n = len(matrix), len(matrix[0])
row = any(x == 0 for x in matrix[0])
col = any(matrix[r][0] == 0 for r in range(m) )
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
#置零
for i in range(1,m):
for j in range(1,n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if row:
for j in range(0,n):
matrix[0][j] = 0
if col:
for i in range(0,m):
matrix[i][0] = 0
以上がPython 多次元リストの落とし穴を解決する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
