LeeCode三百题-3

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

[TOC]

代码工程获取

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

#21 合并两个有序链表

就很简单
while (l1 != null && l2 != null) 中别忘了 cur = cur.next;

package Order300;

import Order300.T2_add_two_numbers.ListNode;

public class T21_merge_two_sorted_lists {

  static class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      ListNode dummy = new ListNode(0);

      ListNode cur = dummy;
      while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
          cur.next = l1;
          l1 = l1.next;
        } else {
          cur.next = l2;
          l2 = l2.next;
        }
        cur = cur.next;
      }
      /**
       * 合并后 l1 和 l2 最多只有一个还未被合并完
       * 我们直接将链表末尾指向未合并完的链表即可
       */
      cur.next = l1 == null ? l2 : l1;

      return dummy.next;
    }
  }
}

#22 括号生成

全排列 —— 回溯算法

package Order300;

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

public class T22_generate_parentheses {

  public static void main(String[] args) {
    System.out.println(new Solution().generateParenthesis(3));
  }

  static class Solution {

    void backtrack(
      List<String> walkedList,
      int goal,
      StringBuilder path,
      int left,/* 已使用的 左括号数目 */
      int right/* 已使用的 右括号数目 */
    ) {
      if (left == goal && right == goal) {
        walkedList.add(path.toString());
      } else {
        if (left < goal) {
          path.append('(');
          backtrack(walkedList, goal, path, left + 1, right);
          path.deleteCharAt(path.length() - 1);
        }
        if (right < left) {
          path.append(')');
          backtrack(walkedList, goal, path, left, right + 1);
          path.deleteCharAt(path.length() - 1);
        }
      }
    }

    public List<String> generateParenthesis(int n) {
      List<String> out = new ArrayList<>();
      backtrack(out, n, new StringBuilder(), 0, 0);
      return out;
    }
  }
}

#23 合并K个升序链表

k个链表、每个链表n个元素
分治法 1ms => 100%—— 时间复杂度 O(k*n * log_k) 空间复杂度 O(log_k)
优先队列 5ms => 66.20% —— 时间复杂度 O(k*n * log_k) 空间复杂度 O(k)
优先队列法因为有更多的空间读写操作，所以即使时间复杂度的数量级和分治法相同，实际性能也仍然弱于分治法。

分治归并法需要解决的问题 —— 简单归纳 —— 思考不够，这些问题还不够能直接指导代码的编写：
- 大问题如何拆分成小问题 —— 递归实现对小问题的求解。
- 怎样的小问题才算是最小子问题 —— if (已经是最小问题) return ...
- 最小子问题如何得到结果
- 分治，需要追求不重不漏。—— 出口管理和越界管理

package Order300;

import java.util.Comparator;
import java.util.PriorityQueue;

import BaseNode.ListNode;

public class T23_merge_k_sorted_lists {

  public static void main(String[] args) {
    ListNode[] lists = new ListNode[3];
    lists[0] = new ListNode(1);
    lists[1] = new ListNode(1);
    lists[2] = new ListNode(2);
    lists[0].add(4).add(5);
    lists[1].add(3).add(4);
    lists[2].add(6);
    // System.out.println(new Solution().mergeKLists(lists).toList());
    System.out.println(new Solution().mergeKLists(new ListNode[] {}));
  }

  /* 分治归并 1ms 100% */
  static class Solution {

    public ListNode mergeKLists(ListNode[] lists) {
      return merge(lists, 0, lists.length - 1);
    }

    /* 左右指针 遍历 链表列表。递归，二分归并。 */
    public ListNode merge(ListNode[] lists, int left, int right) {
      if (left == right) {
        /* 左右指针指向了同一个链表 */
        return lists[left];
      }

      if (left > right) {
        /* 左指针越界 —— 超过了右指针 */
        return null;
      }

      /* 二分归并 */
      int mid = (left + right) >> 1;

      /* 递归 二分 合并链表 */
      return mergeTwoLists(
        merge(lists, left, mid),
        merge(lists, mid + 1, right)
      );
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
      if (a == null || b == null) {
        return a == null ? b : a;
      }
      ListNode dummy = new ListNode(0);
      ListNode tail, l1, l2;
      tail = dummy;
      l1 = a;
      l2 = b;
      while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
          tail.next = l1;
          l1 = l1.next;
        } else {
          tail.next = l2;
          l2 = l2.next;
        }
        tail = tail.next;
      }
      tail.next = ((l1 == null) ? l2 : l1);
      return dummy.next;
    }
  }

  /* 优先队列 5ms 66.20% */
  static class Solution_优先队列 {

    public ListNode mergeKLists(ListNode[] lists) {
      PriorityQueue<ListNode> set = new PriorityQueue<>(
        new Comparator<ListNode>() {
          @Override
          public int compare(ListNode o1, ListNode o2) {
            if (o1 != null && o2 != null) {
              return o1.val - o2.val;
            } else {
              return o1 != null ? 1 : -1;
            }
          }
        }
      );
      /* 数组也可以用 for-each 来遍历 */
      for (ListNode e : lists) {
        /* 只能插入非null的节点 */
        if (e != null) set.offer(e);
      }
      /* 需要 哨兵节点dummy 和 当前节点cur 这样两个节点 */
      /* 哨兵.next 用于返回答案 */
      /* 当前cur 用于尾插法构造链表 */
      ListNode dummy = new ListNode(0);
      ListNode cur = dummy;
      while (!set.isEmpty()) {
        ListNode min = set.poll();
        cur.next = min;
        cur = cur.next;
        if (min.next != null) set.offer(min.next);
      }
      return dummy.next;
    }
  }
}

#24 两两交换链表中的节点

2021-4-26 我对链表的操作水平停留在
- 不画图基本不会做 —— 画个图基本没问题 —— 的水平🤪

package Order300;

import BaseNode.ListNode;

public class T24_swap_nodes_in_pairs {

  public static void main(String[] args) {
    ListNode list = new ListNode(0);
    list.add(1).add(2).add(3).add(4);
    System.out.println(new Solution().swapPairs(list).toList());
  }

  static class Solution {

    public ListNode swapPairs(ListNode head) {
      if (head == null || head.next == null) {
        return head;
      }
      ListNode second = head.next;
      head.next = swapPairs(second.next);
      second.next = head;
      return second;
    }
  }
}

#25 K个一组翻转链表

据官方题解介绍，本题算法不难，难在代码的实现细节，重在考验能否写出简洁优美的算法
实现思路讲解：↓↓↓ —— 只讲终极算法的思路
Step 1 将head链表分成两部分。
- 一部分是前K个
- 另外是剩下的节点
while (groupSize-- > 0) if (cur == null) return head; else cur = cur.next;
如果没等到遍历到K个，就遇到NULL了，说明 head 太短了，无需翻转，直接return head即可
如果因为 groupSize-- > 0 退出了while循环，则此时 cur 正是 剩下的节点 的首个节点
- 也就是 k 号位节点——索引从 0 开始
- ListNode kthNode = cur; 保存 k 号位节点的引用，之后有用

Step 2 原地翻转前K个节点 —— 头插法

ListNode reversedListHead = null; // 用 头插法 生成翻转后的链表
// ListNode reversedListTail = null;
cur = head;
while (cur != kthNode) {
  /* 保存未翻转的部分里，除去首个节点以后，剩下的链表 */
  ListNode second = cur.next;
  /* 头插法 step_1 把当前节点插到 翻转后链表 的头部 */
  cur.next = reversedListHead;
  // if (reversedListHead == null) reversedListTail = cur;
  /* 头插法 step_2 翻转后链表 的头指针，更新为当前节点 */
  reversedListHead = cur;
  cur = second;
}

Step 3 对剩下的节点做处理
- 怎么处理 —— reverseKGroup(kthNode, k);
- 连接到哪里 —— 翻转以后的前K个节点的最后一个 ——也就是原来的第一个的next指针 —— 也就是 head
- 综上所述：head.next = reverseKGroup(kthNode, k);
Step Return 返回被翻转好的整个链表的头指针 return reversedListHead;

package Order300;

import BaseNode.ListNode;

public class T25_reverse_nodes_in_k_group {

  static ListNode getCase() {
    ListNode list;
    list = new ListNode(0);
    list.add(1).add(2).add(3).add(4).add(5).add(6).add(7);
    return list;
  }

  public static void main(String[] args) {
    System.out.println(getCase().next.toList());
    System.out.println(
      new Solution().reverseKGroup(getCase().next, 1).toList() + "\t1"
    );
    System.out.println(
      new Solution().reverseKGroup(getCase().next, 2).toList() + "\t2"
    );
    System.out.println(
      new Solution().reverseKGroup(getCase().next, 3).toList() + "\t3"
    );
    System.out.println(
      new Solution().reverseKGroup(getCase().next, 4).toList() + "\t4"
    );
    System.out.println(
      new Solution().reverseKGroup(getCase().next, 5).toList() + "\t5"
    );
    System.out.println(
      new Solution().reverseKGroup(getCase().next, 6).toList() + "\t6"
    );
    System.out.println(
      new Solution().reverseKGroup(getCase().next, 7).toList() + "\t7"
    );
  }

  /** 使用了数组来存储即将翻转的节点，使用了递归来实现对剩余节点的处理。时间和空间复杂度都是 O(n) 效率 1ms => 35.56% */
  static class me_array_递归 {

    public ListNode reverseKGroup(ListNode head, int k) {
      // System.out.println("\t\t\t\t" + ((head == null) ? "NULL" : head.toList()) + "\t" + k);

      /* 鲁棒性 输入head太短 则不做翻转 */
      int groupSize = k;
      ListNode cur = head;
      while (groupSize-- > 0) {
        if (cur == null) return head; else cur = cur.next;
      }

      ListNode[] heads = new ListNode[k + 1];
      cur = head;
      for (int i = 0; i < k; i++) {
        heads[i] = cur;
        cur = cur.next;
      }
      /* 修复 head 长度 == k 时，于是 cur 为 null ，对 cur.next 的异常访问造成的空指针异常 */
      heads[k] = cur;

      for (int i = 1; i < k; i++) {
        heads[i].next = heads[i - 1];
      }
      heads[0].next = reverseKGroup(heads[k], k);

      return heads[k - 1];
    }
  }

  /** 递归实现，原地旋转k位，终级算法 */
  static class Solution {

    public ListNode reverseKGroup(ListNode head, int k) {
      // System.out.println("\t\t\t\t" + ((head == null) ? "NULL" : head.toList()) + "\t" + k);

      /* 鲁棒性 输入head太短 则不做翻转 */
      int groupSize = k;
      ListNode cur = head;
      while (groupSize-- > 0) {
        if (cur == null) {
          /* 如果发现已经遍历完了，则说明 head 长度不够，不用翻转 */
          return head;
        } else {
          /* 如果循环因 groupSize-- > 0 而不再继续了，则 cur 就是链表中的第 k+1 个节点 —— 可能是 null */
          cur = cur.next;
        }
      }

      /**
       * 如果循环因 groupSize-- > 0 而不再继续了
       * 则 cur 就是链表中的 k 号位节点 —— 索引从 0 开始
       * k 号位节点可能是 null
       */
      ListNode kthNode = cur;
      ListNode reversedListHead = null; // 用 头插法 生成翻转后的链表
      // ListNode reversedListTail = null;
      cur = head;
      while (cur != kthNode) {
        /* 保存未翻转的部分里，除去首个节点以后，剩下的链表 */
        ListNode second = cur.next;
        /* 头插法 step_1 把当前节点插到 翻转后链表 的头部 */
        cur.next = reversedListHead;
        // if (reversedListHead == null) reversedListTail = cur;
        /* 头插法 step_2 翻转后链表 的头指针，更新为当前节点 */
        reversedListHead = cur;
        cur = second;
      }
      /**
       * k 号位节点及其以后的节点，翻转了以后，再连接到已经翻转好了的链表的尾部
       *
       * 在上面那个 while (cur != kthNode) 开始之前
       * 因为 kthNode 是 链表中的 k 号位节点 —— 索引从 0 开始
       * 同时 cur 是 head，也就是 链表中的 0 号位节点
       * 又因为 k > 0, 所以一定有 cur != kthNode, 所以循环会至少执行一次
       * 所以，语句 reversedListTail = cur; 一定会被执行到。
       * 而当时，cur也就是head，所以 reversedListTail 的值一定会被赋为 head
       *
       * 综上所诉，reversedListTail 可以由 head 完全等价替换
       **/
      // reversedListTail.next = reverseKGroup(kthNode, k);
      head.next = reverseKGroup(kthNode, k);

      return reversedListHead;
    }
  }
}

因为关键点是简洁优美——所以有必要看看终极算法的纯净版——除去了测试部分和注释部分
20行 —— 我瞅着OK

class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
    int groupSize = k;
    ListNode cur = head;
    while (groupSize-- > 0) if (cur == null) return head; else cur = cur.next;

    ListNode kthNode = cur;
    ListNode reversedListHead = null;
    cur = head;
    while (cur != kthNode) {
      ListNode second = cur.next;
      cur.next = reversedListHead;
      reversedListHead = cur;
      cur = second;
    }
    head.next = reverseKGroup(kthNode, k);
    return reversedListHead;
  }
}

#26 删除有序数组中的重复项

就很简单，代码熟练度练手题
作为核心的遍历过程，写了两种遍历实现

// 这种遍历法，可以把代码写成一行，不过我觉得没必要
for (int i = 1; i < iMax; i++) {
  if (nums[i] == nums[i - 1]) {
    skip++;
  } else {
    nums[i - skip] = nums[i];
  }
}
// for (int i = 1; i < iMax; i++) if (nums[i] == nums[i - 1]) skip++; else nums[i - skip] = nums[i];
public int removeDuplicates(int[] nums) {
  if (nums == null || nums.length < 1) return 0;
  int skip = 0;
  int iMax = nums.length;
  for (int i = 1; i < iMax; i++) if (nums[i] == nums[i - 1]) skip++; else nums[i - skip] = nums[i];
  return iMax - skip;
}

/* 原先我以为，这样遍历，会更容易达到0ms。实验结果证明我错了 */
int cur = 1;
while (true) {
  while (cur < iMax && nums[cur] == nums[cur - 1]) {
    cur++;
    skip++;
  }
  if (cur < iMax) {
    nums[cur - skip] = nums[cur];
    cur++;
  } else {
    break;
  }
}

完整代码如下

package Order300;

public class T26_remove_duplicates_from_sorted_array {

  public static void main(String[] args) {
    int[] list;
    list = new int[] { 1 };
    list = new int[] { 1, 1 };
    list = new int[] { 1, 2 };
    list = new int[] { 1, 1, 1, 2, 3, 3 };
    int len = new Solution().removeDuplicates(list);
    for (int i = 0; i < len; i++) {
      System.out.printf("%d ", list[i]);
    }
  }

  static class Solution {

    public int removeDuplicates(int[] nums) {
      if (nums == null || nums.length < 1) return 0;
      int skip = 0;
      int iMax = nums.length;

      /* 遍历方法 一 */
      for (int i = 1; i < iMax; i++) {
        if (nums[i] == nums[i - 1]) {
          skip++;
        } else {
          nums[i - skip] = nums[i];
        }
      }

      /* 遍历方法 二 */
      // int cur = 1;
      // while (true) {
        // while (cur < iMax && nums[cur] == nums[cur - 1]) {
          // cur++;
          // skip++;
        // }
        // if (cur < iMax) {
          // nums[cur - skip] = nums[cur];
          // cur++;
        // } else {
          // break;
        // }
      // }
      return iMax - skip;
    }
  }
}

#27 移除元素

for i,x in nums 中，要么是 skip++ 要么是 nums[i - skip] = nums[i]
不可能在一次循环中同时有这两个操作。

package Order300;

public class T27_remove_element {

  public static void main(String[] args) {
    int[] list;
    list = new int[] { 1 };
    list = new int[] { 1, 1 };
    list = new int[] { 1, 2 };
    list = new int[] { 1, 1, 1, 2, 3, 3 };
    list = new int[] { 3, 2, 2, 3 };
    int len = new Solution().removeElement(list, 3);
    for (int i = 0; i < len; i++) {
      System.out.printf("%d ", list[i]);
    }
  }

  static class Solution {

    public int removeElement(int[] nums, int val) {
      if (nums == null) return 0;

      int skip = 0;
      for (int i = 0; i < nums.length; i++) {
        if (nums[i] == val) {
          skip++;
        } else if (i - skip >= 0) {
          nums[i - skip] = nums[i];
        }
      }
      return nums.length - skip;
    }
  }
}

#28 实现 strStr()

KMP算法的核心为前缀函数，记作π(i)
π(i) 之定义
- 对于长度为 m 的字符串 s，其前缀函数π(i) ( 0 ≤ i ≤ m )
- 表示 s 的子串[0:i]的最长的相等的真前缀与真后缀的长度
- 如果不存在符合条件的前后缀，那么π(i) = 0
真前缀、真后缀 —— 不等于自身的前缀、后缀
π(i) 之性质 —— π(i) ≤ π(i-1) + 1
- 约定：用 真前缀 代替 符合条件的最长相等真前缀。真后缀同理。
- 对于子串s[0:i]，其真前缀为 s[ 0 : π(i)-1 ]，其真后缀为 s[ i-(π(i)-1) : i ]
- 已知真前缀等于真后缀，即， s[ 0 : π(i)-1 ] = s[ i-(π(i)-1) : i ]
- 真前缀与真后缀的右界同时左移，显然也应该相等，即， s[ 0 : π(i)-2 ] = s[ i-(π(i)-1) : i-1 ]
- ??? 依据 π(i-1) 定义得，π(i-1) ≥ π(i) - 1，即，π(i) ≤ π(i-1) + 1
π(i) 之性质 —— 如果 s[i] = s[π(i-1)] 那么 π(i) = π(i-1) + 1

#29 两数相除

关于如何用位运算实现int32的加减乘除，在**《左神》P350** 有专门的详细讲解。
完整详细的详细解释我这里就不写了。打字不方便。

#30 串联所有单词的子串

滑动窗口的**“初衷”**
- 窗口的滑动时间复杂度是 O(n)
- 每次滑动后，窗口内的update计算复杂度是常量O(1)
题目中说明了，要求的单词集words中单词，长度都相同 —— 设单词长度为 d
因此，每次滑动窗口时，步长不再应该是 1，而应该是 d
从 0 ~ d-1 设置 d 个不同起点的滑动窗口，即可覆盖扫描整个解空间
实现细节复盘：
- 因为是用 new String().subString(begin,end)来获取子串
- 所以index的合法值是[0,iMax]——注意是右边界可取得的
- 如何判断当前窗口是否满足 words 的要求 —— 用两个 HashMap<String,Integer>，一个存要求，一个存已达指标
- 关键—— HashMap 中的 value 是包装类 Integer，因此判断相等不能使用 == 而应该用 .equals
- 相关知识点：
  - == 是内存地址比较
  - Integer 是 包装类
  - 包装类的缓存机制
  - Integer缓存范围是 [-127,128]
多起点滑动窗口，用两个HashMap判等 —— 效率 17ms => 80.94%

package Order300;

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

public class T30_substring_with_concatenation_of_all_words {

  public static void main(String[] args) {
    String s;
    String words[];

    s = "barfoothefoobarman";
    words = new String[] { "foo", "bar" };
    System.out.println(new Solution().findSubstring(s, words));

    s = "barfoofoobarthefoobarman";
    words = new String[] { "bar", "foo", "the" };
    System.out.println(new Solution().findSubstring(s, words));

    s = "wordgoodgoodgoodbestword";
    words = new String[] { "word", "good", "best", "good" };
    System.out.println(new Solution().findSubstring(s, words));

    StringBuilder sb = new StringBuilder("a");
    words = new String[5000];
    for (int i = 0; i < 5000; i++) {
      words[i] = sb.toString();
    }
    for (int i = 1; i < 5000; i++) {
      sb.append('a');
    }
    s = sb.toString();
    System.out.println(new Solution().findSubstring(s, words));
  }

  public static class Solution {

    public List<Integer> findSubstring(String s, String[] words) {
      List<Integer> answers = new ArrayList<>();
      if (
        s == null ||
        s.length() == 0 ||
        words == null ||
        words.length == 0 ||
        s.length() < words[0].length()
      ) {
        return answers;
      }
      int iMax = s.length();
      int wordsSize = words.length;
      int step = words[0].length();
      int L = step * wordsSize;
      Map<String, Integer> requireMap = new HashMap<String, Integer>(
        wordsSize
      ) {
        {
          for (int i = 0; i < wordsSize; i++) {
            if (keySet().contains(words[i])) {
              put(words[i], get(words[i]) + 1);
            } else put(words[i], 1);
          }
        }
      };
      Map<String, Integer> windowMap = new HashMap<String, Integer>(wordsSize);
      Set<String> keySet = requireMap.keySet();

      for (int begin = 0; begin < step; begin++) {
        for (String key : keySet) {
          windowMap.put(key, 0);
        }
        for (int left = begin; left + L <= iMax; left += step) {
          if (left == begin) {
            for (int i = left; i + step <= left + L; i += step) {
              String cur = s.substring(i, i + step);
              if (keySet.contains(cur)) {
                windowMap.put(cur, windowMap.get(cur) + 1);
              }
            }
          } else {
            String _old = s.substring(left - step, left);
            String _new = s.substring(left + L - step, left + L);
            if (keySet.contains(_old)) {
              windowMap.put(_old, windowMap.get(_old) - 1);
            }
            if (keySet.contains(_new)) {
              windowMap.put(_new, windowMap.get(_new) + 1);
            }
          }
          boolean isOK = true;
          for (String key : keySet) {
            /* Integer 包装类 的判断相等，不能用 == 那是比较内存地址的 */
            if (!requireMap.get(key).equals(windowMap.get(key))) {
              isOK = false;
              break;
            }
          }
          if (isOK) {
            answers.add(left);
          }
        }
      }

      return answers;
    }
  }
}