怒刷LeetCode的第28天（Java版）

2023-10-28 20:01
文章标签 java leetcode 28 怒刷

本文主要是介绍怒刷LeetCode的第28天（Java版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

第一题

题目来源

题目内容

解决方法

方法一：动态规划

方法二：迭代

方法三：斐波那契数列公式

第二题

题目来源

题目内容

解决方法

方法一：栈

方法二：路径处理类

方法三：正则表达式

方法四：字符串处理

第三题

题目来源

题目内容

解决方法

方法一：动态规划

第一题

题目来源

70. 爬楼梯 - 力扣（LeetCode）

题目内容

解决方法

方法一：动态规划

可以使用动态规划的方法来解决这个问题。假设要爬到第n阶楼梯，那么可以从第n-1阶楼梯爬一步上来，或者从第n-2阶楼梯爬两步上来。因此，到达第n阶楼梯的方法数等于到达第n-1阶楼梯的方法数加上到达第n-2阶楼梯的方法数。

首先初始化前两个楼梯的方法数，即dp[0]=1和dp[1]=1。然后从第3个楼梯开始，通过迭代计算每个楼梯的方法数，直到第n个楼梯。

class Solution {
public int climbStairs(int n) {if (n <= 1) {return 1;}int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}
}

复杂度分析：

  • 这个算法的时间复杂度是O(n)，其中n是楼梯的阶数。这是因为我们需要计算从第2阶楼梯到第n阶楼梯的方法数，每次计算都需要常数时间。
  • 空间复杂度是O(n)，因为我们使用一个大小为n+1的数组来存储每个楼梯的方法数。如果只需要存储前两个楼梯的方法数，空间复杂度可以优化为O(1)。

总结起来，这个算法是相当高效的，可以在合理的时间内解决规模较大的问题。

LeetCode运行结果：

方法二：迭代

除了动态规划，还可以使用迭代的方法来解决这个问题。迭代方法的思路是从前往后计算每个楼梯的方法数，并利用一个变量来保存前两个楼梯的方法数，以便计算当前楼梯的方法数。

class Solution {
public int climbStairs(int n) {if (n <= 1) {return 1;}int prev1 = 1; // 到达前一个楼梯的方法数int prev2 = 1; // 到达前两个楼梯的方法数int current = 0; // 当前楼梯的方法数for (int i = 2; i <= n; i++) {current = prev1 + prev2;prev2 = prev1;prev1 = current;}return current;
}
}

复杂度分析：

  • 时间复杂度： 在迭代方法中，我们使用一个循环来计算每个楼梯的方法数，循环执行了n-2次（从第3个楼梯开始计算）。因此，时间复杂度为O(n)。
  • 空间复杂度： 在迭代方法中，我们只使用了三个变量：prev1、prev2和current来保存楼梯的方法数。这三个变量的空间占用是常量级别的，与输入规模n无关。因此，空间复杂度为O(1)。

综上所述，迭代方法的时间复杂度为O(n)，空间复杂度为O(1)。

LeetCode运行结果：

方法三：斐波那契数列公式

除了动态规划和迭代，还可以使用斐波那契数列公式的方法来解决爬楼梯问题。

斐波那契数列公式是一个通用的公式，可以用来计算斐波那契数列中任意一项的值。在爬楼梯问题中，我们可以利用斐波那契数列公式来计算到达第n阶楼梯的方法数。

具体步骤如下：

  1. 定义常量phi为(1 + sqrt(5)) / 2，定义常量psi为(1 - sqrt(5)) / 2。
  2. 利用斐波那契数列公式，计算第n+1项斐波那契数列的值，即Fn+1 = (phi^(n+1) - psi^(n+1)) / sqrt(5)。
  3. 最后，到达第n阶楼梯的方法数即为Fn+1。
class Solution {
public int climbStairs(int n) {double phi = (1 + Math.sqrt(5)) / 2;double psi = (1 - Math.sqrt(5)) / 2;double fn = (Math.pow(phi, n + 1) - Math.pow(psi, n + 1)) / Math.sqrt(5);return (int) Math.round(fn);
}
}

复杂度分析：

  • 时间复杂度：O(1)，直接使用斐波那契数列公式计算结果。
  • 空间复杂度：O(1)，只需要常量级的额外空间。

LeetCode运行结果：

第二题

题目来源

71. 简化路径 - 力扣（LeetCode）

题目内容

解决方法

方法一：栈

class Solution {public String simplifyPath(String path) {Deque<String> stack = new LinkedList<>();String[] components = path.split("/");for (String component : components) {if (component.equals(".") || component.isEmpty()) {// 当前目录，忽略} else if (component.equals("..")) {// 上级目录，弹出栈顶元素if (!stack.isEmpty()) {stack.pop();}} else {// 其他目录，入栈stack.push(component);}}StringBuilder sb = new StringBuilder();while (!stack.isEmpty()) {sb.append("/");sb.append(stack.pollLast());}return sb.length() == 0 ? "/" : sb.toString();}
}

思路解析：

  1. 将路径按照"/"分割成多个组件，存储在数组components中。
  2. 遍历components数组，对于每个组件进行如下处理：
    • 如果是"."或空字符串，表示当前目录，忽略即可。
    • 如果是".."，表示上级目录，将栈顶元素弹出。
    • 否则，表示其他目录，将其入栈。
  3. 遍历完所有组件后，将栈中元素依次弹出，拼接成简化后的路径。注意，由于栈是先进后出的，所以需要使用pollLast方法依次弹出栈顶元素。

复杂度分析：

时间复杂度分析：

  • 字符串的split方法的时间复杂度为O(n)，其中n是路径的长度。因为需要遍历整个路径字符串，并根据"/"进行分割。
  • 遍历components数组的时间复杂度为O(m)，其中m是路径中的组件数量。最坏情况下，路径中的组件数量与路径长度相等。
  • 栈的操作（入栈和出栈）的时间复杂度为O(1)。

综上所述，总的时间复杂度为O(n + m)。

空间复杂度分析：

  • components数组的空间复杂度为O(m)，其中m是路径中的组件数量。
  • 栈的空间复杂度最坏情况下为O(m)，即路径中每个组件都不同。
  • StringBuilder的空间复杂度为O(n)，其中n是路径的长度。

综上所述，总的空间复杂度为O(n + m)。

LeetCode运行结果：

方法二：路径处理类

除了栈，还可以使用Java的路径处理类Path和Paths来实现简化路径。

思路解析：

  1. 使用Paths.get方法将路径字符串转换为Path对象。
  2. 遍历Path对象中的每个组件（即目录名或文件名）。
  3. 如果当前组件不是"."或".."，表示是有效的目录名或文件名，将其拼接到结果字符串中。
  4. 如果当前组件是".."，表示需要返回上级目录，将结果字符串中最后一个目录名删除即可。
import java.nio.file.Path;
import java.nio.file.Paths;class Solution {public String simplifyPath(String path) {Path p = Paths.get(path);StringBuilder sb = new StringBuilder();for (Path component : p) {if (!component.toString().equals("..") && !component.toString().equals(".")) {sb.append("/");sb.append(component.toString());} else if (component.toString().equals("..")) {int len = sb.length();if (len > 1) {sb.delete(sb.lastIndexOf("/"), len);}}}return sb.length() == 0 ? "/" : sb.toString();}
}

复杂度分析：

时间复杂度分析：

  • Paths.get方法的时间复杂度为O(n)，其中n是路径的长度。
  • 遍历Path对象中的每个组件的时间复杂度为O(m)，其中m是路径中的组件数量。
  • StringBuilder的操作的时间复杂度为O(n)，其中n是路径的长度。

综上所述，总的时间复杂度为O(n + m)。

空间复杂度分析：

  • Path对象的空间复杂度为O(m)，其中m是路径中的组件数量。
  • StringBuilder的空间复杂度为O(n)，其中n是路径的长度。

综上所述，总的空间复杂度为O(n + m)。

LeetCode运行结果：

方法三：正则表达式

除了栈和Java的路径处理类，还可以使用正则表达式来实现简化路径。

思路解析：

  1. 将路径按照"/"分割成多个组件，存储在数组components中。
  2. 遍历components数组，对于每个组件进行如下处理：
    • 如果是"."或空字符串，表示当前目录或空目录，忽略即可。
    • 如果是".."，表示上级目录，将结果字符串中最后一个目录名删除即可。
    • 否则，表示其他目录，将其拼接到结果字符串中。
  3. 遍历完所有组件后，返回结果字符串。注意，如果结果字符串为空，则表示路径为根目录，需要返回"/"。
class Solution {public String simplifyPath(String path) {String[] components = path.split("/");StringBuilder sb = new StringBuilder();for (String component : components) {if (component.equals("..")) {// 返回上级目录，将结果字符串中最后一个目录名删除即可。int len = sb.length();if (len > 1) {sb.delete(sb.lastIndexOf("/"), len);}} else if (!component.equals(".") && !component.isEmpty()) {// 忽略当前目录和空目录，其他目录拼接到结果字符串中。sb.append("/");sb.append(component);}}return sb.length() == 0 ? "/" : sb.toString();}
}

复杂度分析：

时间复杂度分析：

  • 字符串的split方法和StringBuilder的append方法都是线性时间复杂度的，所以总时间复杂度为O(n)，其中n是路径的长度。

空间复杂度分析：

  • components数组的空间复杂度为O(m)，其中m是路径中的组件数量。
  • StringBuilder的空间复杂度为O(n)，其中n是路径的长度。

综上所述，总的空间复杂度为O(n + m)。

LeetCode运行结果：

方法四：字符串处理

除了栈、Java的路径处理类、正则表达式，还可以使用字符串处理方法来实现简化路径。

思路解析：

  1. 使用两个指针i和j来遍历路径字符串path。
  2. 当指针i在路径中遇到连续的斜杠时，跳过这些多余的斜杠。
  3. 当指针i遇到非斜杠字符时，将其作为目录名的一部分，存储在StringBuilder对象dirName中。
  4. 检查dirName中的目录名：
    • 如果是"."或空字符串，表示当前目录或空目录，忽略即可。
    • 如果是".."，表示上级目录，将结果字符串中最后一个目录名删除即可。
    • 否则，表示其他目录，将其拼接到结果字符串中。
  5. 继续遍历路径字符串，直到遍历完所有字符。
  6. 返回结果字符串。如果结果字符串为空，则表示路径为根目录，需要返回"/"。
class Solution {public String simplifyPath(String path) {StringBuilder sb = new StringBuilder();int n = path.length();int i = 0;while (i < n) {// 跳过多余的斜杠while (i < n && path.charAt(i) == '/') {i++;}// 获取当前目录名StringBuilder dirName = new StringBuilder();while (i < n && path.charAt(i) != '/') {dirName.append(path.charAt(i));i++;}// 处理当前目录名String name = dirName.toString();if (name.equals("..")) {// 返回上级目录，将结果字符串中最后一个目录名删除即可。int len = sb.length();if (len > 1) {sb.delete(sb.lastIndexOf("/"), len);}} else if (!name.equals(".") && !name.isEmpty()) {// 忽略当前目录和空目录，其他目录拼接到结果字符串中。sb.append("/");sb.append(name);}}return sb.length() == 0 ? "/" : sb.toString();}
}

复杂度分析：

时间复杂度分析：

  • 遍历路径字符串的过程是线性时间复杂度的，所以总时间复杂度为O(n)，其中n是路径的长度。

空间复杂度分析：

  • StringBuilder的空间复杂度为O(n)，其中n是路径的长度。

综上所述，总的空间复杂度为O(n)。

LeetCode运行结果：

第三题

题目来源

72. 编辑距离 - 力扣（LeetCode）

题目内容

解决方法

方法一：动态规划

这是一道典型的动态规划问题。

定义状态：dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最少操作数。

状态转移方程：

  • 当word1[i] == word2[j]时，不需要进行任何操作，dp[i][j] = dp[i-1][j-1]。

  • 当word1[i] != word2[j]时，可以进行三种操作：

    • 插入一个字符：dp[i][j] = dp[i][j-1] + 1。
    • 删除一个字符：dp[i][j] = dp[i-1][j] + 1。
    • 替换一个字符：dp[i][j] = dp[i-1][j-1] + 1。

最终结果为dp[m][n]，其中m和n分别是word1和word2的长度。

class Solution {
public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// 创建动态规划数组int[][] dp = new int[m+1][n+1];// 初始化边界条件for (int i = 0; i <= m; i++) {dp[i][0] = i;}for (int j = 0; j <= n; j++) {dp[0][j] = j;}// 动态规划求解for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i-1) == word2.charAt(j-1)) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;}}}return dp[m][n];
}
}

复杂度分析：

该算法的时间复杂度为O(m*n)，其中m和n分别是word1和word2的长度。

在动态规划求解过程中，需要填充一个大小为(m+1)(n+1)的二维数组dp。对于每个位置(i, j)，都需要通过比较word1.charAt(i-1)和word2.charAt(j-1)来确定操作的类型。因此，总共需要进行mn次比较和计算。

空间复杂度方面，需要额外开辟一个大小为(m+1)(n+1)的二维数组dp来保存中间结果。因此，空间复杂度也为O(mn)。

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

LeetCode运行结果：

这篇关于怒刷LeetCode的第28天（Java版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/295614。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2