怒刷LeetCode的第4天（Java版）

2023-09-17 14:00:39

#【中秋征文】程序人生，中秋共享#

目录

第一题

题目来源

题目内容

解决方法

方法一：遍历字符串

方法二：有限状态机（Finite State Machine）

方法三：正则表达式

第二题

题目来源

题目内容

解决方法

方法一：反转数字比较

第三题

题目来源

题目内容

解决方法

方法一：动态规划

方法二：递归回溯

第一题

题目来源

8. 字符串转换整数 (atoi) - 力扣（LeetCode）

题目内容

解决方法

方法一：遍历字符串

题目要求实现一个字符串转换整数的函数，即将给定字符串转换成一个32位有符号整数。

解题思路如下：

  1. 去除字符串开头的空格。

  2. 判断接下来的字符是否为正号或者负号，如果是则记录符号并向后移动一位。

  3. 遍历剩余的字符串字符，直到遇到非数字字符为止。将遇到的数字字符转换成整数，并累加到结果中。

  4. 根据符号和结果判断最终返回的整数值。

  5. 注意处理越界情况，如果超出32位有符号整数的取值范围，则返回边界值。

class Solution {
    public int myAtoi(String s) {
    // 去除前导空格
    s = s.trim();
    
    // 处理空字符串和只有正负号的情况
    if (s.length() == 0 || (s.length() == 1 && (s.charAt(0) == '+' || s.charAt(0) == '-'))) {
        return 0;
    }
    
    // 判断第一个非空字符是否为正负号
    boolean positive = true;
    int i = 0;
    if (s.charAt(0) == '+' || s.charAt(0) == '-') {
        if (s.charAt(0) == '-') {
            positive = false;
        }
        i++;
    }
    
    // 提取连续的数字字符并转换为整数
    long result = 0; // 使用长整型，防止溢出
    while (i < s.length() && Character.isDigit(s.charAt(i))) {
        int digit = s.charAt(i) - '0';
        result = result * 10 + digit;
        
        // 判断是否超出范围
        if (positive && result > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else if (!positive && result * -1 < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        
        i++;
    }
    
    // 根据正负号返回最终结果
    return positive ? (int)result : (int)(result * -1);
}
}

这个函数首先去除字符串的前导空格，然后判断字符串是否为空或只有正负号的情况，如果是，则返回0。接下来，判断第一个非空字符是正号还是负号，并将其处理为正负标志。然后，遍历字符串的剩余部分，将连续的数字字符转换为整数，并判断是否超出范围。最后，根据正负标志返回最终结果。 

下面是该解决方案的复杂度分析：

  • 时间复杂度：O(n)，其中 n 是字符串的长度。在算法中，我们只遍历字符串一次。
  • 空间复杂度：O(1)。除了存储结果之外，算法使用的额外空间是固定大小的变量，并不随输入的规模而改变。

需要注意的是，在判断是否超出范围时，我们使用了长整型变量 result，而不是直接使用整型变量。这是因为如果 result 溢出 32 位有符号整数的范围，将无法正确判断溢出。所以我们将连续数字字符转换为长整型，然后再判断是否超出范围，并根据正负号返回最终结果。

LeetCode运行结果：

方法二：有限状态机（Finite State Machine）

还有其他方法可以解决这个问题。一种常见的方法是使用有限状态机（Finite State Machine）。有限状态机的基本思想是根据输入的字符和当前状态进行状态转移，最终得到结果。

class Solution {
    public int myAtoi(String s) {
    Automaton automaton = new Automaton();
    for (char c : s.toCharArray()) {
        if (!automaton.process(c)) {
            break;
        }
    }
    return (int) (automaton.sign * automaton.result);
}

class Automaton {
    public int sign = 1; // 符号，默认为正号
    public long result = 0; // 结果，默认为0
    private String state = "start"; // 初始状态
    
    private Map<String, String[]> transitionTable = new HashMap<>(){{
        put("start", new String[]{"start", "signed", "inNumber", "end"});
        put("signed", new String[]{"end", "end", "inNumber", "end"});
        put("inNumber", new String[]{"end", "end", "inNumber", "end"});
        put("end", new String[]{"end", "end", "end", "end"});
    }};
    
    public boolean process(char c) {
        state = transitionTable.get(state)[getStateIndex(c)];
        if ("inNumber".equals(state)) {
            result = result * 10 + (c - '0');
            result = sign == 1 ? Math.min(result, Integer.MAX_VALUE) : Math.min(result, -1L * Integer.MIN_VALUE);
        } else if ("signed".equals(state)) {
            sign = c == '+' ? 1 : -1;
        } else if ("end".equals(state)) {
            return false;
        }
        return true;
    }
    
    private int getStateIndex(char c) {
        if (c == ' ') {
            return 0;
        }
        if (c == '+' || c == '-') {
            return 1;
        }
        if (Character.isDigit(c)) {
            return 2;
        }
        return 3;
    }
}
}

在这个解决方案中，我们使用了一个包含四个状态的有限状态机。根据当前状态和输入字符的类型，我们进行状态转移，并更新符号和结果。具体的状态转移规则可以在 transitionTable 中定义。

这个解决方案的时间复杂度为 O(n)，空间复杂度为 O(1)。

LeetCode运行结果：

方法三：正则表达式

正则表达式是一种强大的模式匹配工具，可以用来匹配和提取字符串中的特定模式。

import java.util.regex.Pattern;
import java.util.regex.Matcher;

class Solution {
    public int myAtoi(String s) {
    String pattern = "^\\s*([+-]?\\d+)";
    Pattern regex = Pattern.compile(pattern);
    Matcher matcher = regex.matcher(s);
    
    if(matcher.find()) {
        try {
            long num = Long.parseLong(matcher.group(1));
            
            if (num > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            } else if (num < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            } else {
                return (int) num;
            }
        } catch (NumberFormatException e) {
            // 处理超出整数范围的情况
            if (matcher.group(1).charAt(0) == '-') {
                return Integer.MIN_VALUE;
            } else {
                return Integer.MAX_VALUE;
            }
        }
    }
    
    return 0; // 如果无法匹配数字，则返回0
}
}

在这个解决方案中，我们使用了正则表达式 ^\\s*([+-]?\\d+) 来匹配字符串中的数字。首先，使用 Pattern 类编译正则表达式，并使用 Matcher 类对输入字符串进行匹配。如果在字符串中找到一个或多个数字序列，我们尝试将其转换为长整型 num。然后，我们检查 num 是否超出了整数的范围，并根据结果返回相应的值。

这个解决方案的时间复杂度取决于正则表达式的匹配速度，通常为 O(n)。空间复杂度为 O(1)，因为只使用了有限的变量来存储结果。

LeetCode运行结果：

第二题

题目来源

9. 回文数 - 力扣（LeetCode）

题目内容

解决方法

方法一：反转数字比较

class Solution {
    public boolean isPalindrome(int x) {
    // 处理特殊情况，负数和以0结尾的非零数不可能是回文数
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    
    int reverse = 0;
    int original = x;
    while (x > 0) {
        int digit = x % 10;
        reverse = reverse * 10 + digit;
        x /= 10;
    }
    
    return original == reverse;
}

}

在这个解决方案中，我们首先处理了一些特殊情况：负数和以0结尾的非零数不可能是回文数。然后，我们使用一个循环，将输入的数字逐位反转并保存到变量 reverse 中。最后，我们检查反转后的数字是否等于原始数字 x。

这个方法的时间复杂度是 O(log n)，其中 n 是 x 的位数。空间复杂度是 O(1)。

LeetCode运行结果：

第三题

题目来源

10. 正则表达式匹配 - 力扣（LeetCode）

题目内容

解决方法

方法一：动态规划

这是一个经典的正则表达式匹配问题，可以使用动态规划来解决。具体的思路如下：

  1. 定义一个二维布尔数组 dp，其中 dp[i][j] 表示 s 的前 i 个字符是否与 p 的前 j 个字符匹配。
  2. 初始化 dp[0][0] 为 true，表示空字符可以匹配。
  3. 对于第一行 dp[0][j]：如果 p[j-1] 是 ''，则可以把 p[j-2] 和 '' 一起消去，即 dp[0][j] = dp[0][j-2]；否则为 false。
  4. 对于其他行 dp[i][j]：
    • 如果 p[j-1] 是字母或者 '.'，则判断当前字符能否匹配，即 dp[i][j] = dp[i-1][j-1]；
    • 如果 p[j-1] 是 '*'，有两种情况：
      • "表示匹配零次前面的元素，即将 p[j-2] 和 "一起消去，即 dp[i][j] = dp[i][j-2]；
      • '*' 表示匹配一次或多次前面的元素，即当前字符与 p[j-2] 匹配且前一个字符匹配（dp[i-1][j]）。

最后，返回 dp[s.length()][p.length()]。

class Solution {
public boolean isMatch(String s, String p) {
    int m = s.length();
    int n = p.length();
    
    // 创建并初始化 dp 数组
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true; // 空字符串和空模式匹配
    
    // 处理边界情况，s 为空字符串时的匹配
    for (int j = 1; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 2]; // '*' 可以将前面的字符匹配 0 次
        }
    }
    
    // 动态规划求解
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 如果当前字符匹配，则和上一个字符的匹配结果一致
            if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p.charAt(j - 1) == '*') {
                // 如果遇到 '*' 字符，有两种情况：
                // 1. '*' 匹配了前一个字符 0 次，则和 p 的前两个字符匹配结果一致
                // 2. '*' 匹配了前一个字符多次，则当前字符和前面的模式字符串匹配，
                //    并且和上一个字符的匹配结果一致
                dp[i][j] = dp[i][j - 2]; // 匹配 0 次的情况
                if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }
    
    return dp[m][n];
}

}

这个算法的时间复杂度是 O(m * n)，其中 m 是字符串 s 的长度，n 是模式 p 的长度。空间复杂度是 O(m * n)。 

LeetCode运行结果：

方法二：递归回溯

除了动态规划，还可以使用递归回溯的方法来解决。具体的思路是从左到右依次匹配字符，对于每个字符，有如下几种情况：

  1. 如果当前字符和模式字符相同，或者模式字符是 '.'，则继续匹配下一个字符。
  2. 如果模式字符是 '*'，有两种情况：
    • 模式字符和前一个字符不匹配，并且当前字符也和模式字符的前一个字符不匹配，则只能将 '*' 视为匹配 0 次前面的字符，继续匹配后面的字符。
    • 其他情况下，可以将 '*' 视为匹配 0 次、1 次或多次前面的字符，然后继续匹配下一个字符。

如果能够成功匹配到最后一个字符，则字符串和字符规律匹配成功。

class Solution {
public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }

        boolean firstMatch = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        
        if (p.length() >= 2 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p));
        } else {
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
    }
}

复杂度分析：

  • 时间复杂度：最坏情况下，对于每个字符都存在两种选择（匹配 0 次或多次），因此时间复杂度是指数级的，即 O(2^(m + n))，其中 m 和 n 分别是字符串 s 和模式 p 的长度。
  • 空间复杂度：递归过程中需要消耗额外的栈空间，最坏情况下递归深度是字符串 s 和模式 p 的长度的和，因此空间复杂度为 O(m + n)。

综上所述，动态规划方法在时间和空间复杂度上都优于递归回溯方法。在实际应用中，建议使用动态规划方法来解决这个问题，尤其是在输入规模较大时。

LeetCode运行结果：

更多推荐

Hive的分区和分桶

目录​编辑一、Hive分区1.1分区产生的背景1.2动态分区1.2.1hive的动态分区介绍1.2.2动态分区配置1.2.2.1动态分区开启1.2.2.2动态分区模式1.2.2.3一个mr节点上，设置动态分区的最大数量1.2.2.4所有mr节点上，设置所有动态分区的最大数量1.2.2.5设置所有mrjob允许创建的文件

软件测试未来的发展趋势以及软件测试进阶路线

【软件测试行业现状】2023年了你还敢学软件测试？未来已寄..测试人该何去何从？【自动化测试、测试开发、性能测试】全球各地的企业每天都在发展变化着，以应对市场挑战，满足日益成熟的客户需求。即使是正在进行的技术进步也会使软件测试专家在实践的过程中更加专注和精确。2021年给软件测试领域带来了新的技术解决方案，以及质量保证

【2023】Git版本控制-远程仓库详解

目录创建远程仓库向远程仓库推送数据文件从第二台主机本地拉取远程仓库数据第一台主机同步远程仓库数据tag标签git忽略文件Git远程仓库是Git版本控制系统的一个概念，它是一个存储Git代码的远程服务器。你可以将本地Git仓库上传到远程仓库，以便与其他人协作开发或备份代码。创建远程仓库远程仓库可以使用第三方平台，如（gi

AI无法提振台积电股价

来源：猛兽财经作者：猛兽财经总结：（1）台积电的股价已经从最高点下跌了18%，很多期权交易员正在押注台积电的股价会进一步下跌。（2）华尔街分析师目前也下调了台积电的收入和盈利预期。台积电(TSM)的股价最近这段时间已经跌回到了了5月份之前的水平，很多期权交易员也正在押注台积电股价将在10月中旬进一步下跌。台积电股价的溢

服务器上一个域名对应多个前端项目的nginx转发配置

场景：当有两个前端项目A,B的时候，项目A（对应端口8000）和项目B（对应端口8001）分别部署在服务器的不同位置，通过服务器ip+端口都能正常访问单独的项目A和项目B；现在要求两个项目共用一个域名~~也就是说访问http://10.111.182.xxx:8000的时候默认访问项目A的资源，访问http://10.

MyBatis 基本使用

文章目录创建项目POJO对象添加配置文件编程式的使用代理方式的使用接口声明映射文件getMapper总结创建项目创建一个普通的Maven项目，然后添加对应的Mybatis和MySQL的相关依赖<dependency><groupId>org.mybatis</groupId><artifactId>mybatis</a

Java中Hashset存储原理底层深挖

上课老师讲了Hashset的添加元素方法，感觉不甚准确，于是下课扒一扒底层源码，这一看，霍！原来如此。现在小丁来捋一遍他的存储原理。publicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;}可以看到PRESENT是一个privatestaticfinal修饰的object

深入浏览器的渲染原理

一、网页的解析过程大家有没有深入思考过：一个网页URL从输入到浏览器中，到显示经历过怎么样的解析过程呢？要想深入理解下载的过程，我们还要先理解，一个index.html被下载下来后是如何被解析和显示在浏览器上的二、浏览器渲染流程1.浏览器的内核常见的浏览器内核有Trident（三叉戟）：IE、360安全浏览器、搜狗高速

【java】【SpringBoot】【三】开发实用篇 基于SpringBoot整合任意第三方技术

目录一、热部署1、手动启动热部署2、自动启动热部署3、热部署范围配置4、关闭热部署二、配置高级1、@ConfigurationProperties2、宽松绑定/松散绑定3、常用计量单位绑定4、数据校验三、测试1、加载测试专用属性2、加载测试专用配置3、web环境模拟测试3.1模拟端口3.2虚拟请求测试3.3匹配响应执行

锂离子电池和电池组安全使用指南

声明本文是学习GB-T42729-2023锂离子电池和电池组安全使用指南.而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们1范围本文件提供了锂离子电池和电池组使用过程中的安全指导和建议，给出了锂离子电池和电池组制造厂商向用户提供可能发生危险的相关信息。本文件适用于锂离子电池和电池组的使用。2规范性引

系统架构设计师（第二版）学习笔记----信息安全基础知识

【原文链接】系统架构设计师（第二版）学习笔记----信息系统基础文章目录一、信息安全的概念1.1信息安全的基本要素1.2信息安全的内容1.3设备安全的内容1.4数据安全的内容1.5内容安全的含义1.6行为安全的含义二、信息存储安全2.1信息存储安全的内容有：2.2信息使用安全的内容2.3用户的标识与验证方法2.4用户存

热文推荐
  1. 云计算的未来：云原生架构和自动化运维的崭露头角

    文章目录云原生架构：重新定义应用开发和部署什么是云原生架构？为什么云原生架构重要？1.弹性和伸缩性2.故障隔离3.更快的交付4.资源利用率5.多云支持云原生架构的实践步骤1：容器化步骤2：微服务步骤3：自动化运维自动化运维：云计算的关键驱动力什么是自动化运维？为什么自动化运维重要？1.复杂性管理2.资源利用率3.错误率

  2. 【汇编】微处理器

    【汇编】微处理器文章目录【汇编】微处理器1、微处理器概念1.1关键词1.2分类2、微处理器结构2.1寄存器2.2寄存器&汇编助记符2.3寄存器组成结构3、地址空间3.1存储空间3.1.1虚拟空间（编程空间）3.1.2线性空间3.2I/O空间4、工作模式4.1实地址模式4.2保护虚拟地址模式4.3虚拟86模式1、微处理器

  3. 中秋特辑：Java事件监听实现一个猜灯谜小游戏

    众所周知，JavaSwing是Java中关于窗口开发的一个工具包，可以开发一些窗口程序，然后由于工具包的一些限制，导致Java在窗口开发商并没有太多优势（当然也有一些第三方的工具包也很好用），不过，在JavaSwing中关于事件的监听机制是我们需要重点掌握的内容。何为事件监听在Java中，事件监听（EventListe

  4. Spring之微服务架构与Spring Cloud

    微服务架构与SpringCloud微服务架构与SpringCloud摘要引言词汇解释详细介绍微服务架构SpringCloud核心组件示例代码：注释：注意事项理解微服务架构的优势详细介绍什么是微服务架构？微服务架构的优势1.可扩展性（Scalability）2.灵活性和快速开发（FlexibilityandRapidDe

  5. Spring高手之路11——BeanDefinition解密：构建和管理Spring Beans的基石

    文章目录1.探索BeanDefinition1.1官方文档对BeanDefinition的解读1.2BeanDefinition关键方法剖析1.3BeanDefinition部分方法的实际运用1.4BeanDefinition深层信息结构梳理2.BeanDefinition构造体系解析2.1BeanDefinition

  6. Java开发 - 探寻Spring的秘密

    前言Spring是企业级J2EE一站式解决方案，提供了整个项目的表现层、业务层、持久层，而且，它的生态特别完善，可以和其他框架无缝对接，现在做Java的哪个项目里没有Spring的说出不去都不信。但往往我们开发者只重视项目是不是run起来了，而忽略了去了解Spring本身，所以很多开发者仅仅是停留在了使用的层次。博主也

  7. JDK8新特性

    Lembda表达式lembda表达式是一个简洁、可传递的匿名函数,实现了把代码块赋值给一个变量的功能是我认为jdk1.8中最让人眼前一亮的特性（我没用过其他函数式的语言）在了解表达式之前，我们先看两个概念函数式接口含有且仅含有一个抽象方法，Lembda表达式需要借助函数式接口实现。通常来说我们在这个接口定义上加上@Fu

  8. Spring复杂对象的3中创建方法

    复杂对象是相对于简单对象可以直接new出的对象。这种对象在Spring中不可以通过简单对象的创建方式来创建。下面我们将通过实现FactoryBean接口、实例工厂、静态工厂三种方法来创建。FactoryBean接口Spring提供FactoryBean接口并且提供了getObject方法是为了支持自定义工厂。通过实现这

  9. 【基础篇】二、parent继承、starter、引导类、内嵌tomcat

    文章目录0、前言1、继承parent2、starter3、引导类4、内嵌tomcat5、SpringBoot项目快速启动0、前言SpringBoot，Boot，鞋子，其设计目的是用来简化Spring框架应用的初始搭建以及开发过程Spring程序缺点：依赖设置繁琐（各个依赖之间版本的适配、依赖排除等活儿得自己调）配置繁琐