Joyce' Blog
0%

edit-distance & set-matrix-zeroes

发表于 更新于

题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

题解

果然最近都是考动态规划！编辑距离我应该是会的，明天试试~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int minDistance(string word1, string word2) {
	int len1 = word1.length();
	int len2 = word2.length();
	int **dist = new int*[len1+1];
	for (int i = 0; i <= len1; i++)
		dist[i] = new int[len2 + 1];
	for (int i = 0; i <= len1; i++)
		dist[i][0] = i;
	for (int j = 0; j <= len2; j++)
		dist[0][j] = j;

	for (int i = 1; i <= len1; i++)
	{
		for (int j = 1; j <= len2; j++)
		{
			int a = dist[i - 1][j - 1];
			int t = word1[i - 1] == word2[j - 1] ? a : a + 1;
			int k = min(dist[i][j - 1], dist[i - 1][j]) + 1;
			dist[i][j] = min(t, k);
		}
	}
	return dist[len1][len2];
}

一遍过，正常发挥。

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

进阶:

一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

题解

O(m + n) 的额外空间也就是两个数组，记录哪一行全1，哪一列全1吧，常数空间的话，看了下官方题解，是在原有的矩阵上做标记，m[i][j]=0，就把m[0][j]和m[i][0]都置为零。

emm……官方题解有问题，用特殊数字做标记行不通。就写 O(m + n) 的吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void setZeroes(vector<vector<int>>& matrix) {
	int m = matrix.size();
	int n = matrix[0].size();
	bool *row, *col;
	row = new bool[m];
	col = new bool[n];
	for (int i = 0; i < m; i++)
		row[i] = 1;
	for (int i = 0;i < n; i++)
		col[i] = 1;
 	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!matrix[i][j])
			{
				row[i] = 0;
				col[j] = 0;
			}
		}
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!(row[i]&col[j]))
			{
				matrix[i][j] = 0;
			}
		}
	}
}

执行用时 :12 ms, 在所有 C++ 提交中击败了96.46%的用户

内存消耗 :11.4 MB, 在所有 C++ 提交中击败了68.26%的用户

我觉得可以接受。