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

相关文章

Java设计模式---迭代器模式(Iterator)解读

Java设计模式---迭代器模式(Iterator)解读

《Java设计模式---迭代器模式(Iterator)解读》：本文主要介绍Java设计模式---迭代器模式(Iterator),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录1、迭代器（Iterator）1.1、结构1.2、常用方法1.3、本质1、解耦集合与遍历逻辑2、统一
阅读更多...
Java内存分配与JVM参数详解(推荐)

Java内存分配与JVM参数详解(推荐)

《Java内存分配与JVM参数详解(推荐)》本文详解JVM内存结构与参数调整,涵盖堆分代、元空间、GC选择及优化策略,帮助开发者提升性能、避免内存泄漏,本文给大家介绍Java内存分配与JVM参数详解,... 目录引言JVM内存结构JVM参数概述堆内存分配年轻代与老年代调整堆内存大小调整年轻代与老年代比例元空
阅读更多...
深度解析Java DTO(最新推荐)

深度解析Java DTO(最新推荐)

《深度解析JavaDTO(最新推荐)》DTO（DataTransferObject）是一种用于在不同层（如Controller层、Service层）之间传输数据的对象设计模式,其核心目的是封装数据,... 目录一、什么是DTO？DTO的核心特点：二、为什么需要DTO？（对比Entity）三、实际应用场景解析
阅读更多...
Java 线程安全与 volatile与单例模式问题及解决方案

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因（调度随机、变量修改、非原子操作、内存可见性、指令重排序）及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操
阅读更多...
从原理到实战深入理解Java 断言assert

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言（assert）：从原理到实战引言：为什么需要断言？一、断言基础1.1 语
阅读更多...
深度解析Java项目中包和包之间的联系

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次，点赞13次，收藏8次。本文详细介绍了Java分层架构中的几个关键包：DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
SpringBoot整合liteflow的详细过程

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》：本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么？ 能做什么？总之一句话：能帮你规范写代码逻辑 ，编排并解耦业务逻辑，代码
阅读更多...
JavaSE正则表达式用法总结大全

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,：本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta
阅读更多...
Spring Security中用户名和密码的验证完整流程

Spring Security中用户名和密码的验证完整流程

《SpringSecurity中用户名和密码的验证完整流程》本文给大家介绍SpringSecurity中用户名和密码的验证完整流程,本文结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定... 首先创建了一个UsernamePasswordAuthenticationTChina编程oken对象，这是S
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2