怒刷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。

相关文章

SpringBoot 获取请求参数的常用注解及用法

SpringBoot 获取请求参数的常用注解及用法

《SpringBoot获取请求参数的常用注解及用法》SpringBoot通过@RequestParam、@PathVariable等注解支持从HTTP请求中获取参数,涵盖查询、路径、请求体、头、C... 目录SpringBoot 提供了多种注解来方便地从 HTTP 请求中获取参数以下是主要的注解及其用法：1
阅读更多...
HTTP 与 SpringBoot 参数提交与接收协议方式

HTTP 与 SpringBoot 参数提交与接收协议方式

《HTTP与SpringBoot参数提交与接收协议方式》HTTP参数提交方式包括URL查询、表单、JSON/XML、路径变量、头部、Cookie、GraphQL、WebSocket和SSE,依据... 目录HTTP 协议支持多种参数提交方式，主要取决于请求方法(Method)和内容类型(Content-Ty
阅读更多...
深度解析Java @Serial 注解及常见错误案例

深度解析Java @Serial 注解及常见错误案例

《深度解析Java@Serial注解及常见错误案例》Java14引入@Serial注解,用于编译时校验序列化成员,替代传统方式解决运行时错误,适用于Serializable类的方法/字段,需注意签... 目录Java @Serial 注解深度解析1. 注解本质2. 核心作用(1) 主要用途(2) 适用位置3
阅读更多...
深入浅出Spring中的@Autowired自动注入的工作原理及实践应用

深入浅出Spring中的@Autowired自动注入的工作原理及实践应用

《深入浅出Spring中的@Autowired自动注入的工作原理及实践应用》在Spring框架的学习旅程中,@Autowired无疑是一个高频出现却又让初学者头疼的注解,它看似简单,却蕴含着Sprin... 目录深入浅出Spring中的@Autowired：自动注入的奥秘什么是依赖注入？@Autowired
阅读更多...
Spring 依赖注入与循环依赖总结

Spring 依赖注入与循环依赖总结

《Spring依赖注入与循环依赖总结》这篇文章给大家介绍Spring依赖注入与循环依赖总结篇,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. Spring 三级缓存解决循环依赖1. 创建UserService原始对象2. 将原始对象包装成工
阅读更多...
Java中如何正确的停掉线程

Java中如何正确的停掉线程

《Java中如何正确的停掉线程》Java通过interrupt()通知线程停止而非强制,确保线程自主处理中断,避免数据损坏,线程池的shutdown()等待任务完成,shutdownNow()强制中断... 目录为什么不强制停止为什么 Java 不提供强制停止线程的能力呢？如何用interrupt停止线程s
阅读更多...
SpringBoot请求参数传递与接收示例详解

SpringBoot请求参数传递与接收示例详解

《SpringBoot请求参数传递与接收示例详解》本文给大家介绍SpringBoot请求参数传递与接收示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录I. 基础参数传递i.查询参数（Query Parameters）ii.路径参数（Path Va
阅读更多...
SpringBoot路径映射配置的实现步骤

SpringBoot路径映射配置的实现步骤

《SpringBoot路径映射配置的实现步骤》本文介绍了如何在SpringBoot项目中配置路径映射,使得除static目录外的资源可被访问,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一... 目录SpringBoot路径映射补：springboot 配置虚拟路径映射 @RequestMapp
阅读更多...
Java MCP 的鉴权深度解析

Java MCP 的鉴权深度解析

《JavaMCP的鉴权深度解析》文章介绍JavaMCP鉴权的实现方式,指出客户端可通过queryString、header或env传递鉴权信息,服务器端支持工具单独鉴权、过滤器集中鉴权及启动时鉴权... 目录一、MCP Client 侧（负责传递，比较简单）（1）常见的 mcpServers json 配置
阅读更多...
GSON框架下将百度天气JSON数据转JavaBean

GSON框架下将百度天气JSON数据转JavaBean

《GSON框架下将百度天气JSON数据转JavaBean》这篇文章主要为大家详细介绍了如何在GSON框架下实现将百度天气JSON数据转JavaBean,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录前言一、百度天气jsON1、请求参数2、返回参数3、属性映射二、GSON属性映射实战1、类对象映
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2