文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Python多维列表中的坑如何解决

2023-07-06 12:22

关注

这篇文章主要讲解了“Python多维列表中的坑如何解决”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Python多维列表中的坑如何解决”吧!

数组常用想法总结:

(以下默认nums为数组。)1.遍历数组遍历:

for num in nums:xxxx

带索引遍历

for idx,num in enumerate(nums):xxxx

动态规划(dp)动态规划一般可以用一个数组保存状态。见53.最大子数组和。用数组保存状态是非常常用的做法。例如36.有效的数独73. 矩阵置零

双指针见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, 3A = [[None] * w for i in range(h)]

等价于

A = [None] * 3for 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

双指针

可以用双指针遍历两个数组:

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多维列表中的坑如何解决”的内容了,经过本文的学习后,相信大家对Python多维列表中的坑如何解决这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是编程网,小编将为大家推送更多相关知识点的文章,欢迎关注!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯