扬州做阿里巴巴的公司网站,招标网哪个好并且免费,app开发公司大连有几家,二建注册信息查询系统官网递归题目技巧
什么是递归 函数自己调用自己的情况为什么会用到递归 本质: 主问题, 可以拆分成相同的子问题 子问题, 又可以拆分出相同的子问题如何理解递归? 宏观的看待递归的过程 1)不要在意递归的细节展开图 2)把递归的函数当成一个黑盒 3)相信这个黑盒一定能够完成这个任务…递归题目技巧
什么是递归 函数自己调用自己的情况为什么会用到递归 本质: 主问题, 可以拆分成相同的子问题 子问题, 又可以拆分出相同的子问题如何理解递归? 宏观的看待递归的过程 1)不要在意递归的细节展开图 2)把递归的函数当成一个黑盒 3)相信这个黑盒一定能够完成这个任务如果写好一个递归? 1)先找到相同的子问题(变得值)-----函数头的设计 2)只关心某个子问题是如何解决的-----函数体的书写 3)注意一下函数递归的出口循环(迭代)和递归本质是可以相互转化的 循环, 适用于只有一层递归的情况, 例如链表 递归, 适合多层, 例如二叉树, 多叉树…
一. 汉诺塔问题
汉诺塔问题
class Solution {public void hanota(ListInteger a, ListInteger b, ListInteger c) {dfs(a, b, c, a.size());// 从a借助b移动到c, 移动n个盘子}public void dfs(ListInteger a, ListInteger b, ListInteger 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;//结果乘在一起}
}
