LeetCode100 错题本

发表于 2024-10-01 更新于 2024-11-05

Hash

字母异位词

排序每一个单词，就知道是不是异位词。

两数之和

从数组中，找到nums[i] + nums[j] == target，并返回{ i, j }。
思路是双重循环，遍历每一个元素，求和是否为target。
然而，双重循环需要 $O(N^2)$ 的复杂度。因此，可以使用一张表，使用containsKey方法识别是否存在当前i的target - nums[i]，即可减少一重循环。

关键思想

用Map高效率查找，减少一重循环。

最长连续序列

从乱序数组中，找到最长连续（数组中不一定连续）的序列。要求 $O(N)$ 。
首先用数组的值存入哈希表，然后遍历数组，判断map.constains(curNum++)。
然而，即使这样还是效率不够高。

优化

中间值不进入循环，序列开始值才进入，使用!contains(curNum - 1)判断是否为序列开始值
去重，不要哈希表，不需要键值对，使用哈希Set，只存储值。

关键思想

去重；不处理中间值

Stack

单调栈

for (int num: nums) {
    // 没找到更大数就呆在栈里；找到更大数的出栈并存入Map
    while (!stk.isEmpty() && num > stk.peek()) {
        map.put(stk.peek(), num);
        stk.pop();
    }
    stk.push(num);
}

每日温度

给一个长度为N的每日温度数组，返回一个数组，记录每一天距离下次升温的天数。

可以用双重循环，找到比当前温度大的那一天，但是这样效率太低。

优化：
使用栈，存取没有找到升温日的index，找到升温日后，一次性处理完，减少一重循环。

关键思想

使用栈存储未处理的值，找到升温日后一次性处理，减少重复动作。

下一个更大元素 I

num1为num2子集，所以只遍历num2，找到num2[i]右边的大数，存入Map；将Map结果去到num1即可。

栈实现队列

关键思想

两个栈in和out，只有out为空时，才将inpop到out中。否则会出错。

List

链表排序

链表的两种排序方法：插入排序和归并排序。
其中，归并排序需要用双指针来找到mid节点。

注意，链表交换时，不要把temp设置成a或b的引用temp = a/b;

public void exch(ListNode a, ListNode b) {
    int temp = a.val; // 或构造一个新的ListNode，否则就是在操作引用
    a.val = b.val;
    b.val = temp;
}

注意，快指针的写法

// 这样可能访问不到fast.next
if (fast.next != end) fast = fast.next;

// 正确写法
if (fast != end) fast = fast.next;

注意，链表的归并排序，不需要一个个赋值

while (head1 != null && head2 != null) {
    if (head1.val < head2.val) {
        p.next = head1;
        head1 = head1.next;
        
    } else {
        p.next = head2;
        head2 = head2.next;
    }
    p = p.next;
}

if (head1 != null) {
    p.next = head1; // 不需要循环
}

if (head2 != null) {
    p.next = head2;
}

注意，终止条件要熔断有序的链表

if (head.next == end) {
    head.next = null;
    return head;
}

删除倒数第N个节点

24.10.11
使用双指针，p2比p1快N个节点，遍历，p2 == null时，p1为要删除的节点

Tree

对称树

使用递归解决。对称遍历到两棵树的底部(null)，仍然没有出现不相等的情况，即为对称树。

private boolean checkNode(TreeNode left, TreeNode right) {
    // condition
    return checkNode(left.left, right.right) &&
           checkNode(left.right, right.left);
}

最大深度

获得每一个节点的最大深度，root再比较left与right的深度，取最大值即可。

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

最长直径

获取每个节点左右节点的最大深度之和，最大值即为二叉树的最长直径。

int longestDiameter;

private int maxDepthCache(TreeNode root) {
    if (root == null) return 0;
    // 使用缓存
    int L = maxDepthCache(root.left);
    int R = maxDepthCache(root.right);
    longestDiameter = max(longestDiameter, L + R + 1);
    return max(L, R) + 1;
}

public int diameterOfBinaryTree(TreeNode root) {
    longestDiameter = 1;
    maxDepthCache(root);
    return longestDiameter - 1;
}

反转二叉树

翻转每一个节点。

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

双指针

移动0

两个指针，i, j，j左边是排序好的数，i用于遍历。
遇到非0的数，交换i与j。

动态规划，DP

动态规划：缓存运算结果，空间换时间。

不同路径和问题

爬楼梯

Distinct Ways问题。
累加所有到达当前状态的可能路径数。

for (int i = 1; i <= target; ++i) {
    for (int j = 0; j < ways.size(); ++j) {
        if (ways[j] <= i) {
            dp[i] += dp[i - ways[j]];
        }
    }
}

不同路径II

增加了Obstacles，不能通过的点。

题目描述：
二维数组，matrix[0][0]为起点；matrix[m-1][n-1]为终点。每次只能向下走或向右走，中间有障碍物，不能通行。求到达终点的不同路径总数。

核心思想：
从起点开始逐步推导走到每一格的路径数量，并将推导结果缓存到数组dp[i][j]中，用于下一步的推导。

题解：

首先，创建二维数组dp[m][n]用于存储达到每一格的路径数，初始化第一行和第一列，将可以通行的路径初始化为1，遇到障碍物，将障碍物置0并break中止初始化。
运用动态规划算法，得出到达每一格的路径数量。

for (int i = 1; i < m; i += 1) {
    for (int j = 1; j <= n; j += 1) {
        // 只能从上方或左方走过来
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
}
return dp[m - 1][n - 1];

处理障碍物。遇到障碍物，跳过当前dp[i][j]的赋值操作。（此路不通，到达此格的路径数为默认值0）
处理边界情况。当起点或终点值为1，即有障碍物不可达时，直接返回0。

最大/最小不同路径问题

在不同路径问题的基础上，增加一个max或min函数，筛选达到每一步的最大或最小步数。
核心算法：

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] = min(dp[i], dp[i - ways[j]]) + cost / path / sum;
       }
   }
}
 
return dp[target]

零钱兑换

首先初始化dp，并填充最大值；然后对coin的倍数赋正确的值（显然，凑成coin*i元最少需要i个硬币）。为了避免小的硬币倍数覆盖大的硬币倍数，先对coins排序。
动态规划最小值核心算法
验证dp是否被修改，没有被修改，说明凑不成，返回-1；否则返回dp[amount]