递归 算法专题

递归题目技巧

1. 什么是递归
   函数自己调用自己的情况
2. 为什么会用到递归
   本质: 主问题, 可以拆分成相同的子问题
   子问题, 又可以拆分出相同的子问题
3. 如何理解递归?
   宏观的看待递归的过程
   1)不要在意递归的细节展开图
   2)把递归的函数当成一个黑盒
   3)相信这个黑盒一定能够完成这个任务
4. 如果写好一个递归?
   1)先找到相同的子问题(变得值)-----函数头的设计
   2)只关心某个子问题是如何解决的-----函数体的书写
   3)注意一下函数递归的出口
5. 循环(迭代)和递归本质是可以相互转化的
   循环, 适用于只有一层递归的情况, 例如链表
   递归, 适合多层, 例如二叉树, 多叉树…

一. 汉诺塔问题

汉诺塔问题

class Solution {public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {dfs(a, b, c, a.size());// 从a借助b移动到c, 移动n个盘子}public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {if (n == 1) {c.add(a.remove(a.size() - 1));return;}dfs(a, c, b, n - 1);c.add(a.remove(a.size() - 1));dfs(b, a, c, n - 1);}
}

二. 合并两个有序链表

合并两个有序链表

/*** 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 l1, ListNode l2) {//合并两个有序链表if(l1 == null) return l2;if(l2 == null) return l1;if(l1.val < l2.val){l1.next = mergeTwoLists(l1.next, l2);//l1小, 合并l1.next 和 l2两个有序链表return l1;}else{l2.next = mergeTwoLists(l1, l2.next);//l2小, 合并l2.next 和 l1两个有序链表return l2;}}
}

三. 反转链表

反转链表

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode newHead = reverseList(head.next);//将head结点后面的逆序, 返回逆序后的头结点head.next.next = head;//将head结点插在逆序链表最后head.next = null;//将head.next置为空return newHead;}
}

四. 两两交换链表中的结点

两两交换链表中的结点

class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null){return head;}ListNode newHead = swapPairs(head.next.next);//将head.next.next 后面的链表两两交换, 返回头结点ListNode ret = head.next;head.next.next = head;//将前两个链表交换head.next = newHead;return ret;}
}

五. pow(x, n)

算法: 快速幂
实现快速幂: 1. 递归 2. 循环

class Solution {public double myPow(double x, int n) {return n < 0 ? 1.0 / pow(x, -n): pow(x, n);}public double pow(double x, int n){if(n == 0) return 1.0;double tmp = pow(x, n / 2);//先算一半return n % 2 == 0? tmp * tmp : tmp * tmp * x;//结果乘在一起}
}