用javascript分类刷leetcode10.递归&分治(图文视频讲解)

递归三要素

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

递归伪代码模版：

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.length1 <= 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 <= 1051 <= 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;
};

视频讲解：传送门