- 递归
- 分治法/二分法
1. 递归
1.1 递归思路的主要小思想
主要分成三步
- 定义一个与题意相关的函数，要知道这个函数作用，函数的参数以及函数的返回值
- 要知道递归的最基础的结束条件
- 要让函数往递归的结束条件靠近，一点点缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。我们要找到父递归函数和子递归函数的关系，找到对应的等价关系式。
1.2 Leetcode实例
q21 合并两个有序链表
/**
* 使用递归的思路:
* 1. 首先思考这个函数的作用: 输入两个链表的首节点，返回回来两个链表合并之后的首节点
* 2. 函数基本返回条件是其中一个node为空时返回另一个node
*
* 流程是:
* 1. 先将基础的终止条件写出来
* 2. 然后比较两个node的值，需要递归更新状态调用子函数，
* 例如如果l1.val < l2. val, 递归调用l1.next = mergeTwoListsTwo(l1.next, l2) （其实也相当于更新状态）
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoListsTwo(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val){
l1.next = mergeTwoListsTwo(l1.next,l2);
return l1;
}else {
l2.next = mergeTwoListsTwo(l1,l2.next);
return l2;
}
}
q101 对称二叉树
/**
* 关于二叉树注意根节点是个特殊点
*
* 使用递归的思路
* 1. 当前树是否对称取决于其左右子节点是否和其相对称的节点是否对称
* 2. 增加一层null的叶子节点
* 3. 对称的思想主要在体现在对比对应的节点, 可以联想有两棵树找对应节点就比较简单
*
* 所以要借助函数isMirror(TreeNode t1, TreeNode t2)
* 函数的意义是输入需要进行比对的两个对称节点， 判断该节点以及子节点是否满足对称的要求
* @param root
* @return
*/
public boolean isSymmetricTwo(TreeNode root) {
return isMirrorTwo(root, root);
}
/**
* 使用递归的思路:
* 1. 因为都为树增加了一层null的叶子节点，所以基本条件是两个节点都为空返回true，若只有一个节点为空返回false
* 2. 然后比对当前节点的value，对比对应节点的子节点是否是对称的(递归，更新状态)
* @param t1
* @param t2
* @return
*/
public boolean isMirrorTwo(TreeNode t1, TreeNode t2){
if (t1==null && t2==null) return true;
if (t1==null || t2==null) return false;
return (t1.val == t2.val) &&
(isMirrorTwo(t1.right, t2.left))&&
(isMirrorTwo(t1.left, t2.right));
}
q104 二叉树的最大深度
/**
* 使用递归的思路:
* 1. 当前树的高度是否左右子树高度的最大值+1得到的，这里使用了递归
* 2. 基本结束条件是如果节点为null返回0
* @param root
* @return
*/
public int maxDepthTwo(TreeNode root){
if (root == null) return 0;
return Math.max(maxDepthTwo(root.left),maxDepthTwo(root.right))+1;
}
q226 翻转二叉树
/**
* 使用递归的思想
* 1. 当前树进行反转的条件是交换已经反转好的左右子节点的位置
*
* 这里的注意事项是:
* 需要把递归完之后返回的根节点进行交换
*/
public TreeNode invertTreeTwo(TreeNode root){
if (root==null) return root;
/**
* 这样写是不ok的，因为第一行的递归把root.left更新了，所以结果是错的 = =
root.left = invertTreeTwo(root.right);
root.right = invertTreeTwo(root.left);*/
TreeNode t1 = invertTreeTwo(root.right);
TreeNode t2 = invertTreeTwo(root.left);
root.left = t1;
root.right = t2;
return root;
}
q236 二叉树的最近公共祖先
private TreeNode ans;
public LowestCommonAncestorOfBinaryTree(){
this.ans = null;
}
/**
* 借助一个函数遍历整颗树的节点判断该节点的子节点或者本身是不是包含目标节点
* @param root
* @param p
* @param q
* @return 返回公共的父节点
*/
public TreeNode lowestCommonAncestorTwo(TreeNode root, TreeNode p, TreeNode q) {
recurseTreeTwo(root,p,q);
return ans;
}
/**
* 使用递归的思想
* 判断当前节点的子节点们或者本身是不是包含目标节点的前提是自己的左右子树是不是也同样符合此条件
*
* 并且在遍历的过程中如果发现有一个节点left + right + mid >= 2， 该节点就是我们目标要找的公共祖先节点
* @param currentNode
* @param p
* @param q
* @return 当前节点的子节点或者本身节点是不是就包含着目标节点
*/
public boolean recurseTreeTwo(TreeNode currentNode, TreeNode p, TreeNode q){
if (currentNode == null) return false;
int left = recurseTreeTwo(currentNode.left,p,q)?1:0;
int right = recurseTreeTwo(currentNode.right,p,q)?1:0;
int mid = (currentNode == p || currentNode == q)?1:0;
if (left+right+mid >=2) this.ans =currentNode;
return (left+right+mid)>0;
}
这道题除了递归还有一种比较简单的思路:
首先使用深度优先遍历遍历整棵树，在遍历的过程中使用map记录每个节点的父子关系，map的key是子节点，value是对应的父节点。
之后使用hashset记录其中一个节点的所有祖先节点，然后遍历另一个节点的祖先节点直到找到两个祖先节点集合的交集就是找到了目标结果。
2. 分治法/二分法
2.1 分治法与二分法的适用场景和基本思想
1. 分治法
分治法的基本思想是：把一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破。
每一层递归上有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立并且与原问题形式相同的子问题
- 解决：若子问题规模较小且容易被解决则直接解决，否则递归地解决各个子问题
- 合并：合并子问题的解为原问题的解
2. 二分法
使用二分法的场景通常是数组中元素是有序的，然后根据中间元素的值和目标值进行比对，判断下一步应该在哪一半（舍弃另一半）查找，从而使得时间复杂度在O(log(n)).
二分法重点在于：
- 决定查找的边界，左闭右开或者左闭右闭，根据查找的区间来决定边界的更新以及循环结束的条件（区间中至少有一个元素或者已经找到了临界值）
- 要确定自己二分查找的结果的临界条件
2.2 Leetcode实例
q23 合并K个排序链表
/**
* 按分治的思路进行求解
* 1. 这个已经细分成非常小的list了，可以将合并k个list转换成先进行小范围的两两合并
* 2. 两两合并之后，扩大list之间间隙，继续进行两两合并，这时候两两一组的数量缩小了一半
* 3. 重复上述步骤，直到间隙超过了两个数组之间的长度
*/
public ListNode mergeKListsTwo(ListNode[] lists) {
int interval = 1;
while (interval < lists.length){
for (int i=0;i<lists.length-interval;i+=2*interval){
lists[i] = merge2List(lists[i], lists[i+interval]);
}
interval *=2;
}
return lists.length>0?lists[0]:null;
}
public ListNode merge2List(ListNode l1, ListNode l2){
ListNode head = new ListNode(0);
ListNode point = head;
while (l1 != null && l2 != null){
if (l1.val <= l2.val){
point.next = l1;
l1 = l1.next;
}else {
point.next = l2;
l2 = l2.next;
}
point = point.next;
}
if (l1 == null){
point.next = l2;
} else {
point.next = l1;
}
return head.next;
}
这道题还有个思路我觉得很好：
就是首先通过把所有list之中首元素加入到PriorityQueue之中，维护一个大小小于等于所有lists大小的队列，然后循环把最小的元素pop出来，然后如果最小的那个元素的下一个不为空，就把他放入到队列之中，重复整个流程直到Queue为空就得到了答案。
q33 搜索旋转排序数组
/**
* 想要让时间复杂度是O(logN)，要使用二分的方式进行查找
* 二分的特点在于根据区间特点和目标值，可以确定目标节点落在哪一半的区间上，
* 每经历一次查找，要查找区间的长度就会缩短一半
*
* 二分查找的时候必须要注意寻找的区间和目标值
* 这道题用的区间是左闭合右闭合的区间，所以保证区间中有元素的条件是low<=high
* 在遍历的过程中判断元素看target在哪个区间，然后缩小区间范围
*
* 这道题的思路是:
* 1. 在每次划分的时候其实都是可能划分成一个有拐点的区间和一个正常的区间
* 2. 要判断在这两种区间中target出现时具备的条件
* @param nums 输入的原数组
* @param target 在原数组中要查找的目标值
* @return 目标值在数组中的index，没找到返回-1
*/
public static int searchTwo(int[] nums, int target){
if (nums.length == 0) return -1;
int i=0, j= nums.length-1;
while (i<=j){
int mid = (i+j)/2;
if (nums[mid] == target){
return mid;
} else if (nums[mid] < nums[i]){ //说明区间的左半边有拐点
if (target<nums[i] && target>nums[mid]){ //target落到右边连续区间的特点
i = mid+1;
}else {
j = mid-1;
}
} else {//说明区间左边是连续的
if (target>=nums[i] && target<nums[mid]){
j=mid-1;
}else {
i = mid+1;
}
}
}
return -1;
}
q34 在排序数组中查找元素的第一个和最后一个位置
public int[] searchRangeTwo(int[] nums, int target) {
int[] res = {-1,-1};
int leftIdx = findLeftestIndex(nums,target);
if (leftIdx == nums.length || nums[leftIdx] != target){
return res;
}
res[0] = leftIdx;
res[1] = findRightestIndex(nums, target)-1;
return res;
}
/**
* 使用二分法查找到最左边与目标值一样的元素
*
* 所选择的区间是左闭右开的
* 结束的条件是l=r, 也就是区间之中没有元素, 看r最后停在哪里
*
* 1. 当mid的值是>=目标值的时候，右半边的区域其实也不用查找了，但是r所在的位置可能是与目标值相等的
* 但是需要看看左半边还有没有和目标值一样的，如果没有就会到l=r的结束条件，返回结果
* 2. 当mid值如果小于目标值，肯定左半边都舍弃掉了，从mid+1开始查找
* @param nums
* @param target
* @return
*/
public int findLeftestIndex(int[] nums, int target){
int left =0, right = nums.length;
while (left<right){
int mid = (left+right)/2;
if (nums[mid]>=target){
right = mid;
}else {
left = mid+1;
}
}
return left;
}
/**
* 使用二分查找法找到第一个比目标值大的元素
*
* 所选择的区间是左闭右开
* 结束的条件也是l=r, 也就是区间之中没有元素, 看r最后停在哪里
*
* 1. 当mid的值是>目标值的时候，右半边的区域其实也不用查找了，但是r所在的位置可能是第一个比目标值大的
* 但是需要看看左半边还有没有比目标值大的元素，如果没有就会到l=r的结束条件，返回结果
* 2. 当mid值如果小于目标值，肯定左半边都舍弃掉了，从mid+1开始查找
* @param nums
* @param target
* @return
*/
public int findRightestIndex(int[] nums, int target){
int left =0, right = nums.length;
while (left<right){
int mid = (left+right)/2;
if (nums[mid]>target){
right = mid;
}else {
left = mid+1;
}
}
return left;
}
