深圳网站建设公司pestl分析,开发平台官网,王也图片,在互易上做的网站如何修改一轮的算法训练完成后#xff0c;对相关的题目有了一个初步理解了#xff0c;接下来进行专题训练#xff0c;以下这些题目就是汇总的高频题目
题目题干直接给出对应博客链接#xff0c;这里只给出简单思路、代码实现、复杂度分析
反转链表
依据难度等级分别为反转链表、…一轮的算法训练完成后对相关的题目有了一个初步理解了接下来进行专题训练以下这些题目就是汇总的高频题目
题目题干直接给出对应博客链接这里只给出简单思路、代码实现、复杂度分析
反转链表
依据难度等级分别为反转链表、区间反转链表、K个一组反转链表【算法训练-链表 一】【反转链表】反转链表、区间反转链表、K个一组反转链表
反转链表【EASY】
LeetCode地址双指针移动逐个扭转指针方向关键词双指针临时节点 /*** 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) {// 1 入参校验如果链表为空或者只有一个节点直接返回if (head null || head.next null) {return head;}// 2 定义双指针节点进行遍历反转操作ListNode pre null;ListNode cur head;// 3 遍历链表进行反转操作while (cur! null) {// 1 定义临时节点存储当前节点的下一个节点ListNode pNext cur.next;// 2 当前节点断开指向上一个节点cur.next pre;// 3 双指针向前移动pre cur;cur pNext;}// 4 返回尾节点也就是新的头节点return pre;}
}时间复杂度ON遍历了一遍链表 空间复杂度O1 额外使用了常数级的指针变量
区间反转链表【MID】
LeetCode地址双指针到指定位置就位然后进行区间内的反转操作关键词双指针临时节点虚拟头节点 /*** 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) {// 1 入参校验如果链表为空或者只有一个节点直接返回if (head null || head.next null) {return head;}// 如果整数left和right相等或者left大于right直接返回if (left right || left right) {return head;}// 2 定义虚拟头节点与双指针如果头节点也被反转了就丢了所以需要虚拟头节点ListNode dummyHead new ListNode(-1);dummyHead.next head;ListNode pre dummyHead;ListNode cur head;// 3 双指针同时向前left-1步走到修改位置for (int i 1; i left; i) {cur cur.next;pre pre.next;}// 4 双指针开始在区间内进行反转操作1-2-3-4-5for (int i left; i right; i) {// 记录节点3ListNode pNext cur.next;// 节点2指向节点4cur.next pNext.next;// 节点3指向节点2pNext.next pre.next;// 节点1指向节点3 : 1-3-2-4-5, cur一直指向节点2pre一直指向节点1下一轮4和3-2整体交换pre.next pNext;}// 5 返回区间反转后的链表return dummyHead.next;}
}时间复杂度ON遍历了一遍链表 空间复杂度O1 额外使用了常数级的指针变量
K个一组反转链表【HARD】
LeetCode地址递归的将区间进行反转然后进行拼接关键词双指针递归 /*** 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) {// 1 入参校验如果链表为空或者只有一个节点或者k小于2直接返回if (head null || head.next null || k 2) {return head;}// 2 设置区间尾节点等于头节点ListNode tail head;for (int i 0; i k; i) {// 如果tail为空说明链表长度小于k无需反转直接返回这段子区间的头节点if (tail null) {return head;}// 如果tail不为空tail指针向前移动,移动k步,直到移动到下一区间头节点tail tail.next;}// 3 对区间进行反转操作返回新的头节点ListNode newHead reverse(head, tail);// 4 反转后head变成了当前区间尾节点tail作为下一子区间头节点传入方法递归区间连接head.next reverseKGroup(tail, k);// 5 返回新的头节点return newHead;}// 区间反转链表private ListNode reverse(ListNode head, ListNode tail) {// 1 入参判断如果链表为空或者只有一个节点直接返回if (head null || head.next null) {return head;}// 2 定义双指针节点进行遍历反转操作ListNode pre null;ListNode cur head;// 3 遍历链表进行反转操作tail为下一区间的头节点所以这里是cur ! tailwhile (cur ! tail) {// 记录当前节点的下一个节点ListNode pNext cur.next;// 当前节点断开指向上一个节点cur.next pre;// 双指针向前移动pre cur;cur pNext;}// 4 返回尾节点也就是新的头节点return pre;}
}时间复杂度ON虽然递归反转但链表只遍历了一遍 空间复杂度ON/K*O1递归的最大栈深度也就是递归深度 *每次递归的空间复杂度
合并链表
依据难度分为合并两个有序链表以及合并K个有序链表【算法训练-链表 二】【合并链表】合并两个有序链表、合并K个有序链表
合并两个有序链表【EASY】
LeetCode地址主要思路就是双指针在两个有序链表上漫游将较小的依次补全到新的链表上关键词双指针 /*** 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) {// 1 入参校验如果链表为空直接返回if (list1 null list2 null) {return null;}if (list1 null) {return list2;}if (list2 null) {return list1;}// 2 定义虚拟头节点和两个漫游指针ListNode dummyHead new ListNode(-1);ListNode p1 list1;ListNode p2 list2;ListNode p dummyHead;// 3 双指针分别在两个链表漫游while (p1 ! null p2 ! null) {// 1 下一个节点挂p1if (p1.val p2.val) {p.next p1;p1 p1.next;} else {// 2 下一个节点挂p2p.next p2;p2 p2.next;}p p.next;}// 4 如果其中一个链表空了则挂另一个链表if (p1 null) {p.next p2;}if (p2 null) {p.next p1;}// 5 返回头结点return dummyHead.next;}
}时间复杂度ONM分别对两个链表进行了遍历 空间复杂度O1 额外使用了常数级的指针变量
合并K个有序链表【HARD】
LeetCode地址应用分治的思想先将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 mergeKLists(ListNode[] lists) {return divideMerge(lists, 0, lists.length-1);}// 划分子问题private ListNode divideMerge(ListNode[] lists, int left, int right) {// 1 终止条件划分到最后的单个链表if (left right) {return null;}// 2 划分到最小单个链表直接返回if (left right) {return lists[left];}// 3 合并两个链表int mid left (right - left) / 2;return mergeTwoLists(divideMerge(lists, left, mid), divideMerge(lists, mid 1, right));}// 合并两个有序链表private ListNode mergeTwoLists(ListNode pHead1, ListNode pHead2) {// 1 入参校验如果链表为空直接返回if (pHead1 null pHead2 null) {return null;}if (pHead1 null) {return pHead2;}if (pHead2 null) {return pHead1;}// 2 定义虚拟头节点和两个漫游指针ListNode dummyHead new ListNode(-1);ListNode p1 pHead1;ListNode p2 pHead2;ListNode cur dummyHead;// 3 双指针分别在两个链表漫游while (p1 ! null p2 ! null) {// 1 下一个节点挂p1if (p1.val p2.val) {cur.next p1;p1 p1.next;} else {// 2 下一个节点挂p2cur.next p2;p2 p2.next;}cur cur.next;}// 4 如果其中一个链表空了则挂另一个链表if (p1 null) {cur.next p2;}if (p2 null) {cur.next p1;}// 5 返回头结点return dummyHead.next;}
}时间复杂度ONLogN二分分治进行了LogN次划分每次遍历时间复杂度为ON 空间复杂度OLogN 递归栈深度为LogN
链表查找
依据难度为查找链表中倒数第K个节点【算法训练-链表 六】【链表查找】链表中倒数第k个节点
链表中倒数第k个节点【EASY】
LeetCode地址解题思路就是应用快慢指针快指针先于慢指针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 trainingPlan(ListNode head, int cnt) {// 1 入参校验如果head为空或者cnt小于1返回headif (head null || head.next null || cnt 1) {return head;}// 2 定义快慢指针都指向头结点ListNode fast head;ListNode slow head;// 3 快指针先前进cnt步for (int i 1; i cnt; i) {// fast为null,证明给的用例cnt大于链表总长度返回nullif (fast null) {return null;}fast fast.next;}// 4 快慢指针同时前进当快指针为尾节点时慢指针位置就是倒数第K个while (fast.next ! null) {fast fast.next;slow slow.next;}// 5 返回slow的位置return slow;}
}时间复杂度ON遍历了一遍链表 空间复杂度O1 额外使用了常数级的指针变量
