赞
踩
递归和回溯的基本概念:
递归的基本性质是函数调用,处理问题时,把大规模的问题不断的变小然后进行推导的过程。
回溯是利用递归的性质。从问题的起点出发。不断尝试,回头异步甚至多步做选择,知道最终抵达终点的过程。
什么是递归,为什么叫递归?
递归有递有归
我认为递归需要几个要素:
递归终止条件 什么时候停止递,开始归。
递归递的条件 什么时候需要继续往下递。
递归归的表达式(归的时候怎么做才能得到结果)
提取重复的逻辑。缩小问题的规模。
递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决。从程序实现的角度而言,我们需要抽象出一个干净利落的重复的逻辑,以便使用相同的方式解决子问题。
一条包含字母 A-Z 的消息通过以下方式进行了编码:
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。
示例 1:
输入: “12”
输出: 2
解释: 它可以解码为 “AB”(1 2)或者 “L”(12)。
示例 2:
输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
首先找到我们终止递开始归的条件,
当前这个例子,我们需要查找到最后,没有问题才能记一个。
也就是我们终止递开始归的条件是,当前元素已经是最后一个元素。
什么时候需要继续往下递。
当前例子,当我们还没有查找到最后一个元素的时候就需要继续递。
递归归的表达式(归的时候怎么做才能得到结果)
当前例子,我们有两种情况,也就是说当我们当前数字的前一个是1,或者前面是2且当前数字小于6的情况下,我们需要在记一个,然后在往前递,直到最后一个元素,算作一个,
const numDecodings = (s)=> { return decode(s,s.length-1); }; const decode=(strs,i)=>{ if(i<=0 ) return 1;// 递归终止条件 let count=0; let curr=strs[i]; let prev=strs[i-1]; if(curr>'0'){// 没有到末尾继续递 这个为O(n) count=decode(strs,i-1); } if (prev == '1' || (prev == '2' && curr <= '6')) { count += decode(strs,i- 2); //这个为O(n-2) // 在归的途中途中,发现有满足条件的,需要做处理, } return count; }
尝试时间复杂度方面的分析:
有两种分支:
回溯算法是一种试探算法。每一步都有多种尝试的可能性,是递归算法的变式,递归和回溯的区别我认为在于,在归的途中做的事情不一样,递归的每一次归都是确切的答案,而回溯的话,在归的时候。每一步都可能有多种尝试的可能。
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
找到停止递开始归的条件
当target减去元素的值小于-1的时候,说明这些元素的和大于了target,这样的组合不是正确的,开始归。
归的时候做的事情
每次归的时候都需要去查找还有没有别的组合 可以得到结果,所有的都需要去尝试,在递到末尾的时候,得到正确的组合之后,就推送到结果组里面了。target-元素-元素=0,说明组合元素是正确的。
什么时候需要继续递
在这个例子中,递的条件就是没有得到正确的组合以及值没有超出边界,就需要继续往下递。
const combinationSum = (candidates, target)=> { let result=[]; let solution=[]; let length=candidates.length; const backTracking=(target,solution,start)=>{ if(target<0) return;// 每次递下去,都需要对其的值进行判断 if(target===0) { // 得到相等的,推送结果组合。开始归。 result.push(solution); return; } for(let i=start;i<length;i++){ solution.push(candidates[i]);// 将当前的值推送进数组 backTracking(target-candidates[i],solution.slice(),i);// 递下去,target以及减去了一个元素的值,递下之后满足条件归,不满足条件继续递。 solution.pop(); } } backTracking(target,solution,0); return result; };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。