【Day17】Java算法刷题 【面试题 01.08. 零矩阵】 【844. 比较含退格的字符串】

简介: 了解Java算法刷题 【面试题 01.08. 零矩阵】 【844. 比较含退格的字符串】。

刷题打卡,第 十七 天


题目一、面试题 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;
                }
            }
     }
    }
}

提交结果:

微信图片_20221030171635.png

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

提交结果:

微信图片_20221030171644.png

⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔

⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔

您的点赞,收藏以及关注是对作者最大的鼓励喔 ~~

微信图片_20221029111446.jpg




目录
相关文章
|
1月前
|
存储 算法 安全
探究‘公司禁用 U 盘’背后的哈希表算法与 Java 实现
在数字化办公时代,信息安全至关重要。许多公司采取“禁用U盘”策略,利用哈希表算法高效管理外接设备的接入权限。哈希表通过哈希函数将设备标识映射到数组索引,快速判断U盘是否授权。例如,公司预先将允许的U盘标识存入哈希表,新设备接入时迅速验证,未授权则禁止传输并报警。这有效防止恶意软件和数据泄露,保障企业信息安全。 代码示例展示了如何用Java实现简单的哈希表,模拟公司U盘管控场景。哈希表不仅用于设备管理,还在文件索引、用户权限等多方面助力信息安全防线的构建,为企业数字化进程保驾护航。
|
4月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
120 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
算法
|
6月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
4月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
132 1
两个字符串匹配出最长公共子序列算法
|
4月前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
4月前
|
机器学习/深度学习 算法 搜索推荐
django调用矩阵分解推荐算法模型做推荐系统
django调用矩阵分解推荐算法模型做推荐系统
67 4
|
4月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
141 2
|
4月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
243 0
|
6月前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。