共计 6911 个字符,预计需要花费 18 分钟才能阅读完成。
递归三要素
- 递归函数以及参数
- 递归终止条件
- 递归单层搜寻逻辑
递归伪代码模版:
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;
};
视频解说:传送门