庐江网站广告怎么做,互助资金盘网站开发,为什么浙江建设厅网站,做视频网站视频加载过慢文章目录 链表反转链表合并删除链表倒数第 n 个结点找链表的中间结点链表中环的检测排序算法递归 趁空闲时间刷一遍极客时间上王争的《数据结构与算法之美》课程#xff0c;个人觉得写的很好#xff0c;每章节由浅入深且从基础到引入设计类问题#xff0c;如果写过很多代码想… 文章目录 链表反转链表合并删除链表倒数第 n 个结点找链表的中间结点链表中环的检测排序算法递归 趁空闲时间刷一遍极客时间上王争的《数据结构与算法之美》课程个人觉得写的很好每章节由浅入深且从基础到引入设计类问题如果写过很多代码想要进行架构设计转型时再回头看这些基础知识还蛮有趣的以下纪录下随着课程走的部分实现代码和思考 内容主要是笔记和代码注手写一遍代码是有必要的 链表反转
单链表反转
class ListNode { int val; ListNode next; ListNode(int val) { this.val val; this.next null; }
public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode nextTemp curr.next; // 临时保存下一个节点 curr.next prev; // 反转当前节点的指针 prev curr; // 将前一个节点移动到当前节点 curr nextTemp; // 将当前节点移动到下一个节点 } return prev; // prev 最后会指向新的头节点 }
}链表合并
两个有序的链表合并用到了哨兵dummy这个指针记录
class ListNode { int val; ListNode next; ListNode(int val) { this.val val; this.next null; } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 创建一个哨兵节点方便处理边界情况 ListNode dummy new ListNode(0); ListNode curr dummy; // 使用两个指针分别遍历两个链表 while (l1 ! null l2 ! null) { if (l1.val l2.val) { curr.next l1; l1 l1.next; } else { curr.next l2; l2 l2.next; } curr curr.next; } // 处理剩余节点只能有一个链表还有剩余节点 if (l1 ! null) { curr.next l1; } else { curr.next l2; } }
}删除链表倒数第 n 个结点
使用快慢指针快慢指针在解很多链表题目中都有体现
class ListNode { int val; ListNode next; ListNode(int val) { this.val val; this.next null; } public ListNode removeNthFromEnd(ListNode head, int n) { // 创建一个哨兵节点简化头节点被删除的情况 ListNode dummy new ListNode(0); dummy.next head;// 初始化快慢指针 ListNode fast dummy; ListNode slow dummy; // 先将快指针向前移动 n1 步 for (int i 0; i n; i) { fast fast.next; } // 然后同时移动快慢指针直到快指针到达链表末尾 while (fast ! null) { fast fast.next; slow slow.next; } // 此时慢指针指向的节点的下一个节点就是要删除的节点 slow.next slow.next.next; // 返回头节点注意是哨兵节点的下一个节点 return dummy.next; }
}找链表的中间结点
使用快慢指针来实现快指针每次移动2步而慢指针每次移动1步。当快指针到达链表末尾时慢指针将恰好位于链表的中间。
class ListNode { int val; ListNode next; ListNode(int val) { this.val val; this.next null; } public ListNode findMiddle(ListNode head) { // 初始化快慢指针 ListNode slow head; ListNode fast head; // 快指针每次移动两步慢指针每次移动一步 while (fast ! null fast.next ! null) { slow slow.next; // 慢指针移动一步 fast fast.next.next; // 快指针移动两步 } // 当快指针到达链表末尾时慢指针指向中间节点 return slow; }
}链表中环的检测
快慢指针进行遍历如果快慢指针不相遇说明没有环
class ListNode { int val; ListNode next;ListNode(int val) { this.val val; this.next null; } public boolean hasCycle(ListNode head) { if (head null || head.next null) { // 如果链表为空或只有一个节点则不可能有环 return false; } ListNode slow head; ListNode fast head;// 快慢指针开始移动直到它们相遇或快指针到达链表末尾 while (fast ! null fast.next ! null) { slow slow.next; // 慢指针每次移动一步 fast fast.next.next; // 快指针每次移动两步 // 如果快慢指针相遇说明链表中存在环 if (slow fast) { return true; } }// 快指针到达链表末尾说明链表中没有环 return false; }
}排序算法
常用的冒泡、选择、插入、归并、快速算法手写很重要写出来会发现即使是一个小的改动对于程序的消耗来说都有所差别 关于排序的算法还可以参照https://mp.weixin.qq.com/s/HQg3BzzQfJXcWyltsgOfCQ 在要求高效的很多基础框架代码中都是用了快速排序递归思路
// 冒泡排序
void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { // 交换arr[j]和arr[j 1] int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } }
} // 选择排序
void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) { minIdx j; } } // 交换arr[i]和arr[minIdx] int temp arr[minIdx]; arr[minIdx] arr[i]; arr[i] temp; }
} // 插入排序
void insertionSort(int[] arr) { int n arr.length; for (int i 1; i n; i) { int key arr[i]; int j i - 1; // 将arr[i]插入到已排序部分arr[0..i-1] while (j 0 arr[j] key) { arr[j 1] arr[j]; j j - 1; } arr[j 1] key; }
}
// 归并排序
void mergeSort(int[] arr, int left, int right) { if (left right) { int mid left (right - left) / 2; // 递归排序两个子数组 mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); // 合并两个已排序的子数组 merge(arr, left, mid, right); }
}
void merge(int[] arr, int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int[] L new int[n1]; int[] R new int[n2]; for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; int i 0, j 0; int k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } while (i n1) { arr[k] L[i]; i; k; } while (j n2) { arr[k] R[j]; j; k; }
}
// 快速排序
void quickSort(int[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); // 递归排序两个子数组 quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); }
}
int partition(int[] arr, int low, int high) { int pivot arr[high]; int i (low - 1); for (int j low; j high; j) { if (arr[j] pivot) { i; // 交换arr[i]和arr[j] int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } // 交换arr[i 1]和arr[high] (或pivot) int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1;
}递归
递归是一种分治的思维不适合人类大脑但天然是计算机的处理方式人类大脑总是想把事情的步骤想的很清晰12345每一步骤做什么但是计算机不是这样的 递归也存在堆栈溢出和重复计算的问题专栏中也给了对应的方式重复计算可以通过缓存来解决
// 上楼梯问题中可以适当增加缓存来消除重复计算
public int f(int n) {if (n 1) return 1;if (n 2) return 2;// hasSolvedList 可以理解成一个 Mapkey 是 nvalue 是 f(n)if (hasSolvedList.containsKey(n)) {return hasSovledList.get(n);}int ret f(n-1) f(n-2);hasSovledList.put(n, ret);return ret;
}
