怒刷LeetCode的第24天（Java版）

2023-10-06 23:30
文章标签 java leetcode 24 怒刷

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

目录

第一题

题目来源

题目内容

解决方法

方法一：反向遍历

方法二：字符串操作函数

方法三：正则表达式

第二题

题目来源

题目内容

解决方法

方法一：模拟

方法二：递归

方法三：迭代

方法四：数学规律

第三题

题目来源

题目内容

解决方法

方法一：回溯算法

方法二：迭代

第一题

题目来源

58. 最后一个单词的长度 - 力扣（LeetCode）

题目内容

解决方法

方法一：反向遍历

具体的思路是：

  1. 先去除字符串两端的空格，确保字符串没有多余的空格。

  2. 从字符串的最后开始向前遍历，找到第一个非空格字符的位置。

  3. 继续向前遍历，直到遇到空格字符或者到达字符串的开头，记录下遍历过程中的字符数。

  4. 返回记录的字符数，即为最后一个单词的长度。

class Solution {
public int lengthOfLastWord(String s) {// 去除字符串两端的空格s = s.trim();// 遍历字符串，找到最后一个单词的长度int length = 0;for (int i = s.length() - 1; i >= 0; i--) {if (s.charAt(i) == ' ') {break;}length++;}return length;
}
}

复杂度分析：

时间复杂度分析：

  • 字符串去除两端空格的操作的时间复杂度是 O(n)，其中 n 是字符串的长度。
  • 从字符串的最后开始向前遍历，直到找到最后一个单词的长度，最坏情况下需要遍历整个字符串，时间复杂度也是 O(n)。 因此，总的时间复杂度为 O(n)。

空间复杂度分析：

  • 代码中没有使用任何额外的数据结构，只使用了常数级别的额外空间。 因此，空间复杂度为 O(1)。

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

LeetCode运行结果：

方法二：字符串操作函数

除了上述的方法外，还可以使用Java内置的字符串操作函数来解决这个问题。具体的思路是：

  1. 先去除字符串两端的空格，确保字符串没有多余的空格。

  2. 使用Java的 split() 函数将字符串按照空格分割成多个单词，并保存在一个字符串数组中。

  3. 如果字符串数组不为空，则最后一个单词即为数组中的最后一个元素。

  4. 返回最后一个单词的长度。

class Solution {
public int lengthOfLastWord(String s) {// 去除字符串两端的空格s = s.trim();// 分割字符串并获取最后一个单词的长度String[] words = s.split(" ");if (words.length == 0) {return 0;}return words[words.length - 1].length();
}}

复杂度分析：

时间复杂度分析：

  • 字符串去除两端空格的操作的时间复杂度是 O(n)，其中 n 是字符串的长度。
  • split() 函数的时间复杂度取决于字符串的长度和分隔符的数量。在这里，分隔符是空格，因此最坏情况下需要遍历整个字符串一次，并且需要额外的时间将结果存储到数组中。所以，split() 函数的时间复杂度为 O(n)。
  • 获取最后一个单词的长度只需要常数时间。 因此，总的时间复杂度为 O(n)。

空间复杂度分析：

  • 代码中使用了一个字符串数组来存储分割后的单词，数组的大小取决于字符串中单词的数量。在最坏情况下，单词的数量与字符串的长度相当，因此空间复杂度为 O(n)。
  • 另外，还需要额外的空间存储去除两端空格后的字符串。 综上所述，总的空间复杂度为 O(n)。

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

LeetCode运行结果：

方法三：正则表达式

还可以使用正则表达式来解决这个问题。具体的思路是：

  1. 使用正则表达式 \\s+ 将字符串以空格作为分隔符拆分成多个单词。
  2. 如果拆分后的单词数组为空，说明字符串中没有单词，直接返回 0。
  3. 如果不为空，则取最后一个单词并返回其长度。
class Solution {
public int lengthOfLastWord(String s) {String[] words = s.split("\\s+");if (words.length == 0) {return 0;}String lastWord = words[words.length - 1];return lastWord.length();
}
}

复杂度分析：

  • 使用正则表达式的做法，时间复杂度为 O(n)，其中 n 是字符串的长度。需要将整个字符串拆分成多个单词，同时只需要遍历一次。
  • 空间复杂度为 O(k)，其中 k 是字符串中单词的数量。需要用数组存储拆分后的单词，因此空间复杂度取决于单词的数量。

LeetCode运行结果：

第二题

题目来源

59. 螺旋矩阵 II - 力扣（LeetCode）

题目内容

解决方法

方法一：模拟

这道题可以使用模拟的方法来生成螺旋矩阵。具体的步骤如下：

  1. 初始化一个空的 n x n 矩阵 matrix。

  2. 定义四个变量 top、bottom、left、right，分别表示当前螺旋轮廓的上边界、下边界、左边界和右边界。

  3. 初始化变量 num 为 1，表示当前要填入的数字。

  4. 进行循环，当 num 小于等于 n 的平方时，进行以下操作：

    • 从左到右遍历上边界，将 num 填入 matrix[top][i]，并将 num 自增 1。

    • 上边界下移一行。

    • 若上边界超出下边界，则结束循环。

    • 从上到下遍历右边界，将 num 填入 matrix[i][right]，并将 num 自增 1。

    • 右边界左移一列。

    • 若右边界超出左边界，则结束循环。

    • 从右到左遍历下边界，将 num 填入 matrix[bottom][i]，并将 num 自增 1。

    • 下边界上移一行。

    • 若下边界超出上边界，则结束循环。

    • 从下到上遍历左边界，将 num 填入 matrix[i][left]，并将 num 自增 1。

    • 左边界右移一列。

    • 若左边界超出右边界，则结束循环。

  5. 返回生成的螺旋矩阵 matrix。

class Solution {
public int[][] generateMatrix(int n) {int[][] matrix = new int[n][n];int top = 0, bottom = n - 1, left = 0, right = n - 1;int num = 1;while (num <= n * n) {for (int i = left; i <= right; i++) {matrix[top][i] = num++;}top++;if (top > bottom) {break;}for (int i = top; i <= bottom; i++) {matrix[i][right] = num++;}right--;if (right < left) {break;}for (int i = right; i >= left; i--) {matrix[bottom][i] = num++;}bottom--;if (bottom < top) {break;}for (int i = bottom; i >= top; i--) {matrix[i][left] = num++;}left++;if (left > right) {break;}}return matrix;
}}

复杂度分析：

  • 对于给定的整数 n，我们需要填充 n^2 个元素到螺旋矩阵中。因此，时间复杂度为 O(n^2)。
  • 在空间复杂度方面，我们使用了一个 n x n 的矩阵来保存结果。因此，空间复杂度也为 O(n^2)。

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

LeetCode运行结果：

方法二：递归

除了模拟法之外，还可以使用递归的方法来生成螺旋矩阵。

具体的思路是，每次递归生成最外层的螺旋轮廓，并将其剥离，然后对剩余的内部矩阵进行递归生成。直到矩阵为空或只剩下一个元素时结束递归。

class Solution {
public int[][] generateMatrix(int n) {int[][] matrix = new int[n][n];generateMatrix(matrix, 0, n - 1, 1);return matrix;
}private void generateMatrix(int[][] matrix, int start, int end, int num) {if (start > end) {return;}// 生成最外层的螺旋轮廓for (int i = start; i <= end; i++) {matrix[start][i] = num++;}for (int i = start + 1; i <= end; i++) {matrix[i][end] = num++;}for (int i = end - 1; i >= start; i--) {matrix[end][i] = num++;}for (int i = end - 1; i > start; i--) {matrix[i][start] = num++;}// 递归生成内部矩阵generateMatrix(matrix, start + 1, end - 1, num);
}}

复杂度分析：

  • 由于递归方法每次递归都会生成最外层的螺旋轮廓，并将其剥离，因此矩阵中的每个元素都会被遍历一次，时间复杂度为 O(n^2)。
  • 在空间复杂度方面，由于递归方法并不需要额外的空间来存储状态，因此仅需要使用一个 n x n 的矩阵来保存结果。因此，空间复杂度也为 O(n^2)。

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

LeetCode运行结果：

方法三：迭代

除了模拟和递归之外，还可以使用迭代的方法来生成螺旋矩阵。该方法使用四个变量表示当前要填入的数字、当前螺旋轮廓的上、下、左、右边界，并按照规律依次填入数字。

class Solution {
public int[][] generateMatrix(int n) {int[][] matrix = new int[n][n];int num = 1;int top = 0, bottom = n - 1, left = 0, right = n - 1;while (num <= n * n) {// 从左到右填入上边界for (int i = left; i <= right; i++) {matrix[top][i] = num++;}top++;// 从上到下填入右边界for (int i = top; i <= bottom; i++) {matrix[i][right] = num++;}right--;// 从右到左填入下边界for (int i = right; i >= left; i--) {matrix[bottom][i] = num++;}bottom--;// 从下到上填入左边界for (int i = bottom; i >= top; i--) {matrix[i][left] = num++;}left++;}return matrix;
}}

复杂度分析：

对于迭代方法来说，时间复杂度和空间复杂度仍然为O(n^2)。

  • 由于需要遍历每个元素，并填入正确的数字，时间复杂度为O(n^2)。
  • 在空间复杂度方面，仅需要使用一个 n x n 大小的矩阵来保存结果，因此空间复杂度也为O(n^2)。

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

LeetCode运行结果：

方法四：数学规律

除了模拟、递归和迭代之外，还可以使用数学规律的方法来生成螺旋矩阵。

在这种方法中，可以将生成螺旋矩阵的过程看作是按层进行填充的过程。首先确定每一层的起始位置和结束位置，并根据数学规律逐步填入数字。

class Solution {
public int[][] generateMatrix(int n) {int[][] matrix = new int[n][n];int num = 1;int startRow = 0, endRow = n - 1, startCol = 0, endCol = n - 1;while (startRow <= endRow && startCol <= endCol) {// 填充当前层的上边界for (int i = startCol; i <= endCol; i++) {matrix[startRow][i] = num++;}startRow++;// 填充当前层的右边界for (int i = startRow; i <= endRow; i++) {matrix[i][endCol] = num++;}endCol--;if (startRow <= endRow) {// 填充当前层的下边界for (int i = endCol; i >= startCol; i--) {matrix[endRow][i] = num++;}endRow--;}if (startCol <= endCol) {// 填充当前层的左边界for (int i = endRow; i >= startRow; i--) {matrix[i][startCol] = num++;}startCol++;}}return matrix;
}}

复杂度分析：

对于数学规律方法来说，时间复杂度和空间复杂度仍然为O(n^2)。

  • 由于需要遍历每个元素，并填入正确的数字，时间复杂度为O(n^2)。
  • 在空间复杂度方面，仅需要使用一个 n x n 大小的矩阵来保存结果，因此空间复杂度也为O(n^2)。

综上所述，数学规律方法的时间复杂度和空间复杂度均为O(n^2)。

LeetCode运行结果：

第三题

题目来源

60. 排列序列 - 力扣（LeetCode）

题目内容

解决方法

方法一：回溯算法

题目要求按照大小顺序列出所有排列情况，并找出第k个排列。

我们可以使用回溯算法来解决这个问题。具体步骤如下：

  1. 创建一个布尔数组used，用于标记数字是否已经被使用过。
  2. 创建一个字符串permutation，用于保存当前的排列结果。
  3. 创建一个整数count，用于计数当前的排列序号。
  4. 定义递归函数backtrack，参数为当前处理的数字num和目标排列的长度n。
    • 如果num等于n，表示已经生成了一个完整的排列，此时count加一。
      • 如果count等于k，说明已经找到了第k个排列，将permutation作为结果返回。
    • 遍历数字1到n：
      • 如果当前数字没有被使用过（即used[i]为false），则将其加入到permutation中，并将used[i]标记为true，然后递归调用backtrack(num + 1, n)。
        • 如果得到了结果，直接返回结果。
      • 回溯：将当前数字从permutation中移除，并将used[i]标记为false。
  5. 返回空字符串作为结果。
class Solution {public String getPermutation(int n, int k) {boolean[] used = new boolean[n + 1];StringBuilder permutation = new StringBuilder();int[] count = new int[1];backtrack(0, n, k, used, permutation, count);return permutation.toString();}private boolean backtrack(int num, int n, int k, boolean[] used, StringBuilder permutation, int[] count) {if (num == n) {count[0]++;if (count[0] == k) {return true;}return false;}for (int i = 1; i <= n; i++) {if (!used[i]) {permutation.append(i);used[i] = true;if (backtrack(num + 1, n, k, used, permutation, count)) {return true;}permutation.deleteCharAt(permutation.length() - 1);used[i] = false;}}return false;}
}

复杂度分析：

设n为给定数字的大小。

  • 时间复杂度分析：回溯过程中，我们需要找到第k个排列，因此最坏情况下需要生成所有的n!个排列。每个排列的生成需要O(n)的时间，因此总的时间复杂度为O(n * n!)。
  • 空间复杂度分析：回溯过程中，我们使用了一个布尔数组used、一个字符串permutation和一个整数count来保存状态和结果。其中，布尔数组used的空间复杂度为O(n)，字符串permutation的空间复杂度为O(n)，整数count的空间复杂度为O(1)。因此总的空间复杂度为O(n)。

综上所述，该算法的时间复杂度为O(n * n!)，空间复杂度为O(n)。由于n的范围限制为1 <= n <= 9，因此算法的运行时间是可以接受的。

LeetCode运行结果：

方法二：迭代

除了回溯算法，我们还可以使用迭代的思路来解决这个问题。

该方法首先通过迭代生成了数字列表和阶乘数组，然后进行迭代过程来计算每一位上的数字，并将其加入到结果中，直到得到第k个排列。

class Solution {public String getPermutation(int n, int k) {// 初始化数字列表和阶乘数组List<Integer> nums = new ArrayList<>();int[] factorials = new int[n+1];factorials[0] = 1;for (int i = 1; i <= n; i++) {nums.add(i);factorials[i] = factorials[i-1] * i;}// k需要减一，方便对索引的计算k--;StringBuilder sb = new StringBuilder();for (int i = n; i >= 1; i--) {int index = k / factorials[i-1]; // 当前位上的数字在数字列表中的索引sb.append(nums.remove(index)); // 将当前位上的数字加入到结果中k %= factorials[i-1]; // 更新k}return sb.toString();}
}

复杂度分析：

时间复杂度分析：

  • 计算阶乘数组：需要对数字从 1 到 n 进行遍历，所以时间复杂度为 O(n)。
  • 迭代过程：需要进行 n 次迭代，每次迭代的时间复杂度为 O(n)，因为要遍历剩余数字列表来确定当前位上的数字。所以总的时间复杂度为 O(n^2)。

空间复杂度分析：

  • 存储阶乘数组：阶乘数组长度为 n+1，所以空间复杂度为 O(n)。

综上所述，该算法的时间复杂度为 O(n^2)，空间复杂度为 O(n)。

LeetCode运行结果：

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


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

相关文章

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