精华内容
下载资源
问答
  • 关于递归: 程序调用自己编程技巧叫做递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义 或说明中有直接或间接调用自身一种方法,它通常把一个大型复杂问题层层转化为一个与原问题...

    关于递归:

    程序调用自己的编程技巧叫做递归。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义

    或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小

    的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量

    例如:文中代码、Fibonacci数列求解、汉诺塔等

    缺点:易发生StackOverFlow

    关于递推:

    递推算法是一种用若干步可重复的简运算(规律)来描述复杂问题的方法。递推是序列计算机中的一种常用算

    法。它是按照一定的规律来计算序列中的每个项,通常是通过计算机前面的一些项来得出序列中的指定象的值。

    关于迭代 :

    迭代是重复反馈过程的活动,其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”,

    =====================================================

    递归与递推的区别:

    一、递归整体是分为两步的:1.向下递推直到限制条件到了。

                      2.回溯结果。

     

    二、递推就是从初始态出发,不断改变自己的过程。

    如:我想让1+2+4+...+64;

    讲故事阶段:

    Leo偷偷溜进电影院看电影(黑灯瞎火),然鹅并不知道自己在第几排,于是乎问一下前一排的观众Q,

    Q也不高兴,直接找自己前一排的P.......问到坐在第一排观众A了,随后每一排的观众向后传递信息,

    Leo最终得到排号b( ̄▽ ̄)d (可以自行判断)

    TuJia笔试小题目:

    func(int a){
        if(a<2){
            return 1;
        }
        return func(a-2)+func(a-1); 
    }
    func(5) = ?

    脑海里想象一下 Java栈结构——FILO:方法进栈-运算-出栈,出现方法调自身方法,那就屯在栈里。

    每有一个叶子节点,返回1 ,

    public class TuJia {
    	static int count  = 0;
    	public static void main(String[] args){
    		System.out.println("结果为"+tt(5));
    		System.out.println("共计"+count+"次调用");
    	}
    	static public int tt(int n){
    		if(n<2){
    			count++;
    			return 1;
    		}
    		count++;
    		return tt(n-2)+tt(n-1);
    	}
    }

    结果为:

    展开全文
  • 二叉树的深度算法,是二叉树中比较基础的算法了。对应 LeetCode 第104。 然后你会发现 LeetCode 后面有些算法需要用到这个算法的变形,比如第110、543。这两道,如果你知道二叉树深度算法的递归过程,就...

    二叉树的深度算法,是二叉树中比较基础的算法了。对应 LeetCode 第104题

    然后你会发现 LeetCode 后面有些算法题需要用到这个算法的变形,比如第110题、543题。这两道题,如果你知道二叉树深度算法的递归过程,就很容易做出来。

    关于二叉树的相关知识,可以看我的这篇文章:数据结构】树的简单分析总结(附js实现)

    题目描述

    给定一个二叉树,找出其最大深度。

    二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

    说明: 叶子节点是指没有子节点的节点。

    示例: 给定二叉树 [3,9,20,null,null,15,7],

        3
       / \
      9  20
        /  \
       15   7
    返回它的最大深度 3 。
    复制代码

    注意这里的二叉树是通过 链式存储法 存储的,而不是数组。

    1. 递归是什么

    在解题之前,我们先了解下什么是递归(如果你已经掌握,请直接跳过这节)。

    那么就开始朗(wang)诵(ba)课本(nian)内容(jing)。

    递归分为 “递” 和 “归”。“递” 就是传进去,“归”就是一个函数执行完解决了一个子问题。递归的实现通过不停地将问题分解为子问题,并通过解决子问题,最终解决原问题。

    递归的核心在于递归公式,当我们分析出递归公式后,递归问题其实也就解决了。递归是一种应用广泛的编程技巧,很多地方都要用到它,比如深度优先遍历(本题就用到这个)、二叉树的前中后序遍历。

    递归需要满足三个条件:

    1. 可以分解为多个子问题;
    2. 子问题除了数据规模不同,求解思路不变;
    3. 存在递归终止条件。

    递归的特点是代码比较简洁,虽然大多数情况下你都比较难理解递归的每个过程,因为它不符合人类的思维习惯,但其实你也不必去真正了解,你只要知道B和 C 被解决后,可以推导出 A 就行,无需考虑 B 和 C 是如何通过子问题解决的(因为都和前面一样的!)。

    其次递归如果太深,可能会导致内存用尽。因为递归的时候要保存许多调用记录,就会维护一个调用栈,当栈太大而超过了可用内存空间,就会发生内存溢出的情况,我们称之为 堆栈溢出。解决方案有下面 4 种:

    1. 递归调用超过一定深度之后,直接报错,不再递归下去。 深度到底到多少会发生溢出,并不能通过计算得出,另外报错也导致程序无法继续运行下去,所以这个方案虽然确实可以防止内存溢出,并好像没有什么用。
    2. 缓存重复计算。 递归可能会重复调用已经求解过的 f(k) 的结果,对于这种情况,就要对 f(k) 进行缓存,一般用哈希表来缓存(js 中可以通过对象实现)。当我们第二次执行 f(k) 时,直接从缓存中获取即可。
    3. 改为非递归代码。 其实就是改为循环的写法。修改后的循环写法本质上也是递归,只是我们手动地实现了递归栈而已。循环写法代码实现会比递归复杂,而且也不够优雅。
    4. 尾递归。 使用的是一种 尾调用优化 的技术,需要看运行环境是否提供这种优化。在支持尾调用优化的情况下,如果函数 A 的 最后一步 调用另一个函数 B,那进入 B 时,就不会保留 A 的调用记录(比如一些 A 的内部变量),这样就不会产生很长的调用栈,而导致堆栈溢出了。

    说到递归,那就不得不提递归的一道经典题目了,那就是“爬楼梯问题”,对应 LeetCode 第70题

    爬楼梯的问题描述是:假设你正在爬楼梯。需要 n (正整数)阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

    首先你可以列出 n = 1,n = 2... 的走法,试着找出规律。

    走法 走法总数
    1 1 1
    2 1 + 1,2 2
    3 1 + 2, 1 + 1 + 1, 2 + 1 3

    到这里我们就可以发现一些规律了。那就是 走到第 3 阶的走法为 2 阶 和 1 阶的和。为什么会这样呢?我们就要透过现象发现本质,本质就是,要走到第 n 阶,首先就要先走到 第 n-1 阶,然后再爬一个台阶,或者是先走到 n - 2 阶,然后爬两个台阶。

    所以我们得到这么一个递归公式:f(n) = f(n-1) + f(n - 2)

    递归写法:

    var climbStairs = function(n) {
        let map = {};
        function f(n) {
            if (n < 3)  return n;
            if (map[n]) return map[n];
            
            let r =  f(n-1) + f(n - 2);
            map[n] = r;
            return r;
        }
        return f(n)
    复制代码

    因为 f(n) = f(n-1) + f(n-2)。这里的f(n-1),又由 f(n-2)+f(n-3) 得出。这里的 f(n-2) 被执行了两次,所以就需要缓存 f(n-2) 的结果到 map 对象中,来减少运算时间。

    循环写法:

    var climbStairs = function(n) {
        if (n < 3) return n;
    
        let step1 = 1,  // 上上一步
            step2 = 2;  // 上一步
    
        let tmp;
        for (let i = 3; i <= n; i++) {
            tmp = step2;
            step2 = step1 + step2;
            step1 = tmp;
        }
        return step2;
    
    };
    复制代码

    2. 问题分析

    说完递归后,我们就来分析题目吧。

    首先我们试着找出递归规律。首先我们知道,除了叶子节点,二叉树的所有节点都有会有左右子树。那么如果我们知道左右子树的深度,找出二者之间的最大值,然后再加一,不就是这个二叉树的深度吗?其次以 叶子节点 为根节点的二叉树的高度是 1,我们就可以根据通过这个作为递归的结束条件。

    3. 代码实现

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    var maxDepth = function(root) {
        function f(node) {
            if (!node) return 0;
            return Math.max(f(node.left), f(node.right)) + 1;
        }
        return f(root);
    };
    复制代码

    这里用到了深度优先遍历,会沿着二叉树从根节点往叶子节点走。另外,因为没有重复计算,所以不需要对结果进行缓存。还有就是,因为没有多余的变量要保存,可以直接把 maxDepth 函数写成递归函数。

    4. 扩展:数组存储的二叉树如何求深度?

    关于如何用数组存储(顺序存储法)的二叉树,这里就不提了,请看我前面提到的相关文章。

    求一个数组表示的二叉树的深度,可以看作求 对应的完全二叉树的深度

    在此之前,我们先看看如何求出一个节点个数为 n 的 满二叉树 的深度 k。

    深度 k 个数 n
    1 1
    2 3 (=1+2)
    3 7 (=1+2+4)
    4 15 (=1+2+4+8)

    规律很明显,通过等比数列求和公式化简,我们得到 k = Math.log2(n+1),其中 k 为深度,n 为满二叉树的节点个数。那么对于一个完全二叉树来说,将 k 向上取整即可:k = Math.ceil( Math.log2(n+1) )

    所以对于一个顺序存储法存储的长度为 n 的二叉树,其高度 k 为:

    k = Math.ceil( Math.log2(n+1) )
    复制代码

    (需要注意的是,这里的数组是从 0 开始存储节点的。)

    参考

    1. 阮一峰的网络日志——尾调用优化
    2. 数据结构与算法之美:10 | 递归:如何用三行代码找到“最终推荐人”?
    展开全文
  • * 三个柱子,其中一个柱子全是由小到大的盘子 * 需要把这些盘子全部移动到另一个上并且顺序不变 * 要求:一次移动一个并且大的只可以在小下面 *** 【算法思想】**: * 1,每次可以把第1~N-1个移到辅助柱子,第N...

    汉诺塔游戏

     * **【题目】**
     * 三个柱子,其中一个柱子全是由小到大的盘子
     * 需要把这些盘子全部移动到另一个上并且顺序不变
     * 要求:一次移动一个并且大的只可以在小的下面
     *** 【算法思想】**:
     * 1,每次可以把第1~N-1个移到辅助柱子,第N个移动到目标柱子
     * 2,然后将原始柱子作为辅助柱子,辅助柱子作为原始柱子
     * 3,在进行第一步
     *** 【总结】**
     * 学习递归要整体化思想把拆分后的一部分看作一个整体来处理
     * 看到这个代码一直不明白,总是想把他代码套进去看一看
     * 假如有4层的汉诺塔,把前3层作为整体就感觉一切都是那么顺其自然了
     * 不必要担心前3层的操作,因为前3层在函数里面还会被分为第3层和前2层
     * 所以说只需要将事物整体化,才可以看明白递归,才可以遇到问题想出递归代码
    
    public class 汉诺塔游戏 {
    
    	public static void main(String[] args) {
    		String A="A",B="B",C="C";
    		printHanoiTower(4, A,C,B);
    	}
    public static void printHanoiTower(int N,String from,String to,String help){
    	if(N==1){
    		System.out.println("move"+N+"from"+from+"to"+to);
    		return;
    	}
    	printHanoiTower(N-1, from, help,to);
    	System.out.println("move "+N+" from "+from+" to "+to);
    	printHanoiTower(N-1, help,to,from);
    }
    }
    

    蓝桥杯题目

    • 【题目】
    • 这样的巧合情况可能还有很多,比如: 27 * 594 = 297 * 54
    • 假设a b C d e代表1~9不同的5个数字(注意是各不相同的数字,且不含0)
    • 能满足形如:abcde=adbce这样的算式一共有多少种呢?
    • 请你利用计算机的优势寻找所有的可能,并回答不同算式的种类数。
    • 满足乘法交换律的算式计为不同的种类,所以答案肯定是个偶数。
    • 【算法思想】
    • 分为2个函数来做
    • 1,算出1到l选k个数的所有可能组合
    • 2,排出每不同的5个数的所有排列顺序
      *【总结】
    • 先找/排出第1个数,再找/排第剩下的
    • 函数做一个for循环,剩下的函数调用函数
    • !!!要注意的就是要注意其中的变量值!!!
    • 我犯错的经常之处
    public class 练习题 {
    	static int max = 0;
    	public static void main(String[] args) {
    		int [] arr=new int[5];
    		f1(1,9,5,0,arr);
    		System.out.println(max);
    		}
    	//1到l选k个数的所有可能组合
    public static void f1(int i,int l ,int k,int j,int [] arr){
    	if(j==k){
    		f2(arr,0);
    	}
    	else
    	{	
    	for(;i<=l;i++){
    		arr[j]=i;
    		j++;i++;
    		f1(i, l,k,j,arr);
    		j--;i--;
    	}
    	}
    }
    //排出每不同的5个数的所有排列顺序
    private static void f2(int[] s, int k) {
    	  if(k==s.length){  
    		  if((s[2]*100+s[3]*10+s[4])*(s[1]+s[0]*10)==(s[0]*100+s[3]*10+s[1])*(s[2]*10+s[4])){
    				max++; 
    			}
    	  }		  
    	  for(int i=k;i<s.length;i++){
    		  int temp=s[k]; s[k]=s[i]; s[i]=temp;
    		  f2(s, k+1);
    		  temp=s[k]; s[k]=s[i]; s[i]=temp;
    	  }
    	}
    }
    

    方法二:当然也有暴力解法 带过一下 ,这里主要总结了一下递归思想

    //方法二
    //暴力解法
    public static void f3(){
    	int count = 0;
        for (int a = 1; a < 10; a++) {
            for (int b = 1; b < 10; b++) {
                if (b != a) for (int c = 1; c < 10; c++) {
                    if (c != a && c != b) for (int d = 1; d < 10; d++) {
                        if (d != a && d != b && d != c) for (int e = 1; e < 10; e++) {
                            if (e != a && e != b && e != c && e != d) {
                                if ((a * 10 + b) * (c * 100 + d * 10 + e) == (a * 100 + d * 10 + b) * (c * 10 + e)) {
                                    count++;
                                }
                            }
                        }
                    }
                }
    
            }
        }
        System.out.println(count);//142
    
    }
    

    【总结】
    有时候想不出来换一种思维来做,看作整体!看作整体!这样就会恍然大悟,并且不会纠结算法到底怎么写的,要不要套一下函数代码来看看,在此过程也要注意变量的问题。
    上面是我的个人总结和看法,如有不当之处希望大佬指出,也希望对在学递归的同学有帮助。

    展开全文
  • 昨天按照自己理解,将网上抄代码按照递归来理解,今早女神发信息说这是动态规划,递归是函数自己调用自己,一看果然不是递归,大体思路没啥太问题,那也重新理解下: 以下是我昨天对于这道题的理解: 拿到这道...

    作为一名小白,完全不知道动态规划究竟是什么意思,百度了下词条我语文不好看不懂它在说什么,那不如联系下实际,看看动态规划算法究竟怎么用。来自杭电oj1028题
    在这里插入图片描述
    在这里插入图片描述
    昨天按照自己的理解,将网上抄的代码按照递归来理解,今早女神发信息说这是动态规划,递归是函数自己调用自己,一看果然不是递归,大体思路没啥太大问题,那也重新理解下:
    以下是我昨天对于这道题的理解:

    拿到这道题,我们不妨转变思路,把此题转变成n个苹果装入n个盘子的过程,我们需要两个变量i,j分别代表苹果数和盘子数,由于ij需要进行循环,且苹果作为大循环,盘子作为小循环,大循环嵌套小循环,所以我们定义一个二维数组来形象的存储苹果和盘子,最后将本身的值作为我们想要的结果——有几种摆放方法。接下来我们要考虑苹果和盘子的数量关系:

    1. 盘子数大于苹果数:很简单将问题转化成将苹果放入和苹果数量等同的盘子中即可。
    2. 盘子数等于苹果数:根据题中示例,可明了的将问题转化为将苹果放入盘子数-1的盘子中的所有情况加一
    3. 盘子数小于苹果数:又得分两种情况第一种情况是填完苹果之后还有空余盘子,第二种情况就是盘子都填满了;第一种情况的话,如果填完之后还有空余盘子,那就可以把那个空的盘子(至少有一个)拿走,所以减一最后总的情况数还是不变的,第二种情况的话,如果都填满了,那么我们把每一个盘子都拿走一个苹果之后,他的这种情况应该和没拿之前那种情况是一样的,其实我有这地方有点儿想不太懂,我拿笔写了一下,一下子懂了,所以年轻人遇到问题一定要多动笔。
      上面第二条分析很不清楚,今早看了女神给我发的信息,正确的理解应该是当苹果数i=盘子数j 时,
      分两种情况讨论:
      1、至少有一个盘子不放苹果,摆放方式就是把i 个苹果放在j-1个盘子里(摆放方式总数与第一个空盘子无关),摆放方式总数表示为dp[i][j-1]
      2、每个盘子都放苹果,因为苹果数=盘子数,所以刚好每个盘子一个苹果,只有一种摆放方式
      故当盘子数等于苹果数的代码为:dp[i][j]=1+dp[i][j-1];

    再系统说下本题,及需要注意的点:

    dp[a][b]

    表示把a 个苹果放入b 个盘子的摆放方式总数,允许有的盘子不放苹果,画一个类似棋盘的表格,例如第一行第五列的小格,表示把五个苹果放在1个盘子里,小格里面填写对应的摆放方式的总数;需要注意的点:

    • 动态规划的第一个难点是,设置递推公式的初始状态。很好理解,如果斐波那契数列不给出数列的第一个数和第二个数,这个数列的其余的数不能根据递推公式计算出来
      这个题,设置初始状态的语句对应的是
      dp[1][j]=dp[i][1]=1;这个循环
    • 动态规划的第二个难点是,让dp数组的下标还有数组元素的值分别表示什么意义
      这道题里,就是:dp[a][b]表示把a 个苹果放入b 个盘子的摆放方式总数,允许有的盘子不放苹果
    • 第三个难点找到递归关系(不要落情况)
      代码如下:
    #include<stdio.h>
    int dp[121][121];
    int main()
    {
        int i,j;
         int n;
        for (i=1;i<=121;i++)
        dp[1][i]=dp[i][1]=1;
        for (i=2;i<121;i++)
        {
            for (j=2;j<=121;j++)
            {
                if (i<j)
                dp[i][j]=dp[i][i];
                else if (i==j)
                dp[i][j]=1+dp[i][j-1];
                else if (i>j)
                dp[i][j]=dp[i-j][j]+dp[i][j-1];
            }
        }
    
        while( scanf("%d",&n)!= EOF )
        {
              printf( "%d\n" , dp[n][n]);
        }
          return 0;
    }
    
    展开全文
  • 最近接触的感觉比较有难度的算法题有一部分可以用递归来解决,今天来总结一下近期对递归的学习总结。 一,递归的存在意义 为何在我们需要递归? 通俗的讲,就是有些有些问题,看似很庞大,但其实可以将它分解为许多...
  • 二叉树高度相关的算法题,主要是用递归算法来求解。关于树的高度,主要有以下几种题目。在线oj地址:1.二叉树的最大深度-leetcode1042.二叉树的最小深度 -leetcode1111.二叉树的最大深度思路:遍历二叉树,二叉树的...
  • 必会的算法题

    2021-02-03 11:15:03
    必会的算法题 1.关于数组和链表的几个必知必会的代码实现 数组 实现一个支持动态扩容的数组 实现一个大小固定的有序数组,支持动态增删改操作 实现两个有序数组合并为一个有序数组 链表 实现单链表、循环链表、...
  • 快速排序相关算法题

    千次阅读 2016-05-03 00:10:48
    快速排序相关算法题 标签(空格分隔): 排序 java 快排 算法 ...最近在做各个公司笔试 ,比如阿里,腾讯,cvte等等,经常会遇到关于快速排序各种算法题,包括时间复杂度,空间复杂度分析与计算等等...
  • 这次整理关于字符全排列递归算法题 将一串数字全排列,那么如果我们按从小到大的顺序来排列,也不会漏掉其中任意一个了。 以最小值为起点,找到比当前值更大的值里面最小值,如此反复操...
  • 最小K个数: 法一:  用改装快速排序,分割函数不变。  分割后返回标号index若等于k-1或k则退出,  大于k,则递归左侧  小于k,则递归右侧  此法复杂度为O(n),但会移动原始数据
  • 码农有道码农有道高质量技术文章目录整理(请戳我)关于码农有道(请戳我)可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,...
  • 在写这篇文章之前,xxx已经写过了几篇关于改数组元素主题文章,想要了解朋友可以去翻一下之前文章 最小K个数: 法一: 用改装快速排序,分割函数不变。 分割后返回标号index若等于k-1或k则退出, ...
  • 重复题目: 输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有...我在文章中也对其做了总结,并对线性时间的算法做了自己的证明,这里重复如下(其实后面的递归式...
  • 这里有三种方法可以从递归方程得到算法的时间复杂度: 代入法 递归树 主方法 代入法 先知道结果,然后想办法证明结果是对,这就是代入法。 但是有两点需要注意: 1.证明时候,要严格按照渐近符号定义证明; 2....
  • 递归基础思想

    2018-05-03 17:56:25
    他在学习时遇到了几道关于递归的,今天简单聊一下关于递归的思路。 上面是朋友发过来的图片,就这几道简单谈一下递归从哪里入手。 先介绍一下递归,百度百科是这样解释的:程序调用自身的编程技巧称为递归...
  • 31-3(关于斐波那契数三个算法) 在已知n情况下,本对计算第n个斐波那契数Fn三种算法的效率进行了比较。 假定两个数加法,减法和乘法代价都是O(1),与数大小无关。 a.证明:基于递归式(3.22)计算Fn...
  • 二叉树高度相关的算法题,主要是用递归算法来求解。关于树的高度,主要有以下几种题目。在线oj地址:1.二叉树的最大深度-leetcode1042.二叉树的最小深度 -leetcode1111.二叉树的最大深度思路:遍历二叉树,二叉树的...
  • 算法经典面试整理(java实现)

    千次阅读 2018-03-12 10:03:59
    以下从Java角度解释面试常见的算法和数据结构:字符串,链表,树,图,排序,递归 vs. 迭代,动态规划,位操作,概率问题,排列组合,以及一些需要寻找规律的题目。 1. 字符串和数组 字符串和数组是最常见的...
  • 1.这是关于题目,一般考查递归算法和树遍历; 2.这是二元查找树,那么其从小到大的顺序就是树前序遍历列表,换句话说,如果题目允许我们重新建立结点,通过前序遍历依次创建一个一个结点,自然就得到了解决...
  • ,大一新生,C语言刚入门,期末项目用C语言编写一个黑白棋AI。 在CSDN上找到不少相关文章,但是发现用C编写很少,并且由于刚接触编程,对哈希置换表等高级数据表示方式还难以理解运用。 根据陈小春《PC...
  • 园子里面试题目盛行,今天看到一个关于“兔子”数量问题,回复很多,但感觉都不得要领,答案也是千奇百怪、五花八门。这里给出我一个写法。题目:一对小兔子一年后长成兔子;一对兔子每半年生一对小兔子。...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 185
精华内容 74
关键字:

关于递归的算法大题