关于leetcode个人解题总结:大厂算法面试之leetcode精讲10递归分治

大厂算法面试之 leetcode 精讲 10. 递归 & 分治

视频教程（高效学习）: 点击学习

目录：

1. 开篇介绍

2. 工夫空间复杂度

3. 动静布局

4. 贪婪

5. 二分查找

6. 深度优先 & 广度优先

7. 双指针

8. 滑动窗口

9. 位运算

10. 递归 & 分治

11 剪枝 & 回溯

12. 堆

13. 枯燥栈

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 double  pow(double  x, 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<Integer,Integer> 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<TreeNode> q = new LinkedList<TreeNode>();
        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;
    }
}