大廠算法面試之leetcode精講10.遞歸&分治
視頻教程（高效學(xué)習(xí)）:點擊學(xué)習(xí)
目錄：
遞歸三要素
- 遞歸函數(shù)以及參數(shù)
- 遞歸終止條件
- 遞歸單層搜索邏輯
遞歸偽代碼模版：
function recursion(level, param1, param2, ...) {
//遞歸終止條件
if (level > MAX_LEVEL) {
// output result
return;
}
//處理當(dāng)前層
process_data(level, data, ...);
//進(jìn)入下一層
recursion(level + 1, p1, ...);
//重置狀態(tài)
reverse_state(level);
}
什么是分治：
分治會將大問題拆解成小問題渴丸，拆解到最小問題之后络拌，開始不斷合并結(jié)果霎终，遞歸是分治實現(xiàn)的一種形式或者是分治實現(xiàn)的一部分漫萄，分治包括三分部分敢订，分解田藐、計算缆八、合并胞谭。分治的場景很多恨溜，例如快速排序符衔，歸并排序。
ds_49
分治偽代碼模版：
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;
斐波那契數(shù)列糟袁，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：分治
ds_66
- 思路：當(dāng)n是偶數(shù)的時候判族，對n進(jìn)行分治，拆解為
x*x的n/2的次方项戴，當(dāng)n為奇數(shù)的時候拆分成x * myPow(x,n-1),注意當(dāng)n是負(fù)數(shù)或者是0的特殊情況 - 復(fù)雜度分析：時間復(fù)雜度：
O(logn)形帮， n是進(jìn)行二進(jìn)制拆分的時間復(fù)雜度≈芏＃空間復(fù)雜度：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是奇數(shù)時 x的n次方 = x*x的n-1次方
return x * myPow(x, n - 1)
}
return myPow(x * x, n / 2) //n是偶數(shù)辩撑，使用分治，一分為二仿耽，等于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：二進(jìn)制
ds_50
- 思路：對n的二進(jìn)制不斷右移動合冀，判斷n的二進(jìn)制最后一位是否是1， 如果是1則將結(jié)果乘以x项贺。
- 復(fù)雜度分析：時間復(fù)雜度
O(logn)： n為對 n 進(jìn)行二進(jìn)制拆分的時間復(fù)雜度君躺，空間復(fù)雜度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的二進(jìn)制最后一位是否是1， 如果是1則將結(jié)果乘以x
x *= x;
n >>>= 1;
//進(jìn)行無符號右移1位开缎，此處不能使用有符號右移（>>）
//當(dāng)n為-2^31轉(zhuǎn)換成正數(shù)時的二進(jìn)制位“10000000000000000000000000000000” ,
//如果采用有符號右移時會取最左側(cè)的數(shù)當(dāng)符號即（1）棕叫，所以返回的結(jié)果是 -1073741824
/*
C++ 中只有一種右移運(yùn)算符——>>。它的定義如下：移出的低位舍棄奕删；
如果是無符號數(shù)俺泣，高位補(bǔ)0；如果是有符號數(shù)完残，高位補(bǔ)符號位砌滞。
而JavaScript中有兩種右移運(yùn)算符——>>和>>>。其中>>是有符號右移坏怪，
即高位補(bǔ)符號位（可能會出現(xiàn)負(fù)數(shù)變正數(shù)贝润，正數(shù)變負(fù)數(shù)的異常情況）；>>>是無符號右移铝宵，高位無腦補(bǔ)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. 多數(shù)元素（easy）
方法1.排序
- 思路：排序數(shù)組华畏，如果有一個數(shù)字出現(xiàn)的頻率大于
n/2，則在數(shù)組nums.length / 2的位置就是這個數(shù) - 復(fù)雜度分析：時間復(fù)雜度：
O(nlogn)尊蚁，快排的時間復(fù)雜度亡笑。空間復(fù)雜度：O(logn)横朋，排序需要logn的空間復(fù)雜度
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.哈希表
- 思路：循環(huán)數(shù)組仑乌，用哈希表存儲數(shù)字和對應(yīng)的個數(shù)，如果數(shù)字出現(xiàn)的個數(shù)大于
n/2則返回這個數(shù) - 復(fù)雜度分析：時間復(fù)雜度：
O(n)琴锭，n為nums數(shù)組的長度晰甚。空間復(fù)雜度：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.分治
ds_51
- 思路：不斷從數(shù)組的中間進(jìn)行遞歸分割厕九，直到每個區(qū)間的個數(shù)是1，然后向上合并左右區(qū)間個數(shù)較多的數(shù)地回，向上返回扁远。
- 復(fù)雜度分析：時間復(fù)雜度：
O(nlogn)，不斷二分刻像，復(fù)雜度是logn畅买，二分之后每個區(qū)間需要線性統(tǒng)計left與right的個數(shù)，復(fù)雜度是n细睡」刃撸空間復(fù)雜度：O(logn)，遞歸棧的消耗纹冤，不斷二分洒宝。
Js:
var majorityElement = function (nums) {
const getCount = (num, lo, hi) => {//統(tǒng)計lo到hi之間num的數(shù)量
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];
//拆分成更小的區(qū)間
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);//統(tǒng)計區(qū)間內(nèi)left的個數(shù)
let rightCount = getCount(right, lo, hi);//統(tǒng)計區(qū)間內(nèi)right的個數(shù)
return leftCount > rightCount ? left : right;//返回left和right中個數(shù)多的那個
};
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.遞歸
ds_107
- 思路：從根節(jié)點遞歸购公，每次遞歸分為走左邊萌京、右邊、不動 3種情況宏浩，用當(dāng)前節(jié)點加上左右子樹最大路徑和不斷更新最大路徑和
- 復(fù)雜度：時間復(fù)雜度
O(n)知残，n為樹的節(jié)點個數(shù)”茸空間復(fù)雜度O(n)求妹，遞歸深度，最差情況下為數(shù)的節(jié)點數(shù)
js：
const maxPathSum = (root) => {
let maxSum = Number.MIN_SAFE_INTEGER;//初始化最大路徑和
const dfs = (root) => {
if (root == null) {//遍歷節(jié)點是null 返回0
return 0;
}
const left = dfs(root.left); //遞歸左子樹最大路徑和
const right = dfs(root.right); //遞歸右子樹最大路徑和
maxSum = Math.max(maxSum, left + root.val + right); //更新最大值
//返回當(dāng)前子樹的路徑和 分為走左邊佳窑、右邊制恍、不動 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）
ds_159
方法1:動態(tài)規(guī)劃
- 思路：當(dāng)前最大子序和只和前面的子序和相關(guān)，循環(huán)數(shù)組神凑，不斷更新最大子序和
- 復(fù)雜度：時間復(fù)雜度
O(n)净神，空間復(fù)雜度O(1)
js：
var maxSubArray = function(nums) {
const dp = [];
let res = (dp[0] = nums[0]);//初始化狀態(tài)
for (let i = 1; i < nums.length; ++i) {
dp[i] = nums[i];
if (dp[i - 1] > 0) {//前面的狀態(tài)是正數(shù) 則加上
dp[i] += dp[i - 1];
}
res = Math.max(res, dp[i]);//更新最大值
}
return res;
};
//狀態(tài)壓縮
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.分治
- 思路：不斷分割何吝，直到每個部分是一個數(shù)字為止，然后不斷合并鹃唯，返回左右和左右合并之后爱榕，3個最大子序和中的最大的一個
- 復(fù)雜度：時間復(fù)雜度
O(nlogn)，二分復(fù)雜度O(logn)坡慌，二分之后每一層統(tǒng)計左右和合并之后的最大子序和復(fù)雜度是O(n)黔酥，所以之后的復(fù)雜度是O(nlogn)『殚伲空間復(fù)雜度O(logn)跪者，遞歸的棧空間梨树，因為是二分坑夯，每次數(shù)據(jù)規(guī)模減半
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
- 復(fù)雜度：時間復(fù)雜度
O(n)，空間復(fù)雜度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
- 復(fù)雜度：時間復(fù)雜度
O(n)抡四，空間復(fù)雜度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;
}
}
