• 怒刷LeetCode的第24天（Java版）

    目录

    第一题

    题目来源

    题目内容

    解决方法

    方法一：反向遍历

    方法二：字符串操作函数

    方法三：正则表达式

    第二题

    题目来源

    题目内容

    解决方法

    方法一：模拟

    方法二：递归

    方法三：迭代

    方法四：数学规律

    第三题

    题目来源

    题目内容

    解决方法

    方法一：回溯算法

    方法二：迭代

    第一题

    题目来源

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

    题目内容

    解决方法

    方法一：反向遍历

    具体的思路是：

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

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

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

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

    1. class Solution {
    2. public int lengthOfLastWord(String s) {
    3.     // 去除字符串两端的空格
    4.     s = s.trim();
    5.  
    6.     // 遍历字符串，找到最后一个单词的长度
    7.     int length = 0;
    8.     for (int i = s.length() - 1; i >= 0; i--) {
    9.         if (s.charAt(i) == ' ') {
    10.             break;
    11.         }
    12.         length++;
    13.     }
    14.  
    15.     return length;
    16. }
    17. }

    复杂度分析：

    时间复杂度分析：

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

    空间复杂度分析：

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

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

    LeetCode运行结果：

    方法二：字符串操作函数

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

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

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

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

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

    1. class Solution {
    2. public int lengthOfLastWord(String s) {
    3.     // 去除字符串两端的空格
    4.     s = s.trim();
    5.  
    6.     // 分割字符串并获取最后一个单词的长度
    7.     String[] words = s.split(" ");
    8.     if (words.length == 0) {
    9.         return 0;
    10.     }
    11.     return words[words.length - 1].length();
    12. }
    13.  
    14. }

    复杂度分析：

    时间复杂度分析：

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

    空间复杂度分析：

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

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

    LeetCode运行结果：

    方法三：正则表达式

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

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

    复杂度分析：

    • 使用正则表达式的做法，时间复杂度为 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。

    1. class Solution {
    2. public int[][] generateMatrix(int n) {
    3.     int[][] matrix = new int[n][n];
    4.     int top = 0, bottom = n - 1, left = 0, right = n - 1;
    5.     int num = 1;
    6.  
    7.     while (num <= n * n) {
    8.         for (int i = left; i <= right; i++) {
    9.             matrix[top][i] = num++;
    10.         }
    11.         top++;
    12.         if (top > bottom) {
    13.             break;
    14.         }
    15.  
    16.         for (int i = top; i <= bottom; i++) {
    17.             matrix[i][right] = num++;
    18.         }
    19.         right--;
    20.         if (right < left) {
    21.             break;
    22.         }
    23.  
    24.         for (int i = right; i >= left; i--) {
    25.             matrix[bottom][i] = num++;
    26.         }
    27.         bottom--;
    28.         if (bottom < top) {
    29.             break;
    30.         }
    31.  
    32.         for (int i = bottom; i >= top; i--) {
    33.             matrix[i][left] = num++;
    34.         }
    35.         left++;
    36.         if (left > right) {
    37.             break;
    38.         }
    39.     }
    40.  
    41.     return matrix;
    42. }
    43.  
    44. }

    复杂度分析：

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

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

    LeetCode运行结果：

    方法二：递归

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

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

    1. class Solution {
    2. public int[][] generateMatrix(int n) {
    3.     int[][] matrix = new int[n][n];
    4.     generateMatrix(matrix, 0, n - 1, 1);
    5.     return matrix;
    6. }
    7.  
    8. private void generateMatrix(int[][] matrix, int start, int end, int num) {
    9.     if (start > end) {
    10.         return;
    11.     }
    12.  
    13.     // 生成最外层的螺旋轮廓
    14.     for (int i = start; i <= end; i++) {
    15.         matrix[start][i] = num++;
    16.     }
    17.     for (int i = start + 1; i <= end; i++) {
    18.         matrix[i][end] = num++;
    19.     }
    20.     for (int i = end - 1; i >= start; i--) {
    21.         matrix[end][i] = num++;
    22.     }
    23.     for (int i = end - 1; i > start; i--) {
    24.         matrix[i][start] = num++;
    25.     }
    26.  
    27.     // 递归生成内部矩阵
    28.     generateMatrix(matrix, start + 1, end - 1, num);
    29. }
    30.  
    31. }

    复杂度分析：

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

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

    LeetCode运行结果：

    方法三：迭代

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

    1. class Solution {
    2. public int[][] generateMatrix(int n) {
    3.     int[][] matrix = new int[n][n];
    4.     int num = 1;
    5.     int top = 0, bottom = n - 1, left = 0, right = n - 1;
    6.  
    7.     while (num <= n * n) {
    8.         // 从左到右填入上边界
    9.         for (int i = left; i <= right; i++) {
    10.             matrix[top][i] = num++;
    11.         }
    12.         top++;
    13.  
    14.         // 从上到下填入右边界
    15.         for (int i = top; i <= bottom; i++) {
    16.             matrix[i][right] = num++;
    17.         }
    18.         right--;
    19.  
    20.         // 从右到左填入下边界
    21.         for (int i = right; i >= left; i--) {
    22.             matrix[bottom][i] = num++;
    23.         }
    24.         bottom--;
    25.  
    26.         // 从下到上填入左边界
    27.         for (int i = bottom; i >= top; i--) {
    28.             matrix[i][left] = num++;
    29.         }
    30.         left++;
    31.     }
    32.  
    33.     return matrix;
    34. }
    35.  
    36.  
    37. }

    复杂度分析：

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

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

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

    LeetCode运行结果：

    方法四：数学规律

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

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

    1. class Solution {
    2. public int[][] generateMatrix(int n) {
    3.     int[][] matrix = new int[n][n];
    4.     int num = 1;
    5.     int startRow = 0, endRow = n - 1, startCol = 0, endCol = n - 1;
    6.  
    7.     while (startRow <= endRow && startCol <= endCol) {
    8.         // 填充当前层的上边界
    9.         for (int i = startCol; i <= endCol; i++) {
    10.             matrix[startRow][i] = num++;
    11.         }
    12.         startRow++;
    13.  
    14.         // 填充当前层的右边界
    15.         for (int i = startRow; i <= endRow; i++) {
    16.             matrix[i][endCol] = num++;
    17.         }
    18.         endCol--;
    19.  
    20.         if (startRow <= endRow) {
    21.             // 填充当前层的下边界
    22.             for (int i = endCol; i >= startCol; i--) {
    23.                 matrix[endRow][i] = num++;
    24.             }
    25.             endRow--;
    26.         }
    27.  
    28.         if (startCol <= endCol) {
    29.             // 填充当前层的左边界
    30.             for (int i = endRow; i >= startRow; i--) {
    31.                 matrix[i][startCol] = num++;
    32.             }
    33.             startCol++;
    34.         }
    35.     }
    36.  
    37.     return matrix;
    38. }
    39.  
    40. }

    复杂度分析：

    对于数学规律方法来说，时间复杂度和空间复杂度仍然为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. 返回空字符串作为结果。
    1. class Solution {
    2.     public String getPermutation(int n, int k) {
    3.         boolean[] used = new boolean[n + 1];
    4.         StringBuilder permutation = new StringBuilder();
    5.         int[] count = new int[1];
    6.  
    7.         backtrack(0, n, k, used, permutation, count);
    8.  
    9.         return permutation.toString();
    10.     }
    11.  
    12.     private boolean backtrack(int num, int n, int k, boolean[] used, StringBuilder permutation, int[] count) {
    13.         if (num == n) {
    14.             count[0]++;
    15.             if (count[0] == k) {
    16.                 return true;
    17.             }
    18.             return false;
    19.         }
    20.  
    21.         for (int i = 1; i <= n; i++) {
    22.             if (!used[i]) {
    23.                 permutation.append(i);
    24.                 used[i] = true;
    25.  
    26.                 if (backtrack(num + 1, n, k, used, permutation, count)) {
    27.                     return true;
    28.                 }
    29.  
    30.                 permutation.deleteCharAt(permutation.length() - 1);
    31.                 used[i] = false;
    32.             }
    33.         }
    34.  
    35.         return false;
    36.     }
    37. }

    复杂度分析：

    设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个排列。

    1. class Solution {
    2.     public String getPermutation(int n, int k) {
    3.         // 初始化数字列表和阶乘数组
    4.         List nums = new ArrayList<>();
    5.         int[] factorials = new int[n+1];
    6.         factorials[0] = 1;
    7.         for (int i = 1; i <= n; i++) {
    8.             nums.add(i);
    9.             factorials[i] = factorials[i-1] * i;
    10.         }
    11.  
    12.         // k需要减一，方便对索引的计算
    13.         k--;
    14.  
    15.         StringBuilder sb = new StringBuilder();
    16.         for (int i = n; i >= 1; i--) {
    17.             int index = k / factorials[i-1]; // 当前位上的数字在数字列表中的索引
    18.             sb.append(nums.remove(index)); // 将当前位上的数字加入到结果中
    19.             k %= factorials[i-1]; // 更新k
    20.         }
    21.  
    22.         return sb.toString();
    23.     }
    24. }

    复杂度分析：

    时间复杂度分析：

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

    空间复杂度分析：

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

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

    LeetCode运行结果：

  • 相关阅读:
    Java-数组和方法(day6-7)
    什么是多维数组？怎样定义多维数组？
    全都会！预测蛋白质标注！创建讲义！解释数学公式！最懂科学的智能NLP模型Galactica尝鲜 ⛵
    〖全域运营实战白宝书 - 运营角色认知篇③〗- 运营的底层逻辑是什么？
    软件Bug和缺陷的区别是什么？
    Python-中北大学人工智能OpenCV人脸识别（根据图片训练数据，根据训练好的数据识别人脸）
    AWS API gateway api CORS错误处理方法
    虚拟化+docker基本概念以及安装部署
    xxl-job学习
    Flask-REXTx 学习笔记——2.字段掩码（Fields masks）
  • 原文地址：https://blog.csdn.net/m0_74293254/article/details/133617450