递归伪代码模版:
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);
}
给你一个整数数组 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 <= numsi <= 104进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。
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;
};
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);
};
实现 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
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次方
}
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;
}
路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ,返回其 最大路径和 。示例 1:
-> 3 ,路径和为 2 + 1 + 3 = 6 示例 2:42 解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42提示:树中节点数目范围是 1, 3 * 104 -1000 <= Node.val <= 1000
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;
};
给定一个大小为 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 <= numsi <= 109进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(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)];
};
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;
}
};
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;
};
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);
};
给定二叉搜索树的根结点 root,返回值位于范围 low, high 之间的所有结点的值的和。示例 1:
7, high = 15 输出:32 示例 2:low = 6, high = 10 输出:23提示:树中节点数目在范围 1, 2 * 104 内 1 <= Node.val <= 105 1 <= low <= high <= 105 所有 Node.val 互不相同
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);
};
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;
};
视频讲解:传送门
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。