递归
- 递归，将问题分解为重叠的子问题，f(n)=f(n-1)+xxx,满足这样的状态转移方程，说明原问题是不是依赖递归子问题，即f(n)依赖f(n-1)
- 确定递归出口
- 递归返回时还原现场
78. 子集(模板题)
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
完整代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
// 对于子集，其实就是每个元素选不选的问题
// 0 不选
// 1 选
// 对于[1,2,3]
// 0 0 0 []
// [0,1],[0,1],[0,1]
// let index=0
var res1=[]
let temp=[]
// 不管当前元素选或者不选，是不是都要走到下一层
const findSubSet=(temp,index)=>{
// console.log(temp,index)
if(index===nums.length){
console.log(temp,index)
res1.push(Array.from(temp))
return
}
// 不选
findSubSet(temp,index+1)
// 选
temp.push(nums[index])
findSubSet(temp,index+1)
temp.pop()
}
findSubSet(temp,0)
return res1
};
- 注意点：
- 选或者不选其实是一个背包问题，即背包容量有限的情况下，如何取舍不同的物品
77. 组合(上题的特例)
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 201 <= k <= n
解题思路
1.还是子集问题，不过子集的个数有限制，为k
完整代码
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
let s=[]
let res=[]
const findSubSet=(index)=>{
// 去除不满满足条件的
if(s.length>k||s.length+n-index+1<k){
// 说明子集长度大于k，或者子集的长度+后面的层数都不足以达到k
return
}
// 递归出口
if(index===n+1){
res.push(Array.from(s))
return
}
// 对于每一个index，选或者不选
// 不选
findSubSet(index+1)
// 选
s.push(index)
findSubSet(index+1)
s.pop(index)
}
findSubSet(1)
return res
};
46. 全排列(模板题)
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
解题思路
1. 递归+visited数组，
2. 每次都选，没有不选的选项
3. 选择是有限制，已经选过的不能在选择
完整代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
// 1，2，3 的排列，如果不考虑重复的元素 总数为3*3*3
// 因为不能出现重复的元素，所以会出现死路（不符合条件）和生路（符合条）两种
// 对于这种路很多的情况，一般需要使用递归来解决
let res=[]
// 定义一个递归的算法
// let path=[]
const backTrack=(path)=>{
// 判断n是否已经在数组中
if(path.length===nums.length){
// console.log(2)
res.push(path)
return
}
nums.forEach((item)=>{
// 每个都选
// 选择条件限制，选过的不能在再选
if(path.includes(item)){
// console.log(1,n)
return
}
backTrack(path.concat(item))
})
}
backTrack([])
return res
};
47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
解题思路
1. 和全排列一样
2. 添加了更多的限制条件==> 不能出现重复的排列（因为元素可以相同）
3. 解决方法:使用hash表保证排列的唯一
完整代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
// 先全排列排出来
// 我们存一个map
// key = “1,1,2" 如果key相同，即has(key) 越过
// 这里三个元素必选，没有不选的选项
let res=[]
let map=new Map()
let visited=[]
const allSort=(temp,visitedArr)=>{
if(temp.length===nums.length){
// console.log(temp)
// 判断temp键是否存在
if(!map.has(temp.join(","))){
map.set(temp.join(","),Array.from(temp))
}
return
}
nums.forEach((item,index)=>{
if(!visitedArr.includes(index)){
allSort(temp.concat(item),visitedArr.concat(index))
}
// console.log(index)
})
}
allSort([],visited)
map.forEach(item=>{
res.push(item)
})
return res
};
98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 1
解题思路
1. 判断一棵树是否有效===>判断其左右子树是否有效
2. 有效的条件
左子树中的最大值小于根节点的值
右子树的最小值大于根节点的值
完整代码
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
// 定义一个数据结构，存储节点数是否有效，即这棵树的最大值和最小值
function NodeInfo(){
this.isValid=false
this.maxValue=-Infinity
this.minValue=Infinity
}
var isValidBST = function(root) {
// 有效的判定
// 1. 节点的左子树的最大值left.maxValue>root.val
// 2. 节点的右子树的最小值right.minValue<root.val
// 3. 所有左子树和右子树自身必须也是二叉搜索树
// 定义一个判断子树节点是否满足条件的函数
const checkValid=(root)=>{
// 说明节点为空，空节点肯定有效
if(!root){
let nodeInfo=new NodeInfo()
nodeInfo.isValid=true
return nodeInfo
}
let nodeInfo=new NodeInfo()
let leftNode=checkValid(root.left)
let rightNode=checkValid(root.right)
if(leftNode.isValid&&rightNode.isValid&&leftNode.maxValue<root.val&&rightNode.minValue>root.val){
nodeInfo.isValid=true
}
nodeInfo.minValue=Math.min(Math.min(leftNode.minValue,rightNode.minValue),root.val)
nodeInfo.maxValue=Math.max(Math.max(leftNode.maxValue,rightNode.maxValue),root.val)
return nodeInfo
}
let res=checkValid(root)
console.log(res.isValid)
return res.isValid
};
50. Pow(x, n)
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1-104 <= xn <= 104
完整代码
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
// n为偶数时 pow(x,n) pow(x,n/2) *pow(x,n/2)
// n为奇数时 pow(x,n) pow(x,n/2)*pow(x,n/2)*x
// 递归出口 n=0 时 1
// n<0为负数是 pow(x,n) = 1/pow(x,-n)
console.log(n)
if(n===0){
return 1
}
if(n<0){
return 1/myPow(x,-n)
}
let temp=myPow(x,Math.floor(n/2))
if(n%2===0){
return temp*temp
}else if(n%2===1){
return temp*temp*x
}
};
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
解题思路
1. 括号的组合类型，其实实际情况就两种
2. 即（）里面套() ,或者()()()....
3. 我们把括号组合的问题分为两个子问题
一个问题为外层有括号 (a)
一个问题为外层没有括号 b===()()()...
完整代码
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
// 递归出口
if(n===0){
return [""]
}
// 分治解决
// 我们把整体的大括号分为a，b两个子问题
// a 为括号里面内嵌括号的类型 即( a ) 其中a为括号组合，也可分为a,b子问题
// b 为单独括号类型，即()*n n>=0 如() ()() ()()()
// 这么分解，a的外层必定右括号,所有括号个数 1~n
// 类型组合
let result=[]
for(let i=1;i<=n;i++){
// a类型
// 因为外层括号算一层
let result_a=generateParenthesis(i-1)
// b类型
let result_b=generateParenthesis(n-i)
for(let a of result_a){
for(let b of result_b){
result.push("("+a+")"+b)
}
}
}
return result
};