算法题小整理

本文准备把常见的算法题中，不同的题型进行分类整理，相信将相同类型的思路放在一起能够起到事半功倍的效果。本分类很大程度参考了灵神的题单和题解，感谢灵神！

遍历+哈希表

两数之和
梦开始的地方，利用哈希表将2次遍历简化为1次。我们采用枚举右，寻找左的方法，将当前遍历到的j作为两数中的一个，去哈希表中寻找左边的另一个数target - j，如果能找到就是一个解；然后将自身添加到哈希表中，等待后续右边的数来找自己。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> idx = new HashMap<>(); // 创建一个空哈希表
        for (int j = 0; ; j++) { // 枚举 j
            int x = nums[j];
            // 在左边找 nums[i]，满足 nums[i]+x=target
            if (idx.containsKey(target - x)) { // 找到了
                return new int[]{idx.get(target - x), j}; // 返回两个数的下标
            }
            idx.put(x, j); // 保存 nums[j] 和 j
        }
    }
}

前缀和

303. 区域和检索 - 数组不可变

核心是“任意子数组的和，都可以表示为两个前缀和的差”，前缀和数组得开辟n+1长度，并且定义pres[i]为[0,i-1]范围内的元素和，并令pres[0]=0，想象如下两个数组：

1 2	[_, 0, 1, 2, 3, ...] : 原数组nums [0, 1, 2, 3, 4, ...] : 前缀和pres

从而任意闭区间子数组的和:nums[i] + ... + nums[j] = pres[j + 1] - pres[i]

560. 和为 K 的子数组
见前缀和
437. 路径总和 III
见前缀和

滑动窗口

定长滑动窗口

1456. 定长子串中元音的最大数目

可以背一下模板，如果窗口大小为k，总长度为n，则：

n = nums.length; // 数组长度
j = 0; // 窗口的右边界
for 0 <= j < n {
	1. 右端点进入窗口，例如累加值，算最值等等
	
	i = j - k + 1;
	if (i < 0) {
		continue; // 窗口大小还没有到k，不进行统计
	}
	
	2. 操作ans，此时是一个合法的窗口
	
	3. 左端点离开窗口
}

变长滑动窗口

模板还是类似定长滑动窗口的，但是左端点就不是直接从右端点算得了，而是要不断右移，直到满足/不满足条件。

3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> mp = new HashMap<>();
        int i = 0, ans = 0; // 最小的答案是0，此时为空串；否则至少是1
        char[] sc = s.toCharArray();
        for (int j = 0; j < sc.length; j++) {
            mp.put(sc[j], mp.getOrDefault(sc[j], 0) + 1);
            // 造成重复的必然是当前新增的，因此不断缩短左端点，直到当前新增的sc[j]不再重复
            while (mp.get(sc[j]) > 1) {
                mp.put(sc[i], mp.get(sc[i]) - 1);
                i++;
            }
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

713. 乘积小于 K 的子数组

越短越合法，因此找到个最长的合法子数组，并计算比它短的子数组的个数。注意此处枚举右端点，所以每次计算时要固定右端点，否则会重复计算。

链表

链表的操作就那么几个，很简单但熟练度要高。

反转链表

这个题要注意，链表长度为n的话，反转的循环体就执行n次，但直接看链表的话好像反转n-1次就够了，这个链表只有两个“->”：0 -> 1 -> 2；但我们得把null算进去，相当于本来在尾部的null变到头部去了，即：0 -> 1 -> 2变成null <- 0 <- 1 <- 2，所以就是要反转n=3次。

还要注意循环不变量，即pre和cur，最开始是pre为null和cur为head，最后cur为null和pre为head，所以最后直接返回pre即可。这在后面问题的下标处理上比较重要。

public ListNode reverseList(ListNode head) {
    // 反转链表无需dummyHead，需要操作n次，其中n是链表长度。
    ListNode pre = null, cur = head;
    int cnt = 0; // 用于验证操作次数
    // 循环终止时，cur为null，pre为last node，也即反转后的头结点
    while (cur != null) {
        cnt++;
        ListNode nxt = cur.next; // 记录一下
        cur.next = pre; // 首次执行循环，pre为null
        pre = cur;
        cur = nxt;
    }
    System.out.printf("%s\n", cnt);
    return pre;
}

92. 反转链表 II

要先找到目标链表的头结点的前一个node，那么如果目标链表就是第一个，无法统一编码，因此引入冗余头结点；
从冗余头结点开始，操作n次.next，就到达第n个节点，因此操作left - 1次到达第left个节点的前一个；
链表的长度是闭区间[left, right]，长度为right - left + 1，所以循环体要循环这么多次；

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummyHead = new ListNode(-1, head);
    ListNode p0 = dummyHead;
    for (int i = 0; i < left - 1; i++) {
        p0 = p0.next;
    }

    // 下面和普通反转一致，注意pre无需设置为p0，因为p0的next应该是反转结束后的头结点pre
    ListNode pre = null, cur = p0.next;
    for (int i = 0; i < right - left + 1; i++) {
        ListNode nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }

    // 此时pre是反转后的头结点，cur是下一个
    p0.next.next = cur;
    p0.next = pre;
    return dummyHead.next;
}

25. K 个一组翻转链表

如果能在短时间内熟练手敲出这个题，链表的所有题基本问题不大了，最怕面试时调试半天。

同样是需要设置冗余头节点dummyHead；注意p0的含义，是要进行反转操作的闭区间[left,right]的前一个节点，反转是和上面的题类似的，但是反转结束后要将p0设置为下一个要反转的起点，即：

p0 -> 2 -> 3 -> 4反转2和3后是p0 -> 2 <- 3 -> 4，此时的pre=3, cur=4，要将p0.next.next指向cur=4，p0.next指向pre=3，而下一个p0是旧的p0.next=2

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummyHead = new ListNode(-1, head);
    int n = 0;
    while (head != null) {
        n++;
        head = head.next;
    }

    ListNode p0 = dummyHead;
    for (int i = 0; i < n / k; i++) {
        ListNode pre = null, cur = p0.next;
        for (int j = 0; j < k; j++) { // 长度为k需反转k次
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        p0.next.next = cur;
        ListNode p0Next = p0.next; // 暂存下一个p0的值
        p0.next = pre;

        p0 = p0Next;
    }

    return dummyHead.next;
}

142. 环形链表 II

这个题直接背下来还是挺方便的，无非是快慢指针一起走，如果会相遇则存在环。此时将头结点和慢指针同步走，他们相遇的节点就是环的入口。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) { return null; }
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 相遇后，让慢指针和头指针直接一起走
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }
}

147. 对链表进行插入排序

由于每次curNode可能会被插入到链表之中，更新时不能使用curNode = curNode.next，而是应该维护一个lastSorted作为已排序链表的末尾，使用curNode = lastSorted.next进行更新；
每次遇到curNode时，根据它是否比lastSorted大，来决定是否要进行插入操作；这样的话，每次执行插入操作时，必然是在lastSorted之前的位置，就不会乱掉了。

public ListNode insertionSortList(ListNode head) {
    ListNode dummyHead = new ListNode(-1, head);
    ListNode curNode = head.next, lastSorted = head;
    while (curNode != null) {        
        if (lastSorted.val <= curNode.val) { // 1. 下一个节点已经大于有序链表的最后一个节点，直接不用插入
            lastSorted = lastSorted.next;
        } else { // 此处必然执行插入操作
            ListNode tarNode = dummyHead;
            // 已经特判过curNode.val并不比lastSorted大
            // 至少当tarNode.next为lastSorted时，会停下来，不可能tarNode.next=curNode
            while (tarNode.next.val <= curNode.val) {
                tarNode = tarNode.next;
            }
            // 此时必然tarNode.next.val > curNode.val
            // 因此将curNode插入到tarNode和tarNode.next之间
            // 1. 将curNode删除
            lastSorted.next = curNode.next;
            // 2. 将curNode插入
            curNode.next = tarNode.next;
            tarNode.next = curNode;
        }
        // 始终是有序链表末节点的下一个(lastSorted.next)，而不是当前节点的下一个(curNode.next)
        curNode = lastSorted.next;
    }
    return dummyHead.next;
}

148. 排序链表

经典归并算法，这里用的是递归实现的分治法，需要额外的空间；也可以用自底向上的迭代法，这个比较复杂就先不考虑了。
注意事项是，从中间断开时，如果是偶数，要取左侧的中间结点，否则必然左边偏长；边界情况是只有1个节点或链表为空；有序链表的合并也是比较高频的题，要保证快速写出来。

class Solution {
    public ListNode sortList(ListNode head) {
        // 链表长度为0或1时无需排序
        if (head == null || head.next == null) {
            return head;
        }

        ListNode midNode = this.middleNode(head);
        ListNode head2 = midNode.next;
        midNode.next = null; // 断开，否则无法判断链表终止

        head = this.sortList(head);
        head2 = this.sortList(head2);

        return this.mergeTwoLists(head, head2);
    }

    // [876. 链表的中间结点]的变种：在偶数时需要取左边的，而非右边的
    public ListNode middleNode(ListNode head) {
        // ListNode slow = head, fast = head; // 偶数时取右侧
        ListNode slow = head, fast = head.next; // 偶数时取左侧
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // [21. 合并两个有序链表]
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode curNode = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                curNode.next = list1;
                list1 = list1.next;
            } else { // 相等的情况可放在任意一侧
                curNode.next = list2;
                list2 = list2.next;
            }
            curNode = curNode.next;            
        }
        curNode.next = list1 == null ? list2 : list1;
        return dummyHead.next;
    }
}

23. 合并 K 个升序链表

这个题可以用最小堆来完成，写法比较简单，注意所用语言是如何定义最小堆的；代码就不贴了

1206. 设计跳表

跳表其实挺简单，就是在只有一个链表的基础上，添加多层的索引。

二分查找

你可能觉得二分查找非常简单，它也确实很简单，但我之前理解的二分查找是要判断mid是否等于target的，这种方式用来查找第一个>=target的值就不好使了，所以有必要对下标和边界进行理解。为了巩固基础，可刷灵神的题单。

34. 在排序数组中查找元素的第一个和最后一个位置

二分查找最好使用开区间，左右端点都是不可取的，即针对长度为n的数组进行二分的话，初始化就是i = -1, j = n；当然闭区间或前闭后开区间也可以，分别是i = 0, j = n - 1和i = 0, j = n；
循环的条件应该是这个区间存在元素，例如开区间应当是j - i > 1，闭区间是i <= j，前闭后开区间是i < j。

如果是要找第一个>=target的元素，我们就可以考虑nums[]中有一排target，当nums[mid]是这一排target中的一个时，我们应该将右端点j左移到mid，而不是将左端点i右移到mid，因为我们找的是第一个>=target的元素，右移左端点i可能会丢失第一个>=target的元素；
同样，我们更不能判断nums[mid]==target时就跳出循环，而是将=target的情况并入到>target或<target中，那么并入到哪里呢？这个和循环终止时最终答案的位置有关系。由于要找第一个>=target的元素，必须让j右边是>=target的，i左边是<target的（此处都包含端点i和j，因为是开区间），这样第一个>=target的就是nums[j]了。同样的，=target的情况就必须并入>target了。

下面的代码就是用于搜索nums中第一个>=target的元素下标，如果没有这个元素，则返回数组长度。

private int searchFirstLargerEqual2(int[] nums, int target) {
    int i = -1, j = nums.length;
    while (j - i > 1) {
        int mid = i + (j - i) / 2;
        if (nums[mid] < target) {
            i = mid;
        } else {
            j = mid;
        }
    }
    return j;
}

153. 寻找旋转排序数组中的最小值

始终和最后一个元素比较大小，搜索第一个>=nums[n - 1]的元素，搜索范围是闭区间[0, n - 2]；无需特判最小元素是nums[n - 1]的情况，因为这种情况下闭区间[0, n - 2]找不到它，自然会返回n-1。

单调栈

单调栈就是用来找左/右边第一个更大/小的元素的，所以可能有4种题意；并且每种题意都可以从左往右/从右往左遍历数组，所以甚至有8种做法。而且我个人暂时无法对单调栈理解得非常到位，时常不知道如何判断该出栈还是入栈。

739. 每日温度

如果要找遍历方向上的下一个更大元素，则让大元素nums[i]把栈顶的小元素弹出去，直到栈顶比nums[i]更大，此时：
那些被弹出去的小元素，它们在遍历方向上的下一个更大元素都是nums[i]；nums[i]在反遍历方向上的下一个更大元素是栈顶。

public int[] dailyTemperatures(int[] temperatures) {
    int[] ans = new int[temperatures.length];
    Deque<Integer> st = new ArrayDeque<>(); // 存储下标
    // 方法一：从右往左遍历，当遇到栈顶元素小于等于当前元素时，进行出栈
    for (int i = temperatures.length - 1; i >= 0; i--) {
        while (!st.isEmpty() && temperatures[st.peek()] <= temperatures[i]) { // 注意此处是大于等于
            st.pop();
        }
        if (st.isEmpty()) {
            ans[i] = 0;
        } else {
            ans[i] = st.peek() - i;
        }
        st.push(i);
    }
    // System.out.printf("%s\n", st); // 最后这个栈，存储的是一个前缀最大值序列

    // 方法二：从左往右遍历，如果当前值比栈顶元素大，则当前值为栈顶元素的下一个最大温度
    // for (int i = 0; i < temperatures.length; i++) {
    //     while (!st.isEmpty() && temperatures[st.peek()] < temperatures[i]) { // 注意此处不能是等于
    //         ans[st.peek()] = i - st.peek(); // 得到了栈顶元素的答案
    //         st.pop();
    //     }
    //     st.push(i);
    // }
    return ans;
}

注意等号的取法，假设是寻找更大/更小的元素，则如下：

当正向遍历时，使用大元素弹出小元素，如果相等则不要弹出，因为此时会去计算弹出元素的正向更大元素（为当前元素），必须是更大的将它弹出；

当反向遍历时，使用大元素弹出小元素，如果相等也要弹出，因为此时会计算当前元素的反向更大元素（为栈顶），因此栈顶不能和当前元素相等；

当然也可能是大于等于或小于等于的元素，此时要将上面是否带等号的情况反转，见题1475. 商品折扣后的最终价格