-
Notifications
You must be signed in to change notification settings - Fork 116
递归算法
zhangpan edited this page Aug 20, 2021
·
4 revisions
/**
* 递归法
* 递归的递流程直接找到递归的最后一个节点,最后一个节点的next为null,返回自身,然后开始递归的归流程
* 递归的归流程,从最后一个节点向上回溯,将最后一个节点的next指向倒数第二个节点,倒数第二个节点的next指向null
* 以此回溯到第一个节点完成链表的反转
*/
public static ListNode reverseLink2(ListNode head) {
// head == null这个条件一定要判断啊!!!!
if (head == null || head.next == null) {
return head;
}
// 返回最后一个节点
ListNode lastNode = reverseLink2(head.next);
head.next.next = head;
head.next = null;
return lastNode;
}
public static ListNode cursor;
public static ListNode reverseLink(ListNode head, int n) {
if (n == 1) {
cursor = head.next;
return head;
}
ListNode lastNode = reverseLink(head.next, n - 1);
head.next.next = head;
head.next = cursor;
return lastNode;
}
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null || head.next == null) {
return head;
}
return reverse(head, left, right);
}
private ListNode reverse(ListNode head, int left, int right) {
if (left == 1) {
return LeetCode92$.reverseLink(head, right);
}
head.next = reverse(head.next, left - 1, right - 1);
return head;
}
/**
* 递归法
*/
public ListNode mergeTwoList2(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else {
if (l1.val < l2.val) {
l1.next = mergeTwoList2(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoList2(l1, l2.next);
return l2;
}
}
}
/**
* 快速排序
* <p>
* 核心的思路是取第一个元素(或者最后一个元素)作为分界点,把整个数组分成左右两侧,左边的元素小于或者等于分界点元素,
* 而右边的元素大于分界点元素,然后把分界点移到中间位置,对左右子数组分别进行递归,最后就能得到一个排序完成的数组。
* 当子数组只有一个或者没有元素的时候就结束这个递归过程。
*/
public static void quickSort(int[] nums, int left, int right) {
if (left > right) return;
int key = nums[left];
int l = left;
int r = right;
while (l < r) {
while (nums[r] >= key && l < r)
r--;
while (nums[l] <= key && l < r)
l++;
if (l < r)
swap(nums, r, l);
}
nums[left] = nums[r];
nums[r] = key;
quickSort(nums, left, r - 1);
quickSort(nums, r + 1, right);
}
- JMM与volatile关键字
- synchronized的实现原理
- synchronized等待与唤醒机制
- AQS的实现原理
- ReentrantLock的实现原理
- ReentrantLock等待与唤醒机制
- CAS、Unsafe类以及Automic并发包
- ThreadLocal的实现原理
- 线程池的实现原理
- Java线程中断机制
- 多线程与并发常见面试题
- Android基础知识汇总
- MVC、MVP与MVVM
- SparseArray实现原理
- ArrayMap的实现原理
- SharedPreferences
- Bitmap
- Activity的启动模式
- Fragment核心原理
- 组件化项目架构搭建
- 组件化WebView架构搭建
- 为什么 Activity.finish() 之后 10s 才 onDestroy ?
- Binder与AIDL
- Binder实现原理
- Android系统启动流程
- InputManagerService
- WindowManagerService
- Choreographer详解
- SurfaceFlinger
- ViewRootImpl
- ActivityManagerService
- APP启动流程
- PMS安装与签名校验
- Dalvik与ART
- 内存优化策略
- UI界面及卡顿优化
- App启动优化
- ANR问题
- 包体积优化
- APK打包流程
- 电池电量优化
- Android屏幕适配
- 线上性能监控1--线上监控切入点
- 线上性能监控2--Matrix实现原理
- Glide实现原理
- OkHttp实现原理
- Retrofit实现原理
- RxJava实现原理
- RxJava中的线程切换与线程池
- LeakCanary实现原理
- ButterKnife实现原理
- ARouter实现原理
- Tinker实现原理
- 2. 两数相加
- 19.删除链表的倒数第 N 个结点
- 21. 合并两个有序链表
- 24. 两两交换链表中的节点
- 61. 旋转链表
- 86. 分隔链表
- 92. 反转链表 II
- 141. 环形链表
- 160. 相交链表
- 206. 反转链表
- 206 反转链表 扩展
- 234. 回文链表
- 237. 删除链表中的节点
- 445. 两数相加 II
- 面试题 02.02. 返回倒数第 k 个节点
- 面试题 02.08. 环路检测
- 剑指 Offer 06. 从尾到头打印链表
- 剑指 Offer 18. 删除链表的节点
- 剑指 Offer 22. 链表中倒数第k个节点
- 剑指 Offer 35. 复杂链表的复制
- 1. 两数之和
- 11. 盛最多水的容器
- 53. 最大子序和
- 75. 颜色分类
- 124.验证回文串
- 167. 两数之和 II - 输入有序数组 -169. 多数元素
- 189.旋转数组
- 209. 长度最小的子数组
- 283.移动0
- 303.区域和检索 - 数组不可变
- 338. 比特位计数
- 448. 找到所有数组中消失的数字
- 643.有序数组的平方
- 977. 有序数组的平方