LeetCode算法小抄
Collection 子接口之 Queue (LeetCode上经常用，手撕算法题！！！)
Queue 与 Deque 的区别
Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。
Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值
Queue 接口 |
抛出异常 | 返回特殊值 |
| 插入队尾 | add(E e) | offer(E e) |
| 删除队首 | remove() | poll() |
| 查询队首元素 | element() | peek() |
Deque 是双端队列，在队列的两端均可以插入或删除元素。
Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：
Deque 接口 |
抛出异常 | 返回特殊值 |
| 插入队首 | addFirst(E e) | offerFirst(E e) |
| 插入队尾 | addLast(E e) | offerLast(E e) |
| 删除队首 | removeFirst() | pollFirst() |
| 删除队尾 | removeLast() | pollLast() |
| 查询队首元素 | getFirst() | peekFirst() |
| 查询队尾元素 | getLast() | peekLast() |
事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。
peek函数使用
Java中的peek函数是用于取出队列中队头元素，但不会将其从队列中移除。这样，使用peek函数可以查看队列中的队头元素，而不会改变队列的状态。
例如：
Queue<Integer> queue = new LinkedList<>(); queue.add(1); queue.add(2); queue.add(3); // 查看队头元素 Integer first = queue.peek(); // 返回1 // 查看队列中的元素 System.out.println(queue); // 输出[1, 2, 3]
peek函数在Java的Queue接口中定义，可以通过实现该接口的类来使用该函数。常见的实现类有LinkedList、PriorityQueue等。
使用peek函数时，需要注意以下几点：
如果队列为空，peek函数会返回null，而不会抛出异常。因此，使用peek函数时，需要先判断队列是否为空，避免出现空指针异常。
peek函数返回的是队列中的队头元素的副本，而不是队列中的实际元素。因此，对返回的元素进行修改并不会改变队列中的实际元素。
如果队列中的元素为null，peek函数也会返回null。因此，使用peek函数时，需要注意区分队列为空和队列中存在null元素的情况。
如果队列中的元素为不可变对象
树
结点的度：结点拥有的子树的数目
树的度：树中结点的最大的度
满二叉树：高度为h，并且由 2^ℎ –1个结点的二叉树，被称为满二叉树，满二叉树的结点的度要么为0（叶子结点），要么为2（非叶子结点）
完全二叉树：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。
二叉查找树：二叉查找树，又被称为二叉搜索树。其特点如下：设x为二叉查找树中的一个结点，x节点包含关键字key，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是 中序遍历可以让结点有序。
二叉堆和二叉树区别：
二叉堆在逻辑上其实是一种特殊的二叉树（完全二叉树）
二叉堆是存储数组，一般的链表二叉树，我们操作节点的指针，而在二叉堆里，我们把数组索引作为指针
二叉堆还分为最大堆和最小堆。最大堆的性质是：每个节点都大于等于它的两个子节点。类似的，最小堆的性质是：每个节点都小于等于它的子节点。
优先级队列(Priority Queue)
这种数据结构有一个很有用的功能，你插入或者删除元素的时候，元素会自动排序，这底层的原理就是二叉堆的操作。优先级队列有两个主要 API，分别是 insert 插入一个元素和 delMax 删除最大元素（如果底层用最小堆，那么就是 delMin）。
插入是先插到最后，然后上浮到正确位置；删除是调换位置后再删除，然后下沉到正确位置
放入PriorityQueue的元素，必须实现Comparable接口，没有实现Comparable接口怎么办？PriorityQueue允许我们提供一个Comparator对象来判断两个元素的顺序
面试：说一说 PriorityQueue
PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
这里列举其相关的一些要点：
PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。
链表
1、单链表
递归反转
经典：206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { // 如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可 if(head == null || head.next == null){ return head; } // 递归反转 ListNode last = reverseList(head.next); head.next.next = head; head.next = null; return last; } }
衍生题目：
反转链表前 N 个节点
ListNode successor = null; // 后驱节点 // 反转以 head 为起点的 n 个节点，返回新的头结点 ListNode reverseN(ListNode head, int n) { if (n == 1) { // 记录第 n + 1 个节点 successor = head.next; return head; } // 以 head.next 为起点，需要反转前 n - 1 个节点 ListNode last = reverseN(head.next, n - 1); head.next.next = head; // 让反转之后的 head 节点和后面的节点连起来 head.next = successor; return last; }
92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // base case if(left == 1){ return reverseN(head, right); } // 前进到反转的起点触发 base case head.next = reverseBetween(head.next, left - 1, right - 1); return head; } // 后继节点 ListNode successor = null; // 反转以 head 为起点的 n 个节点，返回新的头结点 private ListNode reverseN(ListNode head, int n){ if(n == 1){ // 记录第 n + 1 个节点 successor = head.next; return head; } // 以 head.next 为起点，需要反转前 n - 1 个节点 ListNode last = reverseN(head.next, n - 1); head.next.next = head; // 让反转之后的 head 节点和后面的节点连起来 head.next = successor; return last; } }
迭代反转
给定链表头结点，如何反转整个链表？
「反转以 a 为头结点的链表」其实就是「反转 a 到 null 之间的结点」
// 反转以 a 为头结点的链表 ListNode reverse(ListNode a) { ListNode pre, cur, nxt; pre = null; cur = a; nxt = a; while (cur != null) { nxt = cur.next; // 逐个结点反转 cur.next = pre; // 更新指针位置 pre = cur; cur = nxt; } // 返回反转后的头结点 return pre; }
反转 a 到 b 之间的结点
/** 反转区间 [a, b) 的元素，注意是左闭右开 */ ListNode reverse(ListNode a, ListNode b) { ListNode pre, cur, nxt; pre = null; cur = a; nxt = a; // while 终止的条件改一下就行了 while (cur != b) { nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; } // 返回反转后的头结点 return pre; }
25. K 个一组翻转链表[hard]
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { if(head == null) return null; // 区间 [a, b) 包含 k 个待反转元素 ListNode a, b; a = b = head; for(int i = 0; i < k; i++){ // 不足 k 个，不需要反转，base case if(b == null) return head; b = b.next; } // 反转前 k 个元素 ListNode newHead = reverse(a, b); // 递归反转后续链表并连接起来 a.next = reverseKGroup(b, k); return newHead; } /** 反转区间 [a, b) 的元素，注意是左闭右开 */ private ListNode reverse(ListNode a, ListNode b){ ListNode pre, cur, nxt; pre = null; cur = a; nxt = a; while(cur != b){ // 逐个结点反转 nxt = cur.next; cur.next = pre; // 更新指针位置 pre = cur; cur = nxt; } // 返回反转后的头结点 return pre; } }
2、双链表
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：
先初始化一个dummy = new ListNode(0) 为空的节点，定义一个ListNode p = dummy用来方便指针移动
如果list1 list2都不为空，作比较，小的赋值给p.next，
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 虚拟头结点 ListNode dummy = new ListNode(0); ListNode p = dummy; ListNode p1 = list1, p2 = list2; while(p1 != null && p2 != null){ // 比较 p1 和 p2 两个指针 // 将值较小的的节点接到 p 指针 if(p1.val > p2.val){ p.next = p2; p2 = p2.next; }else{ p.next = p1; p1 = p1.next; } // p 指针不断前进 p = p.next; } if(p1 != null){ p.next = p1; } if(p2 != null){ p.next = p2; } return dummy.next; } }
86. 分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode partition(ListNode head, int x) { // 存放小于 x 的链表的虚拟头结点 ListNode dummy1 = new ListNode(0); // 存放大于等于 x 的链表的虚拟头结点 ListNode dummy2 = new ListNode(0); // p 负责遍历原链表，类似合并两个有序链表的逻辑 ListNode p = head; // p1, p2 指针负责生成结果链表 ListNode p1 = dummy1, p2 = dummy2; // 这里是将一个链表分解成两个链表 while(p != null){ if(p.val > x){ p2.next = p; p2 = p2.next; }else{ p1.next = p; p1 = p1.next; } // 断开原链表中的每个节点的 next 指针 ListNode temp = p.next; p.next = null; p = temp; } // 连接两个链表 p1.next= dummy2.next; return dummy1.next; } }
23. 合并 K 个升序链表[hard]
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
这个算法是面试常考题，它的时间复杂度是多少呢？算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。
**思路：**合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？考虑使用优先队列，把k个链表加入队列中，当队列不为空，拉出一个元素，指向到p.next
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists.length == 0){ return null; } // 虚拟头结点 ListNode dummy = new ListNode(0); ListNode p = dummy; // 优先级队列，最小堆 PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.val-b.val)); // 将 k 个链表的头结点加入最小堆 for(ListNode head : lists){ if(head!=null){ pq.add(head); } } while(!pq.isEmpty()){ // 获取最小节点，接到结果链表中 ListNode node = pq.poll(); p.next = node; if(node.next != null){ pq.add(node.next); } // p 指针不断前进 p = p.next; } return dummy.next; } }
3、双指针类型的题目
双指针技巧主要分为两类：左右指针和快慢指针。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
注意细节：又使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; // 先找到倒数第n+1个 ListNode x = findFromEnd(dummy, n+1); x.next = x.next.next; return dummy.next; } // 返回链表的倒数第 k 个节点 private ListNode findFromEnd(ListNode head, int k){ ListNode p1 = head; for(int i = 0; i < k; i++){ p1 = p1.next; } ListNode p2 = head; while(p1 != null){ p2 = p2.next; p1 = p1.next; } return p2; } }
4、快慢指针的问题
876. 链表的中间结点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
思路：
我们让两个指针 slow 和 fast 分别指向链表头结点 head。
每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode middleNode(ListNode head) { // 快慢指针初始化指向 head ListNode fast = head, slow = head; // 快指针走到末尾时停止 while(fast != null && fast.next != null){ // 慢指针走一步，快指针走两步 slow = slow.next; fast = fast.next.next; } return slow; } }
判断链表是否包含环
判断链表是否包含环属于经典问题了，解决方案也是用快慢指针：
每当慢指针 slow 前进一步，快指针 fast 就前进两步。
如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。
boolean hasCycle(ListNode head) { // 快慢指针初始化指向 head ListNode slow = head, fast = head; // 快指针走到末尾时停止 while (fast != null && fast.next != null) { // 慢指针走一步，快指针走两步 slow = slow.next; fast = fast.next.next; // 快慢指针相遇，说明含有环 if (slow == fast) { return true; } } // 不包含环 return false; }
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
思路：
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = 0, lenB = 0; // 计算两条链表的长度 for(ListNode p1 = headA; p1 != null; p1 = p1.next){ lenA++; } for(ListNode p2 = headB; p2 != null; p2 = p2.next){ lenB++; } // 让 p1 和 p2 到达尾部的距离相同 ListNode p1 = headA, p2 = headB; if(lenA > lenB){ for(int i = 0; i < lenA -lenB; i++){ p1 = p1.next; } } else { for(int i = 0; i < lenB - lenA; i++){ p2 = p2.next; } } // 看两个指针是否会相同，p1 == p2 时有两种情况： // 1、要么是两条链表不相交，他俩同时走到尾部空指针 // 2、要么是两条链表相交，他俩走到两条链表的相交点 while(p1 != p2){ p1 = p1.next; p2 = p2.next; } return p1; } }
5、回文链表
寻找回文串
核心思想是从中心向两端扩展
因为回文串长度可能为奇数也可能是偶数，长度为奇数时只存在一个中心点，而长度为偶数时存在两个中心点，所以上面这个函数需要传入 l 和 r。
// 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串 String palindrome(String s, int left, int right) { // 防止索引越界 while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { // 双指针，向两边展开 left--; right++; } // 返回以 s[left] 和 s[right] 为中心的最长回文串 return s.substring(left + 1, right); }
判断一个字符串是不是回文串
因为回文串是对称的，所以正着读和倒着读应该是一样的，这一特点是解决回文串问题的关键。
boolean isPalindrome(String s) { // 一左一右两个指针相向而行 int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }
234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
这道题的关键在于，单链表无法倒着遍历，无法使用双指针技巧
1、最简单的办法就是，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { ListNode head2 = reverseList(head); while(head2 != null && head != null){ if(head.val != head2.val) return false; head = head.next; head2 = head2.next; } return true; } private ListNode reverseList(ListNode head){ if(head == null || head.next == null) return head; ListNode last = reverseList(head.next); head.next.next = head; head.next = null; return last; } }
2、其实，借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表
3、快慢指针，降低空间复杂度
class Solution { public boolean isPalindrome(ListNode head) { ListNode slow, fast; slow = fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } // 如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步： if(fast != null){ slow = slow.next; } // 从slow开始反转后面的链表，现在就可以开始比较回文串了 ListNode left = head; ListNode right = reverse(slow); while(right != null){ if(left.val != right.val) return false; left = left.next; right = right.next; } return true; } // 迭代反转 private ListNode reverse(ListNode head){ ListNode pre = null, next = null, cur = head; while (cur != null) { next = cur.next; // 逐个结点反转 cur.next = pre; // 更新指针位置 pre = cur; cur = next; } // 返回反转后的头结点 return pre; } }
总结：
首先，寻找回文串是从中间向两端扩展，判断回文串是从两端向中间收缩。对于单链表，无法直接倒序遍历，可以造一条新的反转链表，可以利用链表的后序遍历，也可以用栈结构倒序处理单链表。
具体到回文链表的判断问题，由于回文的特殊性，可以不完全反转链表，而是仅仅反转部分链表，将空间复杂度降到 O(1)。
–end–
