찾다

집  >  기사  >  백엔드 개발  >  Python 다차원 목록의 함정을 해결하는 방법

Python 다차원 목록의 함정을 해결하는 방법

WBOY
WBOY앞으로
2023-05-14 12:01:151243검색

배열에 대한 일반적인 아이디어 요약:

(아래의 기본값 nums은 배열입니다.) 1. 어레이 탐색 순회: 

for num in nums:
	xxxx

색인 

for idx,num in enumerate(nums):
	xxxx

를 사용한 순회 2. 동적 프로그래밍(dp) 동적 프로그래밍은 일반적으로 배열을 사용하여 상태를 저장합니다. 또 만나요53.最大子数组和. 상태를 저장하기 위해 배열을 사용하는 것은 매우 일반적인 관행입니다. 예를 들어 36.有效的数独、 73. 矩阵置零.

3.더블 포인터 88.合并两个有序数组、350.两个数组的交集 II를 배열의 왼쪽 및 오른쪽 포인터로 사용할 수 있음을 참조하세요. 또한 두 개의 배열을 탐색하는 두 개의 포인터일 수도 있습니다. index1<m 및 index2<n:while index1<m and index2<n:

列表常用函数

Python中一般用listlist목록에 대한 일반적인 함수.sort是list独有的。参考序列操作文档）

Python에서 는 일반적으로 변수 배열을 구현하는 데 사용됩니다. 다음은 자주 사용되는 기능입니다. (변수 시퀀스 유형의 일반적인 연산, .sort만
函数功能
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
에 고유합니다. 시퀀스 연산 문서를 참조하세요) 🎜🎜
Function< / th>함수
nums.sort(key, reversed)🎜(in place) 오름차순 order by key Sorting, reversed는 역순으로 할지 여부를 지정할 수 있습니다. 🎜🎜
sorted(nums,key,reversed)🎜사용법은 nums.sort와 유사하지만 다른 배열이 반환되고 원본 배열은 변경되지 않습니다. 🎜🎜
s.append(x)🎜시퀀스 끝에 x를 추가하세요🎜🎜
s.extend(t) 또는 s += t🎜t의 내용을 사용하여 s🎜🎜
x를 s에서 확장🎜 x가 배열에 있는지 확인하세요🎜. 🎜🎜
len(s)🎜s🎜🎜
max(s)의 길이를 반환합니다. , min (s)🎜s🎜🎜
all(iterable)🎜의 최대값과 최소값을 반환합니다. < If all elements of code>iterable이 true 값인 경우(또는 iterable 객체가 비어 있는 경우) True🎜🎜
any (iterable)</code >🎜<td><code>iterable의 요소 중 하나라도 true인 경우 True를 반환합니다. iterable이 비어 있으면 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]]<h2>第1天</h2>
<h3>217. 存在重复元素</h3>
<p>给定数组，判断是否存在重复元素。
做法：</p>
<ol class=" list-paddingleft-2">
<li><p>直接遍历（穷举）</p></li>
<li><p>排序后，比较每个元素和下一个元素</p></li>
<li><p>哈希表</p></li>
</ol>
<p>直接遍历会超时。
2的时间复杂度是O(nlogn) 也就是排序的时间复杂度
3的时间复杂度是O(n)，但需要额外的O(n)辅助空间。
（穷举法基本都能想到，但很容易超时，后面只有在穷举法能通过时才列出来。）</p>
<p>3比较简单，这里写一下3的做法：</p>
<pre class="brush:php;toolbar:false">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. 杨辉三角

找规律题。可以直接按照生成的规律生成数组。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

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 다차원 목록의 함정을 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

Python sort while 指针 len append 对象 算法 重构
성명：
이 기사는 yisu.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제
이전 기사：Python에서 셀레늄 스크린샷을 구현하는 방법다음 기사：Python에서 셀레늄 스크린샷을 구현하는 방법

관련 기사

더보기