【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




目录
相关文章
|
3天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
14 2
|
8天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
13天前
|
存储 缓存 Oracle
Java I/O流面试之道
NIO的出现在于提高IO的速度,它相比传统的输入/输出流速度更快。NIO通过管道Channel和缓冲器Buffer来处理数据,可以把管道当成一个矿藏,缓冲器就是矿藏里的卡车。程序通过管道里的缓冲器进行数据交互,而不直接处理数据。程序要么从缓冲器获取数据,要么输入数据到缓冲器。
Java I/O流面试之道
|
9天前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
33 4
|
10天前
|
存储 Java 程序员
Java基础的灵魂——Object类方法详解(社招面试不踩坑)
本文介绍了Java中`Object`类的几个重要方法,包括`toString`、`equals`、`hashCode`、`finalize`、`clone`、`getClass`、`notify`和`wait`。这些方法是面试中的常考点,掌握它们有助于理解Java对象的行为和实现多线程编程。作者通过具体示例和应用场景,详细解析了每个方法的作用和重写技巧,帮助读者更好地应对面试和技术开发。
49 4
|
24天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
10天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
10天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。