当前位置: 首页 > 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;你需要采取的步…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

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

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

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...