【Day17】Java算法刷题 【面试题 01.08. 零矩阵】 【844. 比较含退格的字符串】
【Day17】Java算法刷题 【面试题 01.08. 零矩阵】 【844. 比较含退格的字符串】
CSDN话题挑战赛第2期 参赛话题：学习笔记
刷题打卡，第 十七 天
题目一、面试题 01.08. 零矩阵
原题链接：面试题 01.08. 零矩阵
题目描述：
编写一种算法，若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 可能不属于原始的矩阵，而是前面填充得来的，这样就得不到想要的结果了。
所以这时候我们需要另外准备两个数组，分别代表需要填充 元素0 的行和列，我们遍历整个原始矩阵，当遇到 0，就将这个 元素0 所在矩阵中的行和列做标记。
当我们遍历完整个矩阵的元素后，也就知道了所有 元素0 出现的位置，只需要再遍历一次，当遍历到的元素 位置在被标记了的行或者列中，就使用0填充给。
整个矩阵遍历完，也就完成了零矩阵。
提交代码：
class Solution {
public void setZeroes(int[][] matrix) {
int row = matrix.length; //记录矩阵行数
int coll = matrix[0].length; //记录矩阵列数
int[] R = new int[row]; //用于标记出现0的行
int[] C = new int[coll]; //用于标记出现0的列
for(int i = 0;i < row;++i){
for(int j = 0;j < coll;++j){//遍历整个矩阵
if(matrix[i][j] == 0){ //遇到 0
R[i] = 1; //标记0出现的行和列
C[j] = 1;
}
}
}
for(int i = 0;i < row;++i){
for(int j = 0;j < coll;++j){ //第二次遍历矩阵
if(R[i] == 1 || C[j] == 1){ //将标记了的行和列里面的元素用0填充
matrix[i][j] = 0;
}
}
}
}
}提交结果：
题目二、844. 比较含退格的字符串
原题链接：844. 比较含退格的字符串
题目描述：
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。 注意：如果对空文本输入退格字符，文本继续为空。 / 示例 1： 输入：s = “ab#c”, t = “ad#c” 输出：true 解释：s 和 t 都会变成 “ac”。 / 示例 2： 输入：s = “ab##”, t = “c#d#” 输出：true 解释：s 和 t 都会变成 “”。 / 示例 3： 输入：s = “a#c”, t = “b” 输出：false 解释：s 会变成 “c”，但 t 仍然是 “b”。
解题思路：
题目要求对给定的字符串进行处理，当字符串中出现‘#’退格符号，前面就需要删除一个普通字符，最终判断处理完的字符是否相等，输出答案。
我一开始觉得是用集合或者数组，就写了很多个循环结构去处理，遇到 # 就把 # 以及 前面一个位置的元素删除，但是运行超时，时间复杂度实在让人大跌眼镜。
看了题解的思路之后，瞬间就开窍了。
我们完全可以巧妙地利用堆栈的结构，扫描字符串的每一个字符，正常的字符正常压入堆栈结构中。
当遇到退格符号 # 我们就让栈顶元素出栈，这样就达到了退格的效果，非常简单就得到了我们想要的效果。
最后我们怎么判断重构完成后的两个字符串是否相等呢？只需要使用equals()方法，就可以比较返回的两个堆栈结构是否相等了。
提交代码：
class Solution {
public boolean backspaceCompare(String s, String t) {
//比较最终获得的堆栈内容，两者相等返回true，否则返回false
return bulid(s).equals(bulid(t));
}
public Deque bulid(String str){ //建立重构字符串的方法
int len = str.length(); //获取传入字符串的长度
Deque<Character> dq = new LinkedList<>();//创建堆栈结构
for(int i = 0;i < len;++i){//遍历字符串字符
char ch = str.charAt(i);
if(ch != '#'){ //遍历到正常的字符
dq.push(ch); //入栈
}
else{ //遍历到‘#’退格字符
if(dq.size() > 0) //栈空就不需要操作了
dq.pop(); //栈顶元素出栈，达到推个效果
}
}
return dq; //返回存放重构后字符的堆栈结构
}
}提交结果：
腾讯云开发者
