How to solve pitfalls in Python multidimensional lists
WBOYforward
2023-05-14 12:01:151251browse
Summary of common ideas for arrays:
(The default nums below is an array.)
1. Traverse the array
Traversal:
for num in nums:
xxxx
Traversal with index
for idx,num in enumerate(nums):
xxxx
2. Dynamic programming (dp)
Dynamic programming generally uses an array to save state. See 53. Maximum subarray and .
Using arrays to save state is a very common practice. For example 36. Valid Sudoku, 73. Set matrix to zero.
3.Double pointer
See 88. Merge two ordered arrays, 350. Intersection of two arrays II can be used for one array with left and right pointers.
It can also be two pointers traversing two arrays. while index1<m and index2<n:
Common functions for lists
In Python, list is generally used to implement variable arrays.
The following is listcommonly used functions.
(Common operations for variable sequence types, only .sort is unique to list. Refer to the sequence operation documentation)
function
Function
nums.sort(key,reversed)
(original)Follow The key is sorted in ascending order, reversed can specify whether to reverse.
sorted(nums,key,reversed)
Usage is similar to nums.sort, but returns another array , the original array remains unchanged.
s.append(x)
Append x to the end of the sequence
s.extend(t) or s = t
extend s
x in with the content of t s
Determine whether x is in the array nums.
len(s)
Return s length
max(s), min(s)
Return sMaximum value, minimum value
all( iterable)
Returns True# if all elements of
iterable
are true (or the iterable is empty)
##any(iterable)
Returns
True if any element of iterable is true. If the iterable is empty, returns False.
多维列表的一个坑
创建多维列表，一般用
w, h = 2, 3
A = [[None] * w for i in range(h)]
等价于
A = [None] * 3
for i in range(3):
A[i] = [None] * 2
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
The above is the detailed content of How to solve pitfalls in Python multidimensional lists. For more information, please follow other related articles on the PHP Chinese website!
