每日一题
题目
面试题 01.08. 零矩阵 难度：medium
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
示例 1：
输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]示例 2：
输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
方法一：标记数组
思路
从题目中可知，当矩阵中的某个元素为0时，那么它所在的行与列都将清零，因此，可以先记录下原始矩阵中0的坐标，这里的话，自然而然的就想到了标记数组，伪代码如下：
# 记录某一行是否有0
rows -> List[boolean]
# 记录某一列是否有0
cols -> List[boolean]
# 遍历矩阵找寻元素值为0
for ..:
for ..:
if matrix[i][j] == 0:
rows[i] = cols[j] = True将元素值为0的位置记录下来之后，就是将它所对应的行列给清零，伪代码如下：
for ..:
for ..:
if rows[i] or cols[j]:
matrix[i][j] = 0
题解
Python：
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
row, col = [False] * m, [False] * n
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = col[j] = True
for i in range(m):
for j in range(n):
if row[i] or col[j]:
matrix[i][j] = 0Java：
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
}
方法二：原地标记
思路
在方法一中，我们开辟了额外的空间来存储标记，那这里我们可以做优化，将时间复杂度 O(n) 下降到 O(1) 吗？答案是可以的，请往下看；
我们知道，当某元素值为0时，它所在的行与列将全部清零，因此，我们可以将第一列和第一行用做标记，这样就不需要开辟额外的空间去存储标记了，伪代码如下：
for ..:
for ..:
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0同时，需要注意的是，我们一开始要先判断第一行与第一列是否有元素值为0的存在，伪代码如下：
flag_row = # 判断第一行是否有元素值为0
flag_col = # 判断第一列是否有元素值为0
题解
Python：
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
flag_col0 = any(matrix[i][0] == 0 for i in range(m))
flag_row0 = any(matrix[0][j] == 0 for j in range(n))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][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 flag_col0:
for i in range(m):
matrix[i][0] = 0
if flag_row0:
for j in range(n):
matrix[0][j] = 0Java：
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean flagCol0 = false, flagRow0 = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
flagCol0 = true;
}
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
flagRow0 = true;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (flagCol0) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (flagRow0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}
}
205. 同构字符串
题目
205. 同构字符串 难度：easy
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1:
输入：s = "egg", t = "add"
输出：true示例 2：
输入：s = "foo", t = "bar"
输出：false示例 3：
输入：s = "paper", t = "title"
输出：true提示：
1 <= s.length <= 5 * 104t.length == s.lengths和t由任意有效的 ASCII 字符组成
方法一：哈希表
思路
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
由这个题意可知，我们只要建立好映射关系，并确保它们一一对应即可，因此，需要创建两个哈希表 s2t 和 t2s 来维持一一对应的映射关系，伪代码如下：
if (s[i] in s2t and s2t[s[i]] != t[i]) or (t[i] in t2s and t2s[t[i]] != s[i]):
return False
解题
Python：
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s2t = {}
t2s = {}
for i in range(len(s)):
if (s[i] in s2t and s2t[s[i]] != t[i]) or (t[i] in t2s and t2s[t[i]] != s[i]):
return False
s2t[s[i]] = t[i]
t2s[t[i]] = s[i]
return TrueJava：
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s2t = new HashMap<Character, Character>();
Map<Character, Character> t2s = new HashMap<Character, Character>();
int len = s.length();
for (int i = 0; i < len; ++i) {
char x = s.charAt(i), y = t.charAt(i);
if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
return false;
}
s2t.put(x, y);
t2s.put(y, x);
}
return true;
}
}
392. 判断子序列
题目
392. 判断子序列 难度：easy
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace" 是 "abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false提示：
0 <= s.length <= 1000 <= t.length <= 10^4- 两个字符串都只由小写字符组成。
方法一：双指针
思路
先搞清楚何为子序列？字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
因此，只要能找到任意一种 s 在 t 中出现的方式，即可认为 s 是 t 的子序列。
那么最先想到的自然而然是哈希表啦，但是由于要确保其顺序性，还是使用双指针比较合适；
初始化两个指针 i 和 j，分别指向 s 和 t 的初始位置。每次贪心地匹配，匹配成功则 i 和 j 同时右移，匹配失败则 j 右移，i 不变，尝试用 t 的下一个字符匹配 s。
解题
Python：
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
n, m = len(s), len(t)
i = j = 0
while i < n and j < m:
if s[i] == t[j]:
i += 1
j += 1
return i == nJava：
class Solution {
public boolean isSubsequence(String s, String t) {
int n = s.length(), m = t.length();
int i = 0, j = 0;
while (i < n && j < m) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == n;
}
}
后记
📝 上篇精讲： 【算法题解】 Day1 前缀和
💖 我是 𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注；
👍 创作不易，请多多支持；
🔥 系列专栏： 算法题解
