算法学习笔记

刷题笔记

链表

注意使用虚拟头节点

ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
...
return dummyHead.next;

双指针

19.删除链表的倒数第 N 个结点：快指针先走 n 步，然后两个指针一起走，直到快指针走到尾部，慢指针的下一个节点就是要删除的节点。

21.合并两个有序链表：两个指针分别指向两个链表的头节点，比较两个节点的大小，将较小的节点接到新链表的尾部，然后将较小的节点的指针后移一位，重复上述操作，直到其中一个链表为空，将另一个链表的剩余部分接到新链表的尾部。

23.合并K个有序链表：使用最小堆，将每个链表的头节点放入堆中，然后每次从堆中取出最小的节点，将该节点的下一个节点放入堆中，重复上述操作，直到堆为空。

86.分隔链表：使用两个指针，一个指向小于 x 的节点，一个指向大于等于 x 的节点，遍历链表，将节点放入对应的指针指向的链表中，最后将两个链表连接起来。

142.环形链表Ⅱ：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果快指针追上了慢指针，说明有环，然后将快指针指向头节点，快慢指针每次都走一步，当快慢指针相遇时，相遇的节点就是环的入口。

160.相交链表：一个链表对应指针遍历完后继续前往另一个链表，最终两指针会在相交处相遇。

876.链表的中间节点：每次快指针走两步，慢指针走一步。

数组

滑动窗口

/* 滑动窗口算法框架 */
public void slidingWindow(String s) {
    HashMap<Character, Integer> window = new HashMap<>();
    int left = 0;
    int right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        // debug 输出的位置
        System.out.println("window: " + left + right);

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

排序

快速排序

首先找到一个基准值 pivot，然后把数组分成两部分，一部分小于 pivot，一部分大于 pivot，然后对两部分分别进行快速排序。相当于先把 pivot 放到应有的位置，之后再分别处理两侧，最后把所有值都放在应在的位置。

import java.util.Random;

class QuickSort {
    private Random random = new Random();

    public void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int pivotIdx = partition(nums, left, right);
            quickSort(nums, left, pivotIdx - 1);
            quickSort(nums, pivotIdx + 1, right);
        }
    }

    public int partition(int[] nums, int left, int right) {
        // 为了初始数组有序造成的基准选择不平衡，随机选择基准
        int randomIdx = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIdx);
        int pivot = nums[left];
        int lt = left + 1;
        int gt = right;
        // 循环不变量
        // [left, lt) <= pivot, (gt, right] > pivot
        while (true) {
            // 找到 nums[lt] > pivot
            while (lt < right && nums[lt] <= pivot) {
                lt++;
            }
            // 找到 nums[gt] <= pivot
            while (gt > left && nums[gt] > pivot) {
                gt--;
            }
            if (lt >= gt) {
                break;
            }
            // 交换两侧不满足大小关系的数字
            swap(nums, lt, gt);
        }
        // 把 pivot 放到应有的位置
        swap(nums, left, gt);
        return gt;
    }
}

二叉树

两种思路，遍历和递归。遍历的框架为

public void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

动态规划

1. 确定子问题
2. 确定递推关系
3. 确定dp数组及下标含义
4. 确定遍历顺序

贪心算法

贪心算法可以认为是动态规划算法的一个特例，每一步都做出一个局部最优的选择，最终的结果就是全局最优。

常见问题：区间调度（435.无重叠区间）

public int eraseOverlapIntervals(int[][] intvs) {
    if (intvs.length == 0) return 0;
    // 按 end 升序排序
    Arrays.sort(intvs, new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            return a[1] - b[1];
        }
    });
    // 至少有一个区间不相交
    int count = 1;
    // 排序后，第一个区间就是 x
    int x_end = intvs[0][1];
    for (int[] interval : intvs) {
        int start = interval[0];
        if (start >= x_end) {
            // 找到下一个选择的区间了
            count++;
            x_end = interval[1];
        }
    }
    return intvs.length() - count;
}

跳跃次数最少（45.跳跃游戏II）

public int jump(int[] nums) {
    int end = 0;
    int maxPosition = 0;
    int steps = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        // 找能跳的最远的
        maxPosition = Math.max(maxPosition, i + nums[i]);
        if (i == end) {
            // 遇到边界，就更新边界，并且步数加一
            end = maxPosition;
            steps++;
        }
    }
    return steps;
}