力扣爆刷第107天之CodeTop100五连刷21-25
文章目录
一、103. 二叉树的锯齿形层序遍历
题目链接:https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
思路:本题要求每层先从左往右遍历,下一层从右往左,再往下一层又变成了从左往右遍历,就是这种交替遍历,其实层序遍历的方式我们不需要改变,只需要改变记录的方式,对于每层出队节点收集时,如果该层是要求正序,那么把元素从尾部添加进新队列,如果该层要求逆序,那就从头部添加进队列,因为尾插法是正序,头插法是逆序,遍历后,然后再把收集到的数据添加进总集合中即可。
class Solution {
List<List<Integer>> arrayList = new ArrayList<>();
LinkedList<TreeNode> queue = new LinkedList<>();
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if(root == null) return arrayList;
boolean flag = true;
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
LinkedList<Integer> list = new LinkedList<>();
for(int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(flag) {
list.addLast(node.val);
}else{
list.addFirst(node.val);
}
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
flag = !flag;
arrayList.add(new ArrayList(list));
}
return arrayList;
}
}
二、92. 反转链表 II
题目链接:https://leetcode.cn/problems/reverse-linked-list-ii/description/
思路:翻转链表中的一个片段,没啥技术含量,定位到为止,然后头插法,然后拼接尾部。
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode root = new ListNode(-1, head);
ListNode p = root, pro = root, pre = null, end = null;
for(int i = 0; i < left; i++) {
pro = p;
p = p.next;
}
pro.next = null;
end = p;
for(int i = left; i <= right; i++) {
pre = p.next;
p.next = pro.next;
pro.next = p;
p = pre;
}
end.next = p;
return root.next;
}
}
三、54. 螺旋矩阵
题目链接:https://leetcode.cn/problems/spiral-matrix/description/
思路:螺旋矩阵,控制上下左右边界,例如只要上边界小于等于下边界,就可以读取一行,如果左边界小于等于右边,就可以读取一列。
class Solution {
List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
int left = 0, right = n-1, up = 0, down = m-1;
while(list.size() < m * n) {
if(up <= down) {
for(int i = left; i <= right; i++) {
list.add(matrix[up][i]);
}
up++;
}
if(left <= right) {
for(int i = up; i <= down; i++) {
list.add(matrix[i][right]);
}
right--;
}
if(up <= down) {
for(int i = right; i >= left; i--) {
list.add(matrix[down][i]);
}
down--;
}
if(left <= right) {
for(int i = down; i >= up; i--) {
list.add(matrix[i][left]);
}
left++;
}
}
return list;
}
}
四、160. 相交链表
题目链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
思路:经典题目,两个链表都先求长度,然后遍历统一长度,然后同步遍历即可。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pa = headA, pb = headB;
int lenA = 0, lenB = 0;
while(pa != null) {
pa = pa.next;
lenA++;
}
while(pb != null) {
pb = pb.next;
lenB++;
}
pa = headA;
pb = headB;
while(lenA < lenB) {
pb = pb.next;
lenB--;
}
while(lenA > lenB) {
pa = pa.next;
lenA--;
}
while(pa != null) {
if(pa == pb) return pa;
pa = pa.next;
pb = pb.next;
}
return null;
}
}
五、23. 合并 K 个升序链表
题目链接:https://leetcode.cn/problems/merge-k-sorted-lists/description/
思路:采用优先级队列,链表按照头部节点进行优先级排序,出队后然后再入队,然后一直出队统计即可。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val-b.val);
for(ListNode node : lists) {
if(node != null) {
queue.add(node);
}
}
ListNode root = new ListNode();
ListNode p = root;
while(!queue.isEmpty()) {
ListNode node = queue.poll();
p.next = node;
p = p.next;
if(node.next != null) {
queue.add(node.next);
}
}
return root.next;
}
}