【算法题解】 Day2 字符串

2023-08-31 13:33:46 浏览数 (2)

每日一题

题目

面试题 01.08. 零矩阵 难度：medium

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

代码语言：javascript复制
输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2：

代码语言：javascript复制
输入：
[
  [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的坐标，这里的话，自然而然的就想到了标记数组，伪代码如下：

代码语言：javascript复制
# 记录某一行是否有0
rows -> List[boolean]
# 记录某一列是否有0
cols -> List[boolean]
# 遍历矩阵找寻元素值为0
for ..:
    for ..:
        if matrix[i][j] == 0:
            rows[i] = cols[j] = True

将元素值为0的位置记录下来之后，就是将它所对应的行列给清零，伪代码如下：

代码语言：javascript复制
for ..:
    for ..:
        if rows[i] or cols[j]:
            matrix[i][j] = 0

题解

Python：

代码语言：javascript复制
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] = 0

Java：

代码语言：javascript复制
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时，它所在的行与列将全部清零，因此，我们可以将第一列和第一行用做标记，这样就不需要开辟额外的空间去存储标记了，伪代码如下：

代码语言：javascript复制
for ..:
    for ..:
        if matrix[i][j] == 0:
            matrix[i][0] = matrix[0][j] = 0

同时，需要注意的是，我们一开始要先判断第一行与第一列是否有元素值为0的存在，伪代码如下：

代码语言：javascript复制
flag_row = # 判断第一行是否有元素值为0
flag_col = # 判断第一列是否有元素值为0

题解

Python：

代码语言：javascript复制
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] = 0

Java：

代码语言：javascript复制
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:

代码语言：javascript复制
输入：s = "egg", t = "add"
输出：true

示例 2：

代码语言：javascript复制
输入：s = "foo", t = "bar"
输出：false

示例 3：

代码语言：javascript复制
输入：s = "paper", t = "title"
输出：true

提示：

  • 1 <= s.length <= 5 * 104
  • t.length == s.length
  • s 和 t 由任意有效的 ASCII 字符组成

方法一：哈希表

思路

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

由这个题意可知，我们只要建立好映射关系，并确保它们一一对应即可，因此，需要创建两个哈希表 s2t 和 t2s 来维持一一对应的映射关系，伪代码如下：

代码语言：javascript复制
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：

代码语言：javascript复制
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 True

Java：

代码语言：javascript复制
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：

代码语言：javascript复制
输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

代码语言：javascript复制
输入：s = "axc", t = "ahbgdc"
输出：false

提示：

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。

方法一：双指针

思路

先搞清楚何为子序列？字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。

因此，只要能找到任意一种 s 在 t 中出现的方式，即可认为 s 是 t 的子序列。

那么最先想到的自然而然是哈希表啦，但是由于要确保其顺序性，还是使用双指针比较合适；

初始化两个指针 i 和 j，分别指向 s 和 t 的初始位置。每次贪心地匹配，匹配成功则 i 和 j 同时右移，匹配失败则 j 右移，i 不变，尝试用 t 的下一个字符匹配 s。

解题

Python：

代码语言：javascript复制
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 == n

Java：

代码语言：javascript复制
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;
    }
}
int matrix 算法 指针 字符串

0 人点赞