本文主要是介绍力扣爆刷第107天之CodeTop100五连刷21-25,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣爆刷第107天之CodeTop100五连刷21-25
文章目录
- 力扣爆刷第107天之CodeTop100五连刷21-25
- 一、103. 二叉树的锯齿形层序遍历
- 二、92. 反转链表 II
- 三、54. 螺旋矩阵
- 四、160. 相交链表
- 五、23. 合并 K 个升序链表
一、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;}
}
这篇关于力扣爆刷第107天之CodeTop100五连刷21-25的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!