LeeCode三百题-5

发表于 2021-07-13 更新于 2026-06-20 分类于 LeeCode三百题

[TOC]

代码工程获取

git clone --depth=1 https://gitee.com/SevDaisy/LeeCode300.git

#41 缺失的第一个正数

我自己一年前写过的题。笑死。根本不记得解法。最后看了自己的历史提交。借鉴思想，尝试复现代码。

分析：
题目，难就难在时间复杂度要求为O(n)，且空间复杂度为O(1)
如果没有时空要求。怎么做？
- 直接过滤并排序为一个只有正整数的数组
- 再遍历数组
- 找到那个不符合 nums[i] = i+1 ，返回 i+1 就好了
- 如果一路都找不到，那说明数组形如 [1,2,3..,iMax]，那缺失的第一个正数应该是 iMax+1
所以，难点其实是，过滤和排序要在 O(n) 内完成
- 过滤显然没问题。for x in array: x>0 Only 就好了
- 排序，要 O(n) 似乎是一个不可能的任务
转换思路。
这其实是一个很特殊的排序问题。
- 为什么？
- 因为我们是知道每个数字最后应该被放在哪个位置上的。
所以，我们不需要每个数都比来比去。
只要拿到一个数 —— 把他放到他应该在的位置。
如果他就在那个位置上 —— 那么，i++，直接去看下一个位置。
- 直到整个数组遍历完一遍。
如果他不在自己的位置上 —— 那么，保存原本占了他位置的数，把这个数放到它该去的地方。
- 重复，直到把整个数组遍历完一遍。
概要设计如上，还要注意的细节问题如下：
=> 最后得到的数组，包含哪些元素？
- 如果数组中没有缺少正整数，按题意，这个数组应该是形如 [1,2,3,...,iMax]
- 也就是说，数组中的元素，合法的范围不是 x > 0 而是 x in [1,iMax]
=> 关于数字的比较和交换。
- 应该是, if nums[nums[i]-1] != nums[i] 则交换
- 而不是, if nums[i] != i+1 则
  - buffer = nums[nums[i]-1];
  - nums[nums[i]-1] = nums[i];
- 也就说, 不能拿着这个数，去保存到另外的 buffer。这样的代码远不如直接交换来得简明健壮好用好看。
- 具体逻辑我也说不清楚。我只知道，一开始想用 buffer 写来着，我没写出来。
- 品，细品。悟，好好悟。想明白了可以教教我🤪
补充说明下面这个简化是不成立的：
- nums[nums[i]-1] != nums[i] 转化为 nums[i]-1 != i 转化为 nums[i] != i+1
- 因为，nums[nums[i]-1] != nums[i] 是 nums[i]-1 != i 的 充分但不必要条件

这个算法只能跑到2ms —— 2021年7月13日
可以看到 1ms 的范程，都是不满足题目的空间要求的 —— 开了一个 O(n) 的辅助空间，用空间换了时间
可以看到 0ms 的范程，更加是投机取巧，只对 nums.length <= 300 的情况做真实运算。开了一个 size=300 的辅助空间
上面这两种速度上的优化都没什么意思。我就不做了。

package Order300;

public class T41_first_missing_positive {

  public static void main(String[] args) {
    System.out.println(new Solution().firstMissingPositive(new int[] { 1, 1 })); // -> 2
    System.out.println(
      new Solution().firstMissingPositive(new int[] { 1, 2, 0 })
    ); // -> 3
    System.out.println(
      new Solution().firstMissingPositive(new int[] { 3, 4, -1, 1 })
    ); // -> 2
    System.out.println(
      new Solution().firstMissingPositive(new int[] { 7, 8, 9, 11, 12 })
    ); // -> 1
    System.out.println(new Solution().firstMissingPositive(new int[] { 1 })); // -> 2
  }

  /* 第一次尝试 借鉴自己以前的代码，只能跑到 时间 2ms => 54.47% 空间 94.9MB => 7.00% */
  static class Solution {

    /**
     * 我一年前写过的题。笑死。根本不记得解法。最后看了自己的历史提交。借鉴思想，尝试复现代码。
     * 分析：
     * 题目，难就难在时间复杂度要求为O(n)，且空间复杂度为O(1)
     *
     * 如果没有时空要求。怎么做？
     * 直接过滤并排序为一个只有正整数的数组，再遍历数组，找到那个不符合 nums[i] = i+1 ，返回 i+1 就好了
     *
     * 所以，难点其实是，过滤和排序要在 O(n) 内完成
     *
     * 过滤显然没问题。for x in array: x>0 Only 就好了
     * 排序，要 O(n) 似乎是一个不可能的任务
     *
     * 转换思路。这其实是一个很特殊的排序问题。为什么，因为我们是知道每个数字最后应该被放在哪个位置上的。
     * 所以，我们不需要每个数都比来比去。只要拿到一个数，然后把他放到他应该在的位置。
     * 如果他就在那个位置上，那么，i++，直接去看下一个位置。直到整个数组遍历完一遍。
     * 如果他不在自己的位置上，那么，保存原本占了他位置的数，把这个数放到它该去的地方。重复，直到把整个数组遍历完一遍。
     *
     * 概要设计如上，还要注意的细节问题如下：
     *
     * 最后得到的数组，包含哪些元素？
     * 如果数组中没有缺少正整数，按题意，这个数组应该是这样的 [1,2,3,...,iMax]
     * 也就是说，数组中的元素，合法的范围不是 x > 0 而是 x in [1,iMax]
     *
     * 关于数字的比较和交换。
     * 应该是, if nums[nums[i]-1] != nums[i] 则 交换. 
     * 而不是, if nums[i] != i+1 则 buffer = nums[nums[i]-1]; nums[nums[i]-1] = nums[i];
     * 也就说, 不能拿着这个数，去保存到另外的 buffer。这样的代码远不如直接交换来得简明健壮好用好看。
     * 具体逻辑我也说不清楚。我只知道，一开始想用 buffer 写来着，我没写出来。
     * 品，细品。悟，好好悟。想明白了可以教教我🤪
     *
     * 
     * 补充说明 下面这个简化是不成立的："nums[nums[i]-1] != nums[i] 转化为 nums[i]-1 != i 转化为 nums[i] != i+1"
     * 因为，(nums[nums[i]-1] != nums[i]) 是 (nums[i]-1 != i) 的 充分但不必要条件
     */
    public int firstMissingPositive(int[] nums) {
      // if (nums == null || nums.length == 0) return 0;
      int iMax = nums.length;
      for (int i = 0; i < iMax; i++) {
        while (nums[i] > 0 && nums[i] <= iMax && nums[nums[i] - 1] != nums[i]) {
          int temp = nums[nums[i] - 1];
          nums[nums[i] - 1] = nums[i];
          nums[i] = temp;
        }
      }
      for (int i = 0; i < iMax; i++) {
        if (nums[i] != i + 1) return i + 1;
      }
      return iMax + 1;
    }
  }
}

#42 接雨水

#43 字符串相乘

首次做到，第一次提交就直接AC并且时空双赢，欧耶

package Order300;

public class T43_multiply_strings {

  public static void main(String[] args) {
    String out;
    out = new Solution().multiply("12", "13");
    System.out.println(out);
    out = new Solution().multiply("99", "99");
    System.out.println(out);
  }

  /* 第一次尝试 时间 2ms => 99.30% 空间 38.1MB => 95.63% */
  static class Solution {

    /**
     * num1 和 num2 的长度小于110。
     * num1 和 num2 只包含数字 0-9。
     * num1 和 num2 均不以零开头，除非是数字 0 本身。
     */
    public String multiply(String num1, String num2) {
      int[] buffer = new int[220];
      int[] s1 = new int[110];
      int[] s2 = new int[110];

      /* 倒序储存 num1 和 num2 的各位数 */
      for (int i = num1.length() - 1, j = 0; i >= 0; i--, j++) {
        s1[j] = num1.charAt(i) - '0';
      }
      for (int i = num2.length() - 1, j = 0; i >= 0; i--, j++) {
        s2[j] = num2.charAt(i) - '0';
      }

      /* 逐位计算乘 并相加 */
      for (int i1 = 0; i1 < num1.length(); i1++) {
        for (int i2 = 0; i2 < num2.length(); i2++) {
          buffer[i1 + i2] += s1[i1] * s2[i2];
        }
      }

      /* 统一计算进位，并导出为结果字符串 out */
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < num1.length() + num2.length(); i++) {
        buffer[i + 1] += buffer[i] / 10;
        buffer[i] = buffer[i] % 10;
        sb.append((char) (buffer[i] + '0'));
      }
      String out = sb.reverse().toString();

      /* 消除 out 头部的 0 */
      for (int i = 0; i < out.length(); i++) {
        if (out.charAt(i) != '0') {
          return out.substring(i, out.length());
        }
      }
      /* 如果没在上面的for循环中返回值，那么显然，返回值应为 "0" */
      return "0";
    }
  }
}

#44 通配符匹配

#45 跳跃游戏 II

#46 全排列

package Order300;

import java.util.ArrayList;
import java.util.List;

public class T46_permutations {

  /* 第一次尝试 时间 1ms => 93.95% 空间 38.4MB => 90.16% */
  static class Solution {

    public List<List<Integer>> permute(int[] nums) {
      List<List<Integer>> out = new ArrayList<>();
      backtrack(nums, 0, out, new ArrayList<Integer>());
      return out;
    }

    private void backtrack(
      int[] nums,
      int step,
      List<List<Integer>> ans,
      List<Integer> path
    ) {
      if (step == nums.length) {
        ans.add(new ArrayList<>(path));
        return;
      }
      for (int i = 0; i < nums.length; i++) {
        if (path.contains(nums[i])) continue;
        path.add(nums[i]);
        backtrack(nums, step + 1, ans, path);
        path.remove(path.size() - 1);
      }
    }
  }
}

#47 全排列 II

package Order300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T47_permutations_ii {

  public static void main(String[] args) {
    List<List<Integer>> out;
    out = new Solution().permuteUnique(new int[] { 1, 2, 1 });
    for (List<Integer> line : out) {
      BaseNode.util.errPrintList(
        line,
        String.format("\nline_%d", out.indexOf(line))
      );
    }
  }

  /* 第一次尝试 频率表+回溯 时间 1ms => 99.82% 空间 38.6MB => 97.59% */
  static class Solution {

    public List<List<Integer>> permuteUnique(int[] nums) {
      /* 排序 */
      Arrays.sort(nums);
      /* 生成频率表 */
      List<int[]> freqs = new ArrayList<>();
      for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i - 1] == nums[i]) {
          freqs.get(freqs.size() - 1)[1] += 1;
        } else {
          freqs.add(new int[] { nums[i], 1 });
        }
      }

      int goal = nums.length;
      int step = 0;
      List<List<Integer>> ans = new ArrayList<>();
      List<Integer> path = new ArrayList<>();

      backtrace(freqs, goal, step, ans, path);

      return ans;
    }

    private void backtrace(
      List<int[]> freqs,
      int goal,
      int step,
      List<List<Integer>> ans,
      List<Integer> path
    ) {
      if (step == goal) {
        ans.add(new ArrayList<>(path));
        return;
      }
      for (int i = 0; i < freqs.size(); i++) {
        int[] pair = freqs.get(i);
        if (pair[1] > 0) {
          pair[1] -= 1;
          path.add(pair[0]);
          backtrace(freqs, goal, step + 1, ans, path);
          pair[1] += 1;
          path.remove(path.size() - 1);
        }
      }
    }
  }
}

#48 旋转图像

空白棋盘

旋转之前

旋转之后

因此，如果不要求原地旋转的话，只需要扫描一遍原数组，就可以用指定的 (i,j) => (size-i,size-j)映射出旋转后的数组
但是题目要求用原地旋转。所以，我决定用递归来解决这个问题。

/**
   * 第 -1 次尝试，希望递归解决，写出来是错的
   * 失败的样例如下
   * Input:
   *  1  2  3  4
   *  5  6  7  8
   *  9 10 11 12
   * 13 14 15 16
   *
   * MyOutput:
   *  5  1  7  3
   *  6  2  8  4
   * 13  9 15 11
   * 14 10 16 12
   */
class error_1 {

  public void rotate(int[][] matrix) {
    rotateAngle(matrix, 0, 0, matrix.length);
  }

  /**
     * @param map
     * @param _i 即 baseI
     * @param _j 即 baseJ
     * @param size
     */
  private void rotateEdge(int[][] map, int _i, int _j, int size) {
    int mid = size / 2;
    int[] buffer = new int[size];
    for (int i = 0; i < size; i++) {
      buffer[i] = map[_i + i][mid];
      map[_i + i][mid] = map[mid][_j + i];
    }
    for (int i = 0; i < size; i++) {
      map[mid][_j + i] = buffer[size - 1 - i];
    }
  }

  /**
     * @param map
     * @param _i 即 baseI
     * @param _j 即 baseJ
     * @param size
     */
  private void rotateAngle(int[][] map, int _i, int _j, int size) {
    if (size == 2) {
      int buffer = map[_i][_j];
      map[_i][_j] = map[_i + 1][_j];
      map[_i + 1][_j] = map[_i + 1][_j + 1];
      map[_i + 1][_j + 1] = map[_i][_j + 1];
      map[_i][_j + 1] = buffer;
    } else if (size == 3) {
      rotateEdge(map, _i, _j, size);
      int buffer = map[_i][_j];
      map[_i][_j] = map[_i + 2][_j];
      map[_i + 2][_j] = map[_i + 2][_j + 2];
      map[_i + 2][_j + 2] = map[_i][_j + 2];
      map[_i][_j + 2] = buffer;
    } else {
      int halfSize = size / 2;
      if (size % 2 != 0) {
        rotateEdge(map, _i, _j, size);
        rotateAngle(map, _i, _j, halfSize);
        rotateAngle(map, _i, _j + halfSize + 1, halfSize);
        rotateAngle(map, _i + halfSize + 1, _j, halfSize);
        rotateAngle(map, _i + halfSize + 1, _j + halfSize + 1, halfSize);
      } else {
        rotateAngle(map, _i, _j, halfSize);
        rotateAngle(map, _i, _j + halfSize, halfSize);
        rotateAngle(map, _i + halfSize, _j, halfSize);
        rotateAngle(map, _i + halfSize, _j + halfSize, halfSize);
      }
    }
  }
}

但是递归失败了。继续在递归代码的基础上补充，会很繁很丑，所以我决定改用迭代

package Order300;

/**
 * 题目要求 必须原地旋转
 * 题目保证 输入是一个正方形
 **/
public class T48_rotate_image {

  /* 第一次尝试 迭代 时间 0ms => 100% 空间 38.5MB => 62% */
  static class Solution {

    public void rotate(int[][] matrix) {
      int iMax = matrix.length - 1; // i in [0,iMax]
      /* Lv 即是从外圈往内圈数的第 Lv 层 */
      for (int Lv = 0; Lv < matrix.length / 2; Lv++) {
        int forSize = iMax - (Lv << 1);
        for (int i = 0; i < forSize; i++) {
          int buffer = matrix[Lv + i][Lv];
          matrix[Lv + i][Lv] = matrix[iMax - Lv][Lv + i];
          matrix[iMax - Lv][Lv + i] = matrix[iMax - i - Lv][iMax - Lv];
          matrix[iMax - i - Lv][iMax - Lv] = matrix[Lv][iMax - i - Lv];
          matrix[Lv][iMax - i - Lv] = buffer;
        }
      }
    }
  }
}

#49 字母异位词分组

package Order300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class T49_group_anagrams {

  /* 第一次尝试 sort as Key in Map<String,List> 时间 6ms => 98.50% 空间 41.8MB => 21.72% */
  static class Solution_1 {

    /**
     * 思路：
     * 用 Map<String,List<String>> 做映射
     * String 用 sort 后的字符串
     * 缺点：对每个字符串进行解构然后排序，然后还要用Map。在时间上和空间上都比较奢侈。不够精妙。
     *
     * 仰仗 Java STL 本身的性能，最后在时间上击败 98.50% 还是很喜人的。
     * 不过空间上落后于人 —— 21.72% 到确实有点出乎我医疗。我只是额外申请了一个 O(n) 的 Map 作为辅助空间。
     * 去看看别人的写法。
     */
    public List<List<String>> groupAnagrams(String[] strs) {
      Map<String, List<String>> table = new HashMap<String, List<String>>();
      for (String x : strs) {
        String sorted = sortString(x);
        if (table.containsKey(sorted)) {
          table.get(sorted).add(x);
        } else {
          table.put(
            sorted,
            new ArrayList<String>() {
              {
                add(x);
              }
            }
          );
        }
      }
      List<List<String>> ans = new ArrayList<>();
      for (List<String> group : table.values()) {
        ans.add(group);
      }
      return ans;
    }

    private String sortString(String x) {
      char[] arr = x.toCharArray();
      Arrays.sort(arr);
      StringBuilder builder = new StringBuilder();
      for (char c : arr) {
        builder.append(c);
      }
      return builder.toString();
    }
  }

  /* 第二次尝试 质数之积作为【hash】值 时间 4ms => 99.97% 空间 41.4MB => 55.70% */
  static class Solution {

    /**
     * 别人的解法
     * 自己实现了新的哈希函数
     * 已知待 Hash 者必由且仅由 26 个小写字母组成
     * 所以，只需要把 26 个小写字母映射为 26 个质数，则质数之乘积就是 Hash 值
     * 
     * 注意 是【乘积】而不是【算术和】
     * 因此，这个方法的缺点在于，不能处理过长的单词串
     */
    public List<List<String>> groupAnagrams(String[] strs) {
      Map<Long, List<String>> table = new HashMap<Long, List<String>>();
      for (String x : strs) {
        long key = hash(x);
        if (table.containsKey(key)) {
          table.get(key).add(x);
        } else {
          table.put(
            key,
            new ArrayList<String>() {
              {
                add(x);
              }
            }
          );
        }
      }
      List<List<String>> ans = new ArrayList<>();
      for (List<String> group : table.values()) {
        ans.add(group);
      }
      return ans;
    }

    private long hash(String s) {
      int[] map = new int[] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,};
      long out = 1;
      for (char c : s.toCharArray()) {
        out *= map[c - 'a'];
      }
      return out;
    }
  }
}

#50 Pow(x, n)

业务代码中杂有用于记录调用栈深度的 cnt 变量，会一定程度上影响算法的时空性能

package Order300;

/**
 * 看了题解提示，用【快速幂】法！
 * 可以有【递归】和【迭代】两种实现
 */
public class T50_powx_n {

  public static void main(String[] args) {
    Solution_Rec s = new Solution_Rec();
    // System.out.println(s.myPow(0, 0));
    // System.out.println(s.myPow(0, 9));
    // System.out.println(s.myPow(0, -9));
    // System.out.println();
    // System.out.println(s.myPow(1, 0));
    // System.out.println(s.myPow(1, 9));
    // System.out.println(s.myPow(1, -9));
    // System.out.println();
    // System.out.println(s.myPow(-1, 0));
    // System.out.println(s.myPow(-1, 9));
    // System.out.println(s.myPow(-1, -9));
    // System.out.println();
    // System.out.println(s.myPow(2, 3));
    // System.out.println(s.myPow(2, -3));
    // System.out.println();
    // System.out.println(s.myPow(0.00001, Integer.MAX_VALUE));
    System.out.println(s.myPow(2, 32));
    System.out.println(Solution_Rec.cnt);
    System.out.println(s.myPow(2, 64));
    System.out.println(Solution_Rec.cnt);
  }

  /* 第一次尝试 递归 时间 0ms => 100% 空间 36.6MB => 78.12%  */
  static class Solution_Rec {

    static long cnt = 0;

    public double myPow(double x, int n) {
      Solution_Rec.cnt = 0;
      /* 提前出口 */
      if (n == 0) return x == 0 ? 0 : 1;
      if (x == 1) return 1;
      if (x == 0) return 0;

      /* 子函数的 n 需要映射为【N：long】，是因为在 【n：-2147483648】情况，参数【int】是无法正常接收【-n】的值的 */
      long N = n;
      /* 模式过滤 */
      return n > 0 ? quickRec(x, N) : 1 / quickRec(x, -N);
    }

    /* 递归求值 */
    private double quickRec(double x, long N) {
      if (N == 0) return 1.0;
      /* 使用 buffer 比在 return 里运算子结果要快很多 */
      /* BugFix：这里要调用的是 quiceRec 而不是 myPow，不要写错了！ */
      cnt++;
      double buffer = quickRec(x, N / 2);
      return (N % 2 == 0 ? buffer * buffer : x * buffer * buffer);
    }
  }

  /* 第二次尝试 迭代 时间 1ms => 84.34% 空间 37.4MB => 64.59% */
  static class Solution {

    public double myPow(double x, int n) {
      /* 提前出口 */
      if (n == 0) return x == 0 ? 0 : 1;
      if (x == 1) return 1;
      if (x == 0) return 0;
      long N = n;
      /* 模式过滤 */
      return n > 0 ? quickRec(x, N) : 1 / quickRec(x, -N);
    }

    /* 迭代求值 */
    private double quickRec(double x, Long N) {
      double ans = 1.0;
      double power = x;
      /**
       * 下面这个 while 循环很精妙，我写不出来
       */
      while (N > 0) {
        if ((N & 1) == 1) ans *= power;
        power *= power;
        N >>= 1;
      }
      return ans;
    }
  }
}