前记:
这世界上总存在着那么一些看似相似但有完全不同的东西,比如雷锋和雷峰塔,玛丽和马里奥,Java和javascript….当年javascript为了抱Java大腿恬不知耻的让自己变成了Java的干儿子,哦,不是应该是跪舔,毕竟都跟了Java的姓了。可如今,javascript来了个咸鱼翻身,几乎要统治web领域,Nodejs,React Native的出现使得javascript在后端和移动端都开始占有了一席之地。
之前已经有同学讲过了递归和动态规划之间的关系。今天,我们就再来温习一遍。简单的讲述一下递归和动态规划的一些题目。今天主要就是它们是如何用JavaScript来实现的!打破常规,不单单是能用C和JAVA来a题。也能让我们这些学习前端的同学好好的使用JS来A题。
递归算法
递归的定义:
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
简单来说:递归算法,是将问题转化为规模缩小的同类问题的子问题,每一个子问题都用一个同样的算法去解决。一般来说,一个递归算法就是函数调用自身去解决它的子问题
递归的特点:
1)递归就是方法里调用自身。
2)在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。
3)递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等,所以一般不提倡用递归算法设计程序。
例题1:
小试牛刀:汉诺塔
"汉诺塔"是印度的一个古老传说,也是程序设计中的经典的递归问题,是一个著名的益智游戏:
题目如下:
塔上有三根柱子和一套直径各不相同的空心圆盘,开始时源柱子上的所有圆盘都按从大到小的顺序排列。目标是通过每一次移动一个圆盘到另一根柱子上,最终把一堆圆盘移动到目标柱子上,过程中不允许把较大的圆盘放置在较小的圆盘上。
规律:
1)n(圆盘个数) == 1
第一次:1号盘 A -> C sum(移动次数) = 1
2)n == 2
第一次:1号盘 A -> B
第二次:2号盘 A -> C
第三次:1号盘 B -> C sum = 3
3)n == 3
第一次:1号盘 A -> C
第二次:2号盘 A -> B
第三次:1号盘 C -> B
第四次:3号盘 A -> C
第五次:1号盘 B -> A
第六次:2号盘 B -> C
第七次:1号盘 A -> C sum = 7
以此类推...
故不难发现规律,移动次数为:sum = 2^n - 1
分析:
把一堆圆盘从一个柱子移动另一根柱子,必要时使用辅助的柱子。可以把它分为三个子问题:
首先,移动一对圆盘中较小的圆盘到辅助柱子上,从而露出下面较大的圆盘,
其次,移动下面的圆盘到目标柱子上
最后,将刚才较小的圆盘从辅助柱子上在移动到目标柱子上
把三个步骤转化为简单数学问题:
(1) 把 n-1个盘子由A 移到 B;
(2) 把 第n个盘子由 A移到 C;
(3) 把n-1个盘子由B 移到 C;
我们创建一个JS函数,当它调用自身的时候,它去处理当前正在处理圆盘之上的圆盘。最后它回一个不存在圆盘去调用,在这种情况下,它不在执行任何操作
下面上JS代码:
/*汉诺塔函数*/ function hanoi(disc,src,aux,dst){ if(disc>0){ hanoi(disc-1,src,dst,aux); console.log(' 移动 '+ disc + ' 号圆盘 ' + ' 从 ' + src + ' 移动到 ' + dst); // hanoi(disc,src,aux,dst); // 栈溢出 hanoi(disc-1,aux,src,dst) } }
例题2:
走楼梯:(问题描述)
楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶或者3阶,计算共有多少种不同的走法?(注意,例如:3阶楼梯4种方法:1. 一步一步一步 2.一步两步 3.三步 4.两步一步)
分析:
这其实就是一个斐波那契数列的一种实现。我们分析的时候,可以转化成小规模的子类问题。当到达指定阶梯的最后一步的时候,可以有三种种情况,一是上一步,二是上两步,三是上三步。所以总的方法是F(n) = F(n-1) + F(n-2) + F(n-3)。然后自然就成了各自的小计算,不断循环下去,直到判断条件的发生。
下面上代码
/*走楼梯问题*/ function getMethods(n) { if (n <= 0) { return 0; } if (n <= 1) { return 1; } if (n <= 2) { return 2; } if (n <= 3) { return 4; } return arguments.callee(n-1) + arguments.callee(n-2) + arguments.callee(n-3); } console.log(getMethods(5));
注意:argument.callee
在函数内部,有两个特殊的对象:arguments 和 this。其中, arguments 的主要用途是保存函数参数, 但这个对象还有一个名叫 callee 的属性,该属性是一个指针,指向拥有这个 arguments 对象的函数。一般来说,它会和匿名函数一起结合来用。但是不建议使用,因为访问 arguments 是个很昂贵的操作,因为它是个很大的对象,每次递归调用时都需要重新创建。影响现代浏览器的性能,还会影响闭包。
例题3:(具有JS特色的递归)
DOM树的递归:(问题描述)
获取一个节点的所有父节点的tagName
比较简单就直接上代码了:
/*DOM树的递归问题*/ var arr = []; function getParent(node) { node = node.parentNode; if (node.tagName) { arr.push(node.tagName); getParent(node); } } getParent(document.getElementById("node")); console.log(arr);
到此呢,递归就告一段落,希望大家能有更深的理解。虽然题目都是最基本的,但是我们通过打断点,能发现这个代码执行的步骤,也理解什么时候该执行什么。便于我们理解吧!
动态规划:
动态规划也是五大常用算法之一(贪婪算法,动态规划,分治算法,回溯,分支限界)。
基本思想:
它的思想就是把一个大的问题进行拆分,细分成一个个小的子问题,且能够从这些小的子问题的解当中推导出原问题的解。同时还需要满足以下两个重要性质才能进行动态规划
-
最优子结构性: 既所拆分的子问题的解是最优解。
-
子问题重叠性质: 既在求解的过程当中,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的解题效率
我认为,上面讲的楼梯问题,也算是动态规划的一种,自底向上,只考虑这0阶楼梯,1阶楼梯,2阶楼梯,3阶楼梯。总方案数都是由,0种方案,1种方案,2种方案,4种方案这四个数字加起来的。话不多说,我们看一个例子吧。
例子1:
最长公共子串:
问题描述:什么是最长公共子串呢?举个简单的例子吧,一个数列S,若分别是两个或多个已知序列的子序列,且是所有符合条件序列中最长的,则S称为已知序列的最长公共子串。
解决方法:
蛮力法:即对S的每一个子序列,检查是否为T的子序列,从而确定它是否为S和T的公共子序列,并且选出最长的公共子序列。指数级别的时间复杂度o(2^n*2^m)n和m代表两个序列的长度。
当然,我们也可以使用动态规划的方法!
动态规划方法的分析:
-
假设两个字符串分别为s和t,
s[i]
和t[j]
分别表示其第i
和第j
个字符(字符顺序从0
开始),再令L[i, j]
表示以s[i]
和t[j]
为结尾的相同子串的最大长度。应该不难递推出L[i, j]
和L[i+1,j+1]
之间的关系,因为两者其实只差s[i+1]
和t[j+1]
这一对字符。若s[i+1]
和t[j+1]
不同,那么L[i+1, j+1]
自然应该是0
,因为任何以它们为结尾的子串都不可能完全相同;而如果s[i+1]
和t[j+1]
相同,那么就只要在以s[i]
和t[j]
结尾的最长相同子串之后分别添上这两个字符即可,这样就可以让长度增加一位。合并上述两种情况,也就得到L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)
这样的关系。最后就是要小心的就是临界位置:如若两个字符串中任何一个是空串,那么最长公共子串的长度只能是
0
;当i
为0
时,L[0,j]
应该是等于L[-1,j-1]
再加上s[0]
和t[j]
提供的值,但L[-1,j-1]
本是无效,但可以视s[-1]
是空字符也就变成了前面一种临界情况,这样就可知L[-1,j-1]==0
,所以L[0,j]=(s[0]==t[j]?1:0)
。对于j
为0
也是一样的,同样可得L[i,0]=(s[i]==t[0]?1:0)
<script type="text/javascript"> /*最长子串*/ var str1="abcdefghijklname123what"; var str2="defghiwhatisyourname"; var L=[];//备忘录 记录L[i][j]最大长度子串L[i][j]=max(L[i-1][j-1]+1,0) getMaxSubStr(); function getMaxSubStr(){ for (var i=0;i<str1.length+1;i++) { L[i]=[]; L[i][0]=0; } for (var j=0;j<str2.length+1;j++ ) { L[0][j]=0; } var max=-1; var x=-1; var y=-1; for (var i=1;i<str1.length+1;i++ ) { for (var j=1;j<str2.length+1;j++ ) { //alert(str1[i-1]+":"+str2[j-1]); if(str1.charAt(i-1)==str2.charAt(j-1)){ L[i][j]=L[i-1][j-1]+1; } else{ L[i][j]=0; } //document.write(L[i][j]); if(L[i][j]>max){ max=L[i][j]; x=i-1; y=j-1; document.write("i="+i+";j="+j+";max="+max+"<br/>"); } } } //输出共同的子串 var str=[]; while(x>=0&&y>=0){ if(str1.charAt(x)==str2.charAt(y)){ str[--max]=str1.charAt(x); x--; y--; } else break; } var str_out=""; for (var i=0;i<str.length;i++ ) { str_out+=str[i]; } document.write(str_out); } </script>到这呢,基本就结束了。
相关推荐
递归回溯算法是一种基于深度优先搜索(DFS)的策略,它适用于解决约束满足问题,如数独。该算法的特点是尝试填充数独格子,并在遇到矛盾时回退到上一步,尝试其他可能的值。以下是对递归回溯算法解决数独的详细步骤...
总的来说,解决LeetCode第931题“下降路径最小和”不仅能提升JavaScript编程技巧,也能深入理解动态规划这一核心算法思想。通过不断练习此类问题,面试者可以增强自己的算法思维和问题解决能力,从而在求职面试中...
根据提供的文件信息,我们可以提炼出关于Java编程语言中使用递归算法输出某个目录下所有文件和子目录列表的知识点。以下是对文件内容的详细...同时,我们也了解了递归算法在不同编程语言中的应用和变形题目的扩展思路。
在IT行业中,尤其是在JavaScript开发领域,LeetCode是一个广泛使用的在线平台,它提供了各种算法题目,帮助开发者提升编程技能,特别是对于准备求职面试的人来说。本压缩包文件“javascript-leetcode面试题解动态...
在算法的世界里,我们通常会遇到几种常见的类型,包括排序算法(如冒泡排序、快速排序、归并排序)、搜索算法(如线性搜索、二分搜索)、图论算法(如深度优先搜索、广度优先搜索)、动态规划问题以及回溯法等。...
在本压缩包中,我们关注的是一个与JavaScript编程、LeetCode面试及动态规划相关的知识点——第416题“分割等和子集”。这是一道经典的算法问题,常见于求职面试,尤其是对于寻找前端开发职位的应聘者。下面将详细...
7. **图论算法**:如Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法等,对于网络优化和路径规划问题十分有用。 8. **位运算**:JavaScript也支持位运算,这在处理二进制数据或优化性能时非常有效,例如在...
本题解将聚焦于LeetCode中的第22题,这是一个关于动态规划的JavaScript实现问题,具体题目是“括号生成”。动态规划是一种解决复杂问题的有效方法,通过将大问题分解为小问题,然后存储这些小问题的解以避免重复计算...
3. 递归算法:理解递归的工作原理,如何定义递归函数,处理边界条件。 4. 回溯策略:学习如何通过回溯来撤销不满足条件的决策,避免无效计算。 5. 题目560——和为K的子数组:掌握解题思路,编写递归与回溯的解决...
在本压缩包中,我们关注的是一个与JavaScript编程、LeetCode面试准备以及动态规划相关的知识点。这涉及到第64题“最小路径和”的解决方案。在LeetCode上,这类问题经常被用来测试候选人的算法和数据结构技能,对于...
### JavaScript 算法知识点详解 #### 1. 快速排序 **知识点解析:** - **快速排序原理**:快速排序是一种高效的排序算法,基于分治思想。它选择一个基准值(pivot),将数组分为两部分:一部分的所有元素都比基准...
总的来说,这个压缩包文件提供的内容可能是对LeetCode第1291题的一个详细的JavaScript解题思路和代码实现,涵盖了递归和回溯算法的应用。如果你正在准备面试,学习并理解这个题解将对你的面试准备大有裨益。同时,...
在JavaScript编程领域,LeetCode是一个非常重要的在线平台,它提供了大量的编程题目,帮助开发者提升算法能力和准备求职面试。本题解主要关注的是LeetCode中的第59题,这是一个关于递归与回溯策略的问题,特别是在...
这份名为"算法竞赛的挑战,总结实现_Python_JavaScript_下载.zip"的压缩包文件很可能包含了针对算法竞赛的实用代码实现、教程资料或者练习题目,旨在帮助参赛者提升在Python和JavaScript上的算法设计与实现能力。...
在JavaScript编程领域,LeetCode是一个非常重要的在线平台,它提供了大量的编程题目,帮助开发者提升算法能力和解决问题的能力。尤其是在求职面试中,LeetCode上的题目经常被用作面试官考察候选人技术实力的标准之一...
LeetCode是一个热门的在线平台,它提供了各种算法题目来帮助开发者提升编程技能和准备求职面试。本篇内容主要聚焦于JavaScript解决LeetCode中的第90题——"子集II"(Subsets II)的递归与回溯算法。 子集II问题要求...
总之,理解和熟练掌握递归与回溯算法对于JavaScript开发者来说至关重要,尤其在解决LeetCode等面试题时。通过解题,不仅可以提升编程技巧,还能锻炼问题解决能力,对于求职面试大有裨益。对于第1219题“黄金矿工”,...
这份“用JavaScript实现的算法和数据结构,附详细解释和刷题指南”是一个全面的学习资源,特别适合正在学习数据结构的大学生。 一、**数组** 数组是最基本的数据结构之一,它是一种线性结构,允许我们存储和访问...
第78题“子集”是LeetCode中的一个经典递归与回溯问题,旨在考察开发者对这两种核心算法的理解和应用。 递归是一种解决问题的方法,它将一个问题分解为更小的子问题,直到子问题变得足够简单可以直接求解。递归通常...
在JavaScript编程领域,LeetCode是一个非常重要的在线平台,它提供了大量的编程题目,旨在帮助开发者提升算法能力和准备求职面试。本题解围绕的是LeetCode中的第54题——螺旋矩阵(Spiral Matrix)。该题目的核心是...