大厂算法面试之leetcode精讲10.递归&分治 视频教程（高效学习）:点击学习 目录： 1.开篇介绍
2.时间空间复杂度
3.动态规划
4.贪心
5.二分查找
6.深度优先&广度优先
7.双指针
8.滑动窗口
9.位运算
10.递归&分治
11剪枝&回溯
12.堆
13.单调栈
【大厂算法面试之leetcode精讲10.递归&分治】14.排序算法
15.链表
16.set&map
17.栈
18.队列
19.数组
20.字符串
21.树
22.字典树
23.并查集
24.其他类型题
递归三要素

• 递归函数以及参数
• 递归终止条件
• 递归单层搜索逻辑

递归伪代码模版：

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); }

50. Pow(x, n) (medium) 方法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次方 }

Java：

class Solution { public double myPow(double x, int n) { long N = n; return N >= 0 ? pow(x, N) : 1.0 / pow(x, -N); }public doublepow(doublex, long y) { if (y == 0) { return 1.0; } double ret = pow(x, y / 2); return y % 2 == 0 ? ret * ret : ret * ret * x; } }

方法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; }

Java:

class Solution { public double myPow(double x, int n) { if(x == 0.0f) return 0.0d; long b = n; double result = 1.0; if(b < 0) { x = 1 / x; b = -b; } while(b > 0) { if((b & 1) == 1) result *= x; x *= x; b >>= 1; } return result; } }

169. 多数元素（easy） 方法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)]; };

Java:

class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[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; } };

Java:

class Solution { public int majorityElement(int[] nums) { Map obj = new HashMap<>(); for(int num : nums){ obj.put(num, obj.getOrDefault(num, 0) + 1); if(obj.get(num) > nums.length / 2) return num; } return 0; } }

方法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; };

java:

class Solution { public int majorityElement(int[] num) { int majority = num[0]; int count = 1; for (int i = 1; i < num.length; i++) { if (count == 0) { count++; majority = num[i]; } else if (majority == num[i]) { 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); };

Java:

class Solution { private int getCount(int[] nums, int num, int lo, int hi) { int count = 0; for (int i = lo; i <= hi; i++) { if (nums[i] == num) { count++; } } return count; }private int getMode(int[] nums, int lo, int hi) { if (lo == hi) { return nums[lo]; }int mid = (hi - lo) / 2 + lo; int left = getMode(nums, lo, mid); int right = getMode(nums, mid + 1, hi); if (left == right) { return left; }int leftCount = getCount(nums, left, lo, hi); int rightCount = getCount(nums, right, lo, hi); return leftCount > rightCount ? left : right; }public int majorityElement(int[] nums) { return getMode(nums, 0, nums.length - 1); } }

124. 二叉树中的最大路径和 (hard) 方法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; };

java：

class Solution { int maxSum = Integer.MIN_VALUE; public int dfs(TreeNode root){ if (root == null) { return 0; } int left = dfs(root.left); int right = dfs(root.right); maxSum = Math.max(maxSum, left + root.val + right); int pathSum = root.val + Math.max(Math.max(0, left), right); return pathSum < 0 ? 0 : pathSum; }public int maxPathSum(TreeNode root) { dfs(root); return maxSum; } }

53. 最大子序和 （easy）
文章图片

方法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; };

java：

class Solution { public int maxSubArray(int[] nums) { int pre = 0, maxAns = nums[0]; for (int x : nums) { 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); };

java：

public class Solution {public int maxSubArray(int[] nums) { int len = nums.length; if (len == 0) { return 0; } return _maxSubArray(nums, 0, len - 1); }private int crossSum(int[] nums, int left, int mid, int right) { int sum = 0; int leftSum = Integer.MIN_VALUE; for (int i = mid; i >= left; i--) { sum += nums[i]; if (sum > leftSum) { leftSum = sum; } } sum = 0; int rightSum = Integer.MIN_VALUE; for (int i = mid + 1; i <= right; i++) { sum += nums[i]; if (sum > rightSum) { rightSum = sum; } } return leftSum + rightSum; }private int _maxSubArray(int[] nums, int left, int right) { if (left == right) { return nums[left]; } int mid = left + (right - left) / 2; return max3(_maxSubArray(nums, left, mid), _maxSubArray(nums, mid + 1, right), crossSum(nums, left, mid, right)); }private int max3(int num1, int num2, int num3) { return Math.max(num1, Math.max(num2, num3)); } }

938. 二叉搜索树的范围和 (easy) 方法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); };

java:

class Solution { public int rangeSumBST(TreeNode root, int low, int high) { if (root == null) { 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; };

java：

class Solution { public int rangeSumBST(TreeNode root, int low, int high) { int sum = 0; Queue q = new LinkedList(); q.offer(root); while (!q.isEmpty()) { TreeNode node = q.poll(); if (node == null) { continue; } if (node.val > high) { q.offer(node.left); } else if (node.val < low) { q.offer(node.right); } else { sum += node.val; q.offer(node.left); q.offer(node.right); } } return sum; } }

推荐阅读

• 

  11岁女孩跟大人顶嘴不听话怎么办
• 

  琉璃最早出现在什么年代
• 

  射雕英雄传2017百度云哪里有？射雕英雄传2017 百度云资源
• 

  wi-fi|雷神 911MR 游戏本发布：R7-5800H/RTX 3060，首发 6999 元
• 

  华为手机|华为MatePad 11，120Hz高刷全面屏，还有鸿蒙2.0
• 

  鱼腥草煮水煮多久效果最好 鱼腥草煮水要煮几分钟
• 

  桂花不开花是什么原因造成的
• 

  他汀类药物|长期服用他汀类药物，需要做什么检查，多长时间查一次？
• 

  光明农场旅游攻略 光明农场大观园简介
• 

  玩具消毒用什么消毒
• 

  生煎包怎么做才最好吃视频 生煎包怎么做才最好吃
• 

  2020属马犯太岁佩戴什么好 2020属马犯太岁佩戴什么
• 

  科来网络分析系统，科来网络分析系统技术交流版69干什么用
• 

  黄荆生桩的栽培方法，黄荆树桩的栽培技术
• 

  为什么闲鱼刚发布就被拍下了 闲鱼发布一直是不是上架状态
• 

  17期二班+邱睿+第一周第四次作业
• 

  佳能g2800清零软件-佳能G2800打印多少张纸废墨仓就满了？
• 

  尼康d850怎么看照片参数 尼康D850照片浏览
• 

  win7怎么设置屏幕显示和打印效果无色差?
• 

  隶书可以免费商用吗

• PMSJ寻平面设计师之现代(Hyundai）
• 杜月笙的口才
• 画解算法（1.|画解算法：1. 两数之和）
• Guava|Guava RateLimiter与限流算法
• Linux下面如何查看tomcat已经使用多少线程
• 皮夹克
• 解读《摩根集团》（1）
• 绘本与写作
• 一个选择排序算法
• SG平滑轨迹算法的原理和实现