当前位置: 首页 > news >正文

怒刷LeetCode的第26天(Java版)

第一题

题目来源

64. 最小路径和 - 力扣(LeetCode)

题目内容

解决方法

方法一:动态规划

可以使用动态规划来解决这个问题。

  1. 首先创建一个与网格大小相同的二维数组dp,用于存储从起点到每个位置的最小路径和。
  2. 然后初始化dp[0][0] = grid[0][0],表示起点的最小路径和为起点的值。
  3. 接下来进行动态规划的遍历,遍历顺序可从起点开始按行或按列遍历。对于每个位置dp[i][j],其最小路径和为grid[i][j]加上它左边或上边位置的最小路径和的较小值。

复杂度分析:

时间复杂度:

  • 遍历网格中的每个元素,所以需要进行两层嵌套循环,总共遍历次数为m * n,其中m为网格的行数,n为网格的列数。
  • 在每次循环中,执行常数时间的操作,将上方和左方的最小路径和与当前位置的值相加,然后取最小值。
  • 因此,整体的时间复杂度为O(m * n)。

空间复杂度:

  • 创建了一个与网格大小相同的二维数组dp,用于存储从起点到每个位置的最小路径和。因此需要额外的空间来存储这些最小路径和。
  • dp数组的大小为m * n,与原始网格的大小相同。
  • 所以,空间复杂度为O(m * n)。

综上所述,该算法的时间复杂度为O(m * n),空间复杂度为O(m * n)。

LeetCode运行结果:

第二题

题目来源

65. 有效数字 - 力扣(LeetCode)

题目内容

解决方法

方法一:有限状态自动机

可以使用有限状态自动机(DFA)来解决该问题。我们需要设计合适的状态集合以及状态转移规则。其中,状态包括以下几种:

起始空格状态:在这个状态下,前面的空格已经被忽略。 符号位状态:在这个状态下,可能出现 + 或 -。 整数状态:在这个状态下,输入了数字 0-9。 小数点状态:在这个状态下,已经输入了小数点。 小数状态:在这个状态下,已经输入了数字并带有小数点。 幂符号状态:在这个状态下,出现了字符 e 或 E。 幂符号后的符号位状态:在这个状态下,出现了符号位 + 或 -。 幂符号后的整数状态:在这个状态下,输入了数字 0-9。 终止状态:如果当前输入的字符不合法或者最后一步能够到达终止状态,则说明输入是一个合法的数字。

class Solution {
public boolean isNumber(String s) {// 定义有限状态自动机Map<State, Map<CharType, State>> transfer = new HashMap<>(); transfer.put(State.STATE_INITIAL, new HashMap<>() {{put(CharType.CHAR_SPACE, State.STATE_INITIAL); // 起始空格状态put(CharType.CHAR_NUMBER, State.STATE_INTEGER); // 整数状态put(CharType.CHAR_SIGN, State.STATE_SIGN); // 符号位状态put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT); // 小数点状态(前面没有数字)}});transfer.put(State.STATE_SIGN, new HashMap<>() {{put(CharType.CHAR_NUMBER, State.STATE_INTEGER); // 整数状态put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT); // 小数点状态(前面没有数字)}});transfer.put(State.STATE_INTEGER, new HashMap<>() {{put(CharType.CHAR_NUMBER, State.STATE_INTEGER); // 整数状态put(CharType.CHAR_EXP, State.STATE_EXP); // 幂符号状态put(CharType.CHAR_POINT, State.STATE_POINT); // 小数状态put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});transfer.put(State.STATE_POINT, new HashMap<>() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION); // 小数状态put(CharType.CHAR_EXP, State.STATE_EXP); // 幂符号状态put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});transfer.put(State.STATE_POINT_WITHOUT_INT, new HashMap<>() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION); // 小数状态}});transfer.put(State.STATE_FRACTION, new HashMap<>() {{put(CharType.CHAR_NUMBER, State.STATE_FRACTION); // 小数状态put(CharType.CHAR_EXP, State.STATE_EXP); // 幂符号状态put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});transfer.put(State.STATE_EXP, new HashMap<>() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); // 幂符号后的整数状态put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN); // 幂符号后的符号位状态}});transfer.put(State.STATE_EXP_SIGN, new HashMap<>() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); // 幂符号后的整数状态}});transfer.put(State.STATE_EXP_NUMBER, new HashMap<>() {{put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER); // 幂符号后的整数状态put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});transfer.put(State.STATE_END, new HashMap<>() {{put(CharType.CHAR_SPACE, State.STATE_END); // 终止状态}});// 根据定义的状态转移规则,判断该字符串是否为有效数字int length = s.length();State state = State.STATE_INITIAL;for (int i = 0; i < length; i++) {CharType type = toCharType(s.charAt(i));if (!transfer.get(state).containsKey(type)) { // 当前输入不合法return false;}state = transfer.get(state).get(type); // 进入下一个状态}// 最后一步能够到达终止状态说明该字符串是一个有效数字return state == State.STATE_INTEGER || state == State.STATE_POINT ||state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER ||state == State.STATE_END;
}// 定义字符类型枚举类
enum CharType {CHAR_NUMBER,CHAR_EXP,CHAR_POINT,CHAR_SIGN,CHAR_SPACE,CHAR_ILLEGAL
}// 判断字符类型
private CharType toCharType(char ch) {if (ch >= '0' && ch <= '9') {return CharType.CHAR_NUMBER;} else if (ch == 'e' || ch == 'E') {return CharType.CHAR_EXP;} else if (ch == '.') {return CharType.CHAR_POINT;} else if (ch == '+' || ch == '-') {return CharType.CHAR_SIGN;} else if (ch == ' ') {return CharType.CHAR_SPACE;} else {return CharType.CHAR_ILLEGAL;}
}// 定义状态枚举类
enum State {STATE_INITIAL,STATE_INTEGER,STATE_POINT,STATE_POINT_WITHOUT_INT,STATE_FRACTION,STATE_EXP,STATE_EXP_SIGN,STATE_EXP_NUMBER,STATE_SIGN,STATE_END
}
}

复杂度分析:

  • 时间复杂度为O(n),其中n表示字符串的长度。算法需要对字符串中的每个字符进行遍历,因此时间复杂度与字符串的长度成正比。
  • 空间复杂度为O(1),因为算法只使用了常数个变量和一个固定大小的哈希表(状态转移规则),不随输入规模的增加而增加额外的空间消耗。因此,算法的空间复杂度是常数级别的。

LeetCode运行结果:

方法二:正则表达式

除了有限状态自动机,还可以使用正则表达式来判断一个字符串是否为有效数字。Java中提供了一个函数matches(String regex)来判断一个字符串是否能够匹配指定的正则表达式。

class Solution {
public boolean isNumber(String s) {// 使用正则表达式匹配字符串return s.trim().matches("[+-]?(?:\\d+\\.?\\d*|\\.\\d+)(?:[Ee][+-]?\\d+)?");
}
}

复杂度分析:

该算法的时间复杂度为O(1),因为使用了Java内置函数,时间复杂度是固定的。空间复杂度为O(1),因为没有使用额外的空间。

需要注意的是,使用正则表达式虽然代码简单易懂,但是性能可能不如有限状态自动机。正则表达式求解的时间复杂度是O(n),其中n是字符串长度,适用于一些简单的模式匹配。对于复杂模式,引擎会消耗非常多的时间和空间,建议在使用时注意性能问题。

LeetCode运行结果:

第三题

题目来源

66. 加一 - 力扣(LeetCode)

题目内容

解决方法

方法一:从最后一位向前遍历

该方法从数组的最后一位开始向前遍历,将当前位加一,如果加一后不需要进位,则直接返回结果。如果加一后需要进位,则将当前位置为0,并继续处理前一位。如果所有位都需要进位,则返回新的结果数组,长度为原数组长度加一,首位为1,其余位为0。

class Solution {
public int[] plusOne(int[] digits) {int n = digits.length;// 从最后一位开始向前遍历for (int i = n - 1; i >= 0; i--) {// 当前位加一digits[i]++;// 如果当前位加一后仍然小于10,没有进位,直接返回结果if (digits[i] < 10) {return digits;}// 有进位,当前位变为0,继续处理前一位digits[i] = 0;}// 若所有位都有进位,则数组长度需要增加1,首位为1,后面全是0int[] result = new int[n + 1];result[0] = 1;return result;
}}

复杂度分析:

  • 时间复杂度:O(n),其中n为数组的长度。在最坏情况下,需要遍历整个数组一次。
  • 空间复杂度:O(n),需要创建一个新的结果数组,长度可能为n+1。

LeetCode运行结果:

方法二:数学运算

还可以使用数学运算来实现加一操作。

  1. 首先将数组最后一位加一,记录进位carry。
  2. 从数组倒数第二位开始,将当前位加上进位carry,并更新进位carry。
  3. 如果进位carry为0,则无需继续处理,直接返回结果数组。
  4. 如果进位carry不为0,则继续向前处理前一位。
  5. 如果处理完所有位后,进位carry仍然不为0,说明需要扩展结果数组的长度,将原数组复制到新的结果数组中,并在首位插入进位carry。
class Solution {
public int[] plusOne(int[] digits) {int n = digits.length;int carry = 1; // 进位初始化为1// 从数组最后一位开始计算for (int i = n - 1; i >= 0; i--) {digits[i] += carry; // 当前位加上进位carry = digits[i] / 10; // 计算新的进位digits[i] %= 10; // 当前位取模,得到个位数// 如果进位为0,说明不需要再进位,直接返回结果数组if (carry == 0) {return digits;}}// 若所有位都有进位,则数组长度需要增加1,首位为进位carry,后面全是0int[] result = new int[n + 1];result[0] = carry;System.arraycopy(digits, 0, result, 1, n);return result;
}}

复杂度分析:

  • 时间复杂度:遍历数组需要线性时间O(n),其中每个元素只进行一次常数级别的数学运算,所以总体时间复杂度也是O(n)。
  • 空间复杂度:除了原数组外,需要在进位的情况下创建一个新数组来存储结果,所以空间复杂度为O(n)。

LeetCode运行结果:

相关文章:

怒刷LeetCode的第26天(Java版)

第一题 题目来源 64. 最小路径和 - 力扣&#xff08;LeetCode&#xff09; 题目内容 解决方法 方法一&#xff1a;动态规划 可以使用动态规划来解决这个问题。 首先创建一个与网格大小相同的二维数组dp&#xff0c;用于存储从起点到每个位置的最小路径和。然后初始化dp[0…...

Linux文件基本权限

一、Linux权限 简介 在Linux系统中,每个文件和目录都有读(r),写(w)和执行(x)权限,这些权限决定了用户对该文件或目录的访问方式。Linux服务器上有严格的权限等级,如果权限过高导致误操作会增加服务器的风险。文件权限 只有root用户和文件拥有者才可以修改文件访问权…...

Unity设计模式——装饰模式

装饰模式&#xff08;Decorator&#xff09;&#xff0c;动态地给一个对象添加一些额外的职责&#xff0c;就增加功能来说&#xff0c;装饰模式比生成子类更为灵活。 Component类&#xff1a; abstract class Component : MonoBehaviour {public abstract void Operation(); …...

Http请求响应 Ajax 过滤器

10/10/2023 近期总结&#xff1a; 最近学的后端部署&#xff0c;web服务器运行&#xff0c;各种请求响应&#xff0c;内容很多&#xff0c;学的很乱&#xff0c;还是需要好好整理&#xff0c;前面JavaSE内容还没有完全掌握&#xff0c;再加上一边刷题&#xff0c;感觉压力很大哈…...

【Qt控件之QTableWidget】使用及技巧

简介 QTableWidget是Qt中的表格控件&#xff0c;用于显示和编辑二维表格数据&#xff0c;QTableView类的子类。 可以和定时器结合&#xff0c;实现定时刷新表格中的数据或执行其他与表格相关的操作。 主要函数说明 定时器相关函数(用于刷新表格数据)&#xff1a; void startT…...

算法-动态规划/中心扩散法-最长回文子串

算法-动态规划/中心扩散法-最长回文子串 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/longest-palindromic-substring 1.2 题目描述 2 动态规划 2.1 思路 dp[i][j] 表示[i,j]之间的字符串是否是回文。 那么&#xff0c;如果chars[i] chars[j]时&#xff0c;就…...

(6)SpringMVC中使用CharacterEncodingFilter编码过滤器处理请求和响应的乱码问题

处理SpringMVC中乱码问题 处理原生Servlet中请求和响应的乱码问题,参考文章 Servlet中的过滤器的实现及其原理,参考文章 配置CharacterEncodingFilter 在Servlet规范中要求request和response对象设置编码之前不能有获取请求参数和响应数据的操作,否则后续设置的编码都将不起…...

USB协议层数据格式

USB协议 1. 硬件拓扑结构2. 协议层2.1 字节/位传输顺序2.2 SYNC域2.3 包格式2.3.1 PID域2.3.2 令牌包(Token)2.3.3 数据包2.3.4 握手包 2.4 传输细节2.4.1 传输(Transfer)和事务(Transaction)2.4.2 过程(stage)和阶段(phase)2.4.3 批量传输2.4.4 中断传输2.4.5 实时传输2.4.6 控…...

加密的重要性,MySQL加密有哪些好处?

加密是一种将信息转化为无法直接读取的格式的技术&#xff0c;从而保护信息安全。在当今数字化的世界中&#xff0c;数据已成为企业的重要资产&#xff0c;因此加密的重要性不言而喻。在这篇文章中&#xff0c;我们将探讨MySQL加密的好处以及如何选择合适的加密算法。 MySQL加密…...

Python为Excel中每一个单元格计算其在多个文件中的平均值

本文介绍基于Python语言&#xff0c;对大量不同的Excel文件加以跨文件、逐单元格平均值计算的方法。 首先&#xff0c;我们来明确一下本文的具体需求。现有一个文件夹&#xff0c;其中有如下所示的大量Excel文件&#xff0c;我们这里就以.csv文件为例来介绍。其中&#xff0c;每…...

LLM 系列之 Transformer 组件总结

本系列为LLM 学习博客&#xff0c;会一一记录各个模块解读。 以下内容参考:大语言模型综述 https://github.com/RUCAIBox/LLMSurvey 主流架构 大语言模型&#xff0c;主要的核心组件是Transformer。不同的模型选择的架构不一样&#xff0c;目前主流架构有&#xff1a; 编码器…...

计算机等级考试—信息安全三级真题十

目录 一、单选题 二、填空题 三、综合题 一、单选题...

面试总结(mysql定精度/oom排查/spring三级缓存/stream流)

Mysql数据类型上的一个把握 1、MySQL Decimal为什么不会丢失精度 DECIMAL的存储方式和其他数据类型都不同&#xff0c;它是以字符串形式存储的。假设一个字段为DECIMAL(3,0)&#xff0c;当我们存入100时&#xff0c;实际上存入的1、0、0这三个字符拼接而成的字符串的二进制值&…...

uniapp四个元素点击那个哪个变色,其他的还变原来的颜色

在UniApp中&#xff0c;可以使用CSS伪类选择器和动态样式绑定来实现点击某个元素时改变其颜色的效果。假设有四个元素分别为A、B、C和D。 首先&#xff0c;为这四个元素添加一个共同的类名&#xff0c;例如"item"。 然后&#xff0c;在页面的样式中定义两种颜色&am…...

Springcloud笔记(2)-Eureka服务注册

Eureka服务注册 服务注册&#xff0c;发现。 在Spring Cloud框架中&#xff0c;Eureka的核心作用是服务的注册和发现&#xff0c;并实现服务治理。 Eureka包含两个组件&#xff1a;Eureka Server和Eureka Client。 Eureka Server提供服务注册服务&#xff0c;各个节点启动后…...

国庆 day 5

QT实现TCP服务器客户端搭建的代码&#xff0c;现象 服务器 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);server new QTcpServer(this);connect (server,&…...

计算机网络 | OSI 参考模型

计算机网络 | OSI 参考模型 计算机网络 | OSI 参考模型应用层表示层会话层传输层网络层数据链路层物理层 参考视频&#xff1a;王道计算机考研 计算机网络 参考书&#xff1a;《2022年计算机网络考研复习指导》 计算机网络 | OSI 参考模型 OSI 参考模型自下而上分为7层&…...

uniapp 实现地图头像上的水波纹效果

最近实现了uniapp 地图头像水波纹的效果&#xff0c;话不多说&#xff0c;先来看看视频效果吧&#xff1a;链接 在这里具体的代码就不放出来了&#xff0c;还是利用了uniapp的 uni.createAnimation 方法&#xff0c;因为cover-view 不支持一些css 的动画效果&#xff0c;所以这…...

Zabbix7.0 LTS新功能

一、简介 LTS是长期支持。LTS版本支持5年。如果更喜欢稳定性&#xff0c;未涉及到最新的功能&#xff0c;可以选次新的LTS或者更低解决方案。而Zabbix6.4是最新的主要版本不属于LTS版本。 二、新功能 从以下几个方面介绍部分新功能&#xff1a; 性能提升&#xff1a;内存储存…...

充电100%并非都是美事,有时少点更有溢出!如何正确为iPhone充电

iPhone是非凡的设备&#xff0c;但一旦电池耗尽&#xff0c;它们就会失去光泽。这就是为什么照看电池内部并确保始终正确充电很重要。 在这篇文章中&#xff0c;我们解释了如果你想让你的iPhone每天运行到深夜&#xff0c;并尽可能多地保持这种状态&#xff0c;你需要采取的步…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...

uniapp获取当前位置和经纬度信息

1.1. 获取当前位置和经纬度信息&#xff08;需要配置高的SDK&#xff09; 调用uni-app官方API中的uni.chooseLocation()&#xff0c;即打开地图选择位置。 <button click"getAddress">获取定位</button> const getAddress () > {uni.chooseLocatio…...