Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Set Matrix Zeroes

Leetcode algorithms 第 73 题:Set Matrix Zeroes。

题目

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

解答

某一个位置为0时,不能立刻把它所在的行和列全部置为0,因为这样会导致后面判断时不知道一个0是已有的还是后面才添加的。

由于不能使用额外的空间,于是只能在原有的矩阵中做一些标记。可以在某个位置为0时,把它所在行的第一个位置和所在列的第一个位置置为0,这样在遍历完所有数字之后,根据第一行和第一列的标志0即可知道要把哪些行和哪些列置为0。

但是第一行和第一列可能本身也有一些0,我们不能确定第一行和第一列是否需要全部置为0,这可以在遍历整个矩阵之前先遍历第一行和第一列,记录下是否需要把第一行和第一列全部置0,然后再在最后根据这两个记录的标志进行对应的操作。

具体代码如下:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[1000][1000]; //dp[i][j:word1的前i个字符和word2的前j个字符的edit distance
        
        int n1 = word1.size(), n2 = word2.size();
        for (int i = 0; i <= n1; i++) dp[i][0] = i; //初始化
        for (int i = 0; i <= n2; i++) dp[0][i] = i;
        
        for (int i = 1; i <= n1; i++)
            for (int j = 1; j <= n2; j++)
            {
                if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
            }
        
        return dp[n1][n2];
    }
};
上一篇: 下一篇:
  1. ▇▇▇▇无毒爽站【htTP://v.ht/aS8H】 ,在线爽,夫妇必备 ▇▇▇▇▇

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论