Python多維列表中的坑怎么解決

蝸牛 互聯網技術資訊 2022-10-14 6 0

本篇內容主要講解“Python多維列表中的坑怎么解決”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學習“Python多維列表中的坑怎么解決”吧!

數組常用想法總結:

(以下默認nums為數組。) 1.遍歷數組 遍歷:

for?num?in?nums:
	xxxx

帶索引遍歷

for?idx,num?in?enumerate(nums):
	xxxx

2.動態規劃(dp) 動態規劃一般可以用一個數組保存狀態。見53.最大子數組和。 用數組保存狀態是非常常用的做法。例如36.有效的數獨、 73. 矩陣置零。

3.雙指針 見88.合并兩個有序數組、350.兩個數組的交集 II可以是左右指針對一個數組使用。 也可以是兩個指針遍歷兩個數組。while index1<m and index2<n:

列表常用函數

Python中一般用list實現可變數組。 下面是list常用的函數。 (可變序列類型通用操作,只有.sortlist獨有的。參考序列操作文檔)

函數 功能
nums.sort(key,reversed) (原地)按照key升序排序,reversed可以指定是否反轉。
sorted(nums,key,reversed) 用法與nums.sort類似,但返回另一個數組,原數組不變。
s.append(x) 將 x 添加到序列的末尾
s.extend(t)s += t 用 t 的內容擴展 s
x in s 判斷x是否在數組nums中。
len(s) 返回s 長度
max(s)、min(s) 返回s最大值、最小值
all(iterable) 如果 iterable 的所有元素均為真值(或可迭代對象為空)則返回 True
any(iterable) 如果 iterable 的任一元素為真值則返回 True。 如果可迭代對象為空,返回 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

而不是

?A?=?[[None]?*?2]?*?3

原因在于用*對列表執行重復操作并不會創建副本,而只是創建現有對象的引用。 *3創建的是包含 3 個引用的列表,每個引用指向的是同一個長度為 2 的列表。 如果你給一項賦值,就會發現這個問題:

>>>?A[0][0]?=?5
>>>?A
[[5,?None],?[5,?None],?[5,?None]]

第1天

217. 存在重復元素

給定數組,判斷是否存在重復元素。 做法:

  1. 直接遍歷(窮舉)

  2. 排序后,比較每個元素和下一個元素

  3. 哈希表

直接遍歷會超時。 2的時間復雜度是O(nlogn) 也就是排序的時間復雜度 3的時間復雜度是O(n),但需要額外的O(n)輔助空間。 (窮舉法基本都能想到,但很容易超時,后面只有在窮舉法能通過時才列出來。)

3比較簡單,這里寫一下3的做法:

return?len(nums)?!=?len(set(nums))

53. 最大子數組和

給定數組,求其中一個連續數組和的最大值。

比較容易想到的是用一個數組記錄目前位置最大的值(動態規劃)。

dp[i] 表示以i位置結尾的連續數組和的最大值。 最后返回dp數組中最大值。

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?[]

哈希表

官方題解的一個比較巧妙的方式:使用哈希表(字典) 用字典記錄出現過的數字的位置。 時間復雜度$O(N)$,空間復雜度$O(N)$

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?merge(self,?nums1:?List[int],?m:?int,?nums2:?List[int],?n:?int)?->?None:
????????"""
????????Do?not?return?anything,?modify?nums1?in-place?instead.
????????"""
????????sorted?=?[]
????????p1,?p2?=?0,?0
????????while?p1?<?m?or?p2?<?n:
????????????if?p1?==?m:
????????????????sorted.append(nums2[p2])
????????????????p2?+=?1
????????????elif?p2?==?n:
????????????????sorted.append(nums1[p1])
????????????????p1?+=?1
????????????elif?nums1[p1]?<?nums2[p2]:
????????????????sorted.append(nums1[p1])
????????????????p1?+=?1
????????????else:
????????????????sorted.append(nums2[p2])
????????????????p2?+=?1
????????nums1[:]?=?sorted

(暴力) 追加后排序

  1. 更簡單粗暴的方式是直接將nums2追加到nums1后,進行排序。 及其簡單而且效果很好。

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.
????????"""
????????nums1[m:]?=?nums2
????????nums1.sort()

第3天

350. 兩個數組的交集 II

以數組形式返回兩數組的交集(數組形式,返回結果中每個元素出現的次數,應與元素在兩個數組中都出現的次數一致)。 排序后雙指針遍歷。

class?Solution:
????def?intersect(self,?nums1:?List[int],?nums2:?List[int])?->?List[int]:
????????nums1.sort()
????????nums2.sort()
????????i?=?0
????????j?=?0
????????result?=?[]
????????while?i<len(nums1)?and?j<len(nums2):
????????????if(nums1[i]<nums2[j]):
????????????????i+=1
????????????elif(nums1[i]>nums2[j]):
????????????????j+=1
????????????else:
????????????????result.append(nums1[i])
????????????????i+=1
????????????????j+=1
???????
????????return??result

121. 買賣股票的最佳時機

只需要記錄下當前最低價,遍歷價格過程中,用當前價格-最低價 就是當前可獲得的最大利潤。另外如果出現了更低的價格,則最低價也要更新。(一個樸素的想法,要是我在最低點買進就好了) 總的最大利潤就是這些利潤中的最大值。

class?Solution:
????def?maxProfit(self,?prices:?List[int])?->?int:
????????r?=?0
????????min_price?=?float('inf')??#?float('inf')表示正無窮
????????for?price?in?prices:
????????????min_price?=?min(min_price,?price)??#?截止到當前的最低價(買入價)
????????????r?=?max(r,?price?-?min_price)??#?截止到目前的最高利潤
????????return?r

第4天

566. 重塑矩陣

給定一個mxn的數組,重構為rxc的數組。 比較簡單的想法是把數組拉平為一位數組,然后逐個填充到新的數組中:

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. 楊輝三角

找規律題??梢灾苯影凑丈傻囊幝缮蓴到M。在「楊輝三角」中,每個數是它左上方和右上方的數的和。

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

73. 矩陣置零

如果一個元素為 0 ,則將其所在行和列的所有元素都設為 0 。請使用 原地 算法。 A: 利用數組的首行和首列來記錄 0 值 另外用兩個布爾值記錄首行首列是否需要置0

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多維列表中的坑怎么解決”有了更深的了解,不妨來實際操作一番吧!這里是蝸牛博客網站,更多相關內容可以進入相關頻道進行查詢,關注我們,繼續學習!

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:niceseo99@gmail.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

評論

日本韩欧美一级A片在线观看