怒刷LeetCode的第24天（Java版）

2023-10-06 22:52
文章标签 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/154426。

相关文章

Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
Java中String字符串使用避坑指南

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下：1. 字符串的不可变性：每次修改都创建新对象2. 使用 == 比较字符串，陷阱满
阅读更多...
Java判断多个时间段是否重合的方法小结

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D
阅读更多...
IDEA编译报错“java: 常量字符串过长”的原因及解决方法

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①：StringBui
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
Java中ArrayList和LinkedList有什么区别举例详解

Java中ArrayList和LinkedList有什么区别举例详解

《Java中ArrayList和LinkedList有什么区别举例详解》：本文主要介绍Java中ArrayList和LinkedList区别的相关资料,包括数据结构特性、核心操作性能、内存与GC影... 目录一、底层数据结构二、核心操作性能对比三、内存与 GC 影响四、扩容机制五、线程安全与并发方案六、工程
阅读更多...
JavaScript中的reduce方法执行过程、使用场景及进阶用法

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》：本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
Java调用DeepSeek API的最佳实践及详细代码示例

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》：本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.
阅读更多...
Spring AI集成DeepSeek的详细步骤

Spring AI集成DeepSeek的详细步骤

《SpringAI集成DeepSeek的详细步骤》DeepSeek作为一款卓越的国产AI模型,越来越多的公司考虑在自己的应用中集成,对于Java应用来说,我们可以借助SpringAI集成DeepSe... 目录DeepSeek 介绍Spring AI 是什么？1、环境准备2、构建项目2.1、pom依赖2.2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2