链表题
反转链表
1 | ListNode* reverseList(ListNode* head) { |
反转链表II
反转从位置m到n的链表,一趟扫描完成。
有哨兵和无哨兵
1 | ListNode* reverseBetween(ListNode *head, int m, int n) { |
k个一组翻转链表
1 | ListNode* reverseKGroup(ListNode* head, int k) { |
分隔链表(快慢指针)
慢指针负责找到第一个 >= x 的节点的父节点,然后快指针负责从该节点开始寻找 < x 的节点,并将其插入到慢指针之后,同时慢指针指向插入的节点。
1 | ListNode* partition(ListNode* head, int x) { |
两个链表的第一个公共节点
环形链表
环形链表就是会访问到之前访问过的节点,可以通过hash表保存。若对空间有要求可以用快慢指针,这个需要推公式:
在有环的情况中,fast和slow相遇,最终的步数是f = 2s,设进入环之前有a个节点,环内有b个节点,a是它们都走过的路程,因此在环中相遇即f比s多走n个环,即 f = s + nb ,可推出s = nb ,这说明s走的路程是环b的整数倍,s在进入环前走了a个距离,那么从当前点再走a个距离便到了进入环的入口,因此再设一个从head出发 的节点,当它与相遇后的s再次相遇的节点就是环的入口。
1 | // 快慢指针 |
双指针
三数之和
求满足三数之和为0,且不重复的组合
这题的一个关键是不重复,和为0。暴力的做法是三重循环得到满足和为0的组合,再用哈希表去重。优化去重可先将它们排序后再循环,此时三个数$a, b, c$满足$a \le b \le c$ 。这样元素的组合顺序就确定了,但是没有完全去除重复,例如$-2, 2,2,2$ ,$b,c$可以两次都取2,因此在得到一个组合后,需要判断当前的循环的下一个数是否跟本次加入组合的数相同,相同则跳过。这样就可以完全去除重复。
再观察到$a \le b \le c$ ,后面两个数的大小关系是确定的,因此可以分别从左右两侧进行第二第三层循环,在它们相交时终止,这样将复杂度降到$O(N^2)$ 。
1 | vector<vector<int>> threeSum(vector<int>& nums) { |
单调栈
下一个更大的数
给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。
1 | vector<int> nextGreaterElements(vector<int>& nums) { |
思路
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
1 | // 暴力做法,直接搜索一个柱子两侧最高的柱,它的水平线一定是其中较矮的那个,这样每次左右分别搜索最高的柱子,一次搜索可以确定一个柱子上方的雨水量 |