首页 > 编程学习 > 【Day17】Java算法刷题 【面试题 01.08. 零矩阵】 【844. 比较含退格的字符串】

CSDN话题挑战赛第2期
参赛话题:学习笔记

在这里插入图片描述

刷题打卡,第 十七 天

  • 题目一、面试题 01.08. 零矩阵
  • 题目二、844. 比较含退格的字符串


题目一、面试题 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; //返回存放重构后字符的堆栈结构
    }
}

提交结果

在这里插入图片描述



求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞收藏以及关注是对作者最大的鼓励喔 ~~

在这里插入图片描述

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号