递归三要素
- 递归函数以及参数
- 递归终止条件
- 递归单层搜寻逻辑
递归伪代码模版：
function recursion(level, param1, param2, ...) { //递归终止条件 if (level > MAX_LEVEL) { // output result return; } //解决以后层 process_data(level, data, ...); //进入下一层 recursion(level + 1, p1, ...); //重置状态 reverse_state(level);}什么是分治：
分治会将大问题拆解成小问题，拆解到最小问题之后，开始一直合并后果，递归是分治实现的一种模式或者是分治实现的一部分，分治包含三分局部，合成、计算、合并。分治的场景很多，例如疾速排序，归并排序。
分治伪代码模版：
function divide_conquer(problem, param1, param2, ...){ if(problem === null){ // return result } //宰割问题 subproblem = split_problem(problem, data) //计算子问题 subResult1 = divide_conquer(subproblem[0], p1, ...) subResult2 = divide_conquer(subproblem[1], p1, ...) subResult3 = divide_conquer(subproblem[2], p1, ...) ... result = process_resule(subResult1, subResult2, subResult3,...)}举例
计算n! n! = 1 * 2 * 3... * n
function factorial(n) { if (n <= 1) return 1; return n * factorial(n - 1);}factorial(6);6 * factorial(5);6 * 5 * factorial(4);//...6 * 5 * 4 * 3 * 2 * factorial(1);6 * 5 * 4 * 3 * 2 * 1;6 * 5 * 4 * 3 * 2;//...6 * 120;720;斐波那契数列，F(n)=F(n-1)+F(n+2)
function fib(n) { if (n === 0 || n === 1) { return n; } return fib(n - 1) + fib(n - 2);}53. 最大子序和 （easy）
给你一个整数数组 nums ，请你找出一个具备最大和的间断子数组（子数组起码蕴含一个元素），返回其最大和。
子数组 是数组中的一个间断局部。
示例 1：
输出：nums = [-2,1,-3,4,-1,2,1,-5,4]
输入：6
解释：间断子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：输出：nums = [1]
输入：1
示例 3：输出：nums = [5,4,-1,7,8]
输入：23提醒：
1 <= nums.length <= 105
-104 <= nums[i] <= 104进阶：如果你曾经实现复杂度为 O(n) 的解法，尝试应用更为精妙的 分治法 求解。
办法1:动静布局
- 思路：以后最大子序和只和后面的子序和相干，循环数组，不断更新最大子序和
- 复杂度：工夫复杂度
O(n)，空间复杂度O(1)
js：
var maxSubArray = function(nums) { const dp = []; let res = (dp[0] = nums[0]);//初始化状态 for (let i = 1; i < nums.length; ++i) { dp[i] = nums[i]; if (dp[i - 1] > 0) {//后面的状态是负数 则加上 dp[i] += dp[i - 1]; } res = Math.max(res, dp[i]);//更新最大值 } return res;};//状态压缩var maxSubArray = function(nums) { let pre = 0, maxAns = nums[0]; nums.forEach((x) => { pre = Math.max(pre + x, x); maxAns = Math.max(maxAns, pre); }); return maxAns;};办法2.分治
- 思路：一直宰割，直到每个局部是一个数字为止，而后一直合并，返回左右和左右合并之后，3个最大子序和中的最大的一个
- 复杂度：工夫复杂度
O(nlogn)，二分复杂度O(logn)，二分之后每一层统计左右和合并之后的最大子序和复杂度是O(n)，所以之后的复杂度是O(nlogn)。空间复杂度O(logn)，递归的栈空间，因为是二分，每次数据规模减半
js：
function crossSum(nums, left, right, mid) { if (left === right) {//左右相等 返回右边的值 return nums[left]; } let leftMaxSum = Number.MIN_SAFE_INTEGER;//右边最大值初始化 let leftSum = 0; for (let i = mid; i >= left; --i) { leftSum += nums[i]; leftMaxSum = Math.max(leftMaxSum, leftSum);//更新右边最大子序和 } let rightMaxSum = Number.MIN_SAFE_INTEGER; let rightSum = 0; for (let i = mid + 1; i <= right; ++i) { rightSum += nums[i]; rightMaxSum = Math.max(rightMaxSum, rightSum);//更新左边最大子序和 } return leftMaxSum + rightMaxSum;//返回左右合并之后的最大子序和}function _maxSubArray(nums, left, right) { if (left === right) {//递归终止条件 return nums[left]; } const mid = Math.floor((left + right) / 2); const lsum = _maxSubArray(nums, left, mid);//右边最大子序和 const rsum = _maxSubArray(nums, mid + 1, right);//左边最大子序和 const cross = crossSum(nums, left, right, mid);//合并左右的之后的最大子序和 return Math.max(lsum, rsum, cross);//返回3中子序和中最大的}var maxSubArray = function(nums) { return _maxSubArray(nums, 0, nums.length - 1);};50. Pow(x, n) (medium)
实现 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
办法1：分治
- 思路：当n是偶数的时候，对n进行分治，拆解为
x*x的n/2的次方，当n为奇数的时候拆分成x * myPow(x,n-1),留神当n是正数或者是0的非凡状况 - 复杂度剖析：工夫复杂度：
O(logn)， n是进行二进制拆分的工夫复杂度。空间复杂度：O(logn), n为递归深度
js：
var myPow = function (x, n) { if (n === 0) return 1 // n=0间接返回1 if (n < 0) { //n<0时 x的n次方等于1除以x的-n次方分 return 1 / myPow(x, -n) } if (n % 2) { //n是奇数时 x的n次方 = x*x的n-1次方 return x * myPow(x, n - 1) } return myPow(x * x, n / 2) //n是偶数，应用分治，一分为二，等于x*x的n/2次方 }办法2：二进制
- 思路：对n的二进制一直右挪动，判断n的二进制最初一位是否是1， 如果是1则将后果乘以x。
- 复杂度剖析：工夫复杂度
O(logn)： n为对 n 进行二进制拆分的工夫复杂度，空间复杂度O(1)
js:
var myPow = function (x, n) { if (n < 0) { x = 1 / x; n = -n; } let result = 1; while (n) { if (n & 1) result *= x; //判断n的二进制最初一位是否是1， 如果是1则将后果乘以x x *= x; n >>>= 1; //进行无符号右移1位，此处不能应用有符号右移（>>） //当n为-2^31转换成负数时的二进制位“10000000000000000000000000000000” , //如果采纳有符号右移时会取最左侧的数当符号即（1），所以返回的后果是 -1073741824 /* C++ 中只有一种右移运算符——>>。它的定义如下：移出的低位舍弃； 如果是无符号数，高位补0；如果是有符号数，高位补符号位。 而JavaScript中有两种右移运算符——>>和>>>。其中>>是有符号右移， 即高位补符号位（可能会呈现正数变负数，负数变正数的异常情况）；>>>是无符号右移，高位无脑补0。 */ } return result;}124. 二叉树中的最大门路和 (hard)
门路 被定义为一条从树中任意节点登程，沿父节点-子节点连贯，达到任意节点的序列。同一个节点在一条门路序列中 至少呈现一次 。该门路 至多蕴含一个 节点，且不肯定通过根节点。
门路和 是门路中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大门路和 。
示例 1：
输出：root = [1,2,3]
输入：6
解释：最优门路是 2 -> 1 -> 3 ，门路和为 2 + 1 + 3 = 6
示例 2：输出：root = [-10,9,20,null,null,15,7]
输入：42
解释：最优门路是 15 -> 20 -> 7 ，门路和为 15 + 20 + 7 = 42提醒：
树中节点数目范畴是 [1, 3 * 104]
-1000 <= Node.val <= 1000
办法1.递归
- 思路：从根节点递归，每次递归分为走右边、左边、不动 3种状况，用以后节点加上左右子树最大门路和不断更新最大门路和
- 复杂度：工夫复杂度
O(n)，n为树的节点个数。空间复杂度O(n)，递归深度，最差状况下为数的节点数
js：
const maxPathSum = (root) => { let maxSum = Number.MIN_SAFE_INTEGER;//初始化最大门路和 const dfs = (root) => { if (root == null) {//遍历节点是null 返回0 return 0; } const left = dfs(root.left); //递归左子树最大门路和 const right = dfs(root.right); //递归右子树最大门路和 maxSum = Math.max(maxSum, left + root.val + right); //更新最大值 //返回以后子树的门路和 分为走右边、左边、不动 3种状况 const pathSum = root.val + Math.max(0, left, right); return pathSum < 0 ? 0 : pathSum; }; dfs(root); return maxSum; };169. 少数元素（easy）
给定一个大小为 n 的数组 nums ，返回其中的少数元素。少数元素是指在数组中呈现次数 大于 ⌊ n/2 ⌋ 的元素。
你能够假如数组是非空的，并且给定的数组总是存在少数元素。
示例 1：
输出：nums = [3,2,3]
输入：3
示例 2：输出：nums = [2,2,1,1,1,2,2]
输入：2提醒：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109进阶：尝试设计工夫复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
办法1.排序
- 思路：排序数组，如果有一个数字呈现的频率大于
n/2，则在数组nums.length / 2的地位就是这个数 - 复杂度剖析：工夫复杂度：
O(nlogn)，快排的工夫复杂度。空间复杂度：O(logn)，排序须要logn的空间复杂度
js：
var majorityElement = function (nums) { nums.sort((a, b) => a - b); return nums[Math.floor(nums.length / 2)];};办法2.哈希表
- 思路：循环数组，用哈希表存储数字和对应的个数，如果数字呈现的个数大于
n/2则返回这个数 - 复杂度剖析：工夫复杂度：
O(n)，n为nums数组的长度。空间复杂度：O(n），哈希表须要的空间
js:
var majorityElement = function (nums) { let half = nums.length / 2; let obj = {}; for (let num of nums) { obj[num] = (obj[num] || 0) + 1; if (obj[num] > half) return num; }};办法3:对消
js：
//[1,1,2,2,2]const majorityElement = nums => { let count = 1; let majority = nums[0]; for (let i = 1; i < nums.length; i++) { if (count === 0) { majority = nums[i]; } if (nums[i] === majority) { count++; } else { count--; } } return majority;};办法4.分治
- 思路：一直从数组的两头进行递归宰割，直到每个区间的个数是1，而后向上合并左右区间个数较多的数，向上返回。
- 复杂度剖析：工夫复杂度：
O(nlogn)，一直二分，复杂度是logn，二分之后每个区间须要线性统计left与right的个数，复杂度是n。空间复杂度：O(logn)，递归栈的耗费，一直二分。
Js:
var majorityElement = function (nums) { const getCount = (num, lo, hi) => {//统计lo到hi之间num的数量 let count = 0; for (let i = lo; i <= hi; i++) { if (nums[i] === num) count++; } return count; }; const getMode = (lo, hi) => { if (lo === hi) return nums[lo]; //拆分成更小的区间 let mid = Math.floor((lo + hi) / 2); let left = getMode(lo, mid); let right = getMode(mid + 1, hi); if (left === right) return left; let leftCount = getCount(left, lo, hi);//统计区间内left的个数 let rightCount = getCount(right, lo, hi);//统计区间内right的个数 return leftCount > rightCount ? left : right;//返回left和right中个数多的那个 }; return getMode(0, nums.length - 1);};938. 二叉搜寻树的范畴和 (easy)
给定二叉搜寻树的根结点 root，返回值位于范畴 [low, high] 之间的所有结点的值的和。
示例 1：
输出：root = [10,5,15,3,7,null,18], low = 7, high = 15
输入：32
示例 2：输出：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输入：23提醒：
树中节点数目在范畴 [1, 2 * 104] 内
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不雷同
办法1:dfs
- 复杂度：工夫复杂度
O(n)，空间复杂度O(n)
js:
var rangeSumBST = function(root, low, high) { if (!root) { return 0; } if (root.val > high) { return rangeSumBST(root.left, low, high); } if (root.val < low) { return rangeSumBST(root.right, low, high); } return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);};办法2:bfs
- 复杂度：工夫复杂度
O(n)，空间复杂度O(n)
js：
var rangeSumBST = function(root, low, high) { let sum = 0; const q = [root]; while (q.length) { const node = q.shift(); if (!node) { continue; } if (node.val > high) { q.push(node.left); } else if (node.val < low) { q.push(node.right); } else { sum += node.val; q.push(node.left); q.push(node.right); } } return sum;};视频解说：传送门