Python:二维列表的定义

写Leetcode的时候突然出现的一个错误,想要记录一下,也不知道起个什么标题好,所有随便起了一个大概相关的标题

以Leetcode的题目开始引入

Leetcode的第72题

image.png

下面是解法(Python)

# 动态规划
# 具体看leetcode讲解
# 注意里面dp定义的细节
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)

        if n*m == 0:
            return n+m
        
        # 下面两种dp定义,第一种定义是错的,因为列表内的元素id都相同
        # dp = [[0] * (m+1)] * (n+1)
        dp = [ [0] * (m + 1) for _ in range(n + 1)]
        for i in range(n+1):
            dp[i][0] = i
        for j in range(m+1):
            dp[0][j] = j
        
        for i in range(1, n+1):
            for j in range(1, m+1):
                left = dp[i][j-1] + 1
                down = dp[i-1][j] + 1
                left_down = dp[i-1][j-1]
                if word1[i-1] != word2[j-1]:
                    left_down += 1
                dp[i][j] = min(left, down, left_down)
        return dp[-1][-1]

代码中列表定义的区别

看代码注意到dp = [[0] * (m+1)] * (n+1)dp = [ [0] * (m + 1) for _ in range(n + 1)]是不一样的,两种答案不同,后者才是我们想要的答案,那么为什么会出现这种不同呢?

通过一个简单的例子来看看

image.png

我们发现不同元素的id是一样的,即它们都指向同一个内存地址。


image.png

结论

dp = [[0] * (m+1)] * (n+1)dp = [ [0] * (m + 1) for _ in range(n + 1)]打印出来一样,但前者是列表里面n+1个元素都是指向同一个内存地址,后者是不同的内存地址。所以,建议定义二维列表的时候用列表生成式

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,415评论 0 2
  • 官网 中文版本 好的网站 Content-type: text/htmlBASH Section: User ...
    不排版阅读 4,465评论 0 5
  • (欢迎转载,但请注明出处并附带链接)算法好久没复习了,今天看见一妹子在办公室刷Leetcode,顿时我也来了兴趣,...
    Nick_Zuo阅读 688评论 0 3
  • 今天又是很丧的一天,都不知道记录什么好。你现在的状态真的是很不好,上班一副要死不活的样子,中午特地上去找你,结果...
    forYouForUs阅读 70评论 0 0
  • 听说练毛笔字可以修身养性,于是这学期自己去报了一个书法班,一方面沉淀下自己浮躁的心,另一方面也可以提升下自己的写字...
    31慢慢阅读 607评论 0 0