全栈大前端

# 分治

  • 递归的一种细分，问题花解成好几个子问题

  • 结果返回需要组合

# 分治的解题策略

  1. 分解，将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
  2. 解决，解决各个子问题
  3. 合并，将各个子问题的解合并为原问题的解

# 模版

  1. 递归终止条件，没有问题要解决

  2. 处理当前层逻辑

  3. 下探下一层

  4. 组装结果返回（合并子结果）

  5. 清理当前层状态（可选）

# 适用场景

当出现满足以下条件的问题，可以尝试只用分治策略进行求解：

  1. 原始问题可以分成多个相似的子问题
  2. 子问题可以很简单的求解
  3. 原始问题的解是子问题解的合并
  4. 各个子问题是相互独立的，不包含相同的子问题

# 使用分治法求解的一些经典问题

  1. 二分查找
  2. 归并排序
  3. 快速排序
  4. 汉诺塔问题
  5. React 时间分片

# 二分查找

  • 前提条件

  1. 目标函数单调性（单调递增或递减）

  2. 存在上下界

  3. 能够通过索引访问

  • 代码模版
let left ,right = 0

const end= len(array)-1

while(left<=right){
    const mid = (left+right)/2
    if(array[mid]==target){
        // find the target
        break or return result
    }
    else if(array[mid]<target){
        left= mid+1
    }
    else {
        right =mid-1
    }
      
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 高频题

  • 分治

分治

  • 二分查找

# Sqrt(x) 求平方根(简单) (opens new window)

  • 二分查找

  1. 一开始把右边界粗略的设定为目标值 x，左右边界的中间值设为 mid，然后在二分过程中每次发现 mid * mid < x 的情况，就把这个 mid 值记录为 ans。

  2. 如果计算出的乘积正好等于 x，就直接返回这个 mid 值。

  3. 如果二分查找超出边界了，无论最后的边界是停留在小于 x 的位置还是大于 x 的位置，都返回 ans 即可，因为它是最后一个乘积小于 x 的值，一定是正确答案。

let mySqrt =function (x){
    let left = 0;
    let right =x;
    let ans =-1;

    while(left <=right){
        let mid =Math.round((left +right) /2)
        let product = mid*mid;
        if(product <=x){
            ans =mid;
            left =mid +1
        } else if(product >x){
            right =mid -1
        }else{
            return mid
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 二分查找(简单) (opens new window)

//左闭右闭区间
const search =function (nums,target){
    let start = 0;
    let end =nums.length -1
    while(start <= end){
        const mid =start +((end - start)>>1)
        if(nums[mid]===target)return mid
        if(nums[mid]<target){
            start =mid +1
        }else{
            end =mid-1
        }
    }
    return -1
}

// 左闭右开区间
const search =function (nums, target){
    let start =0;
    let end =nums.length
    while(start <end ){
        const mid = start +((end -start)>>1)
        if(nums[mid] ===target ) return mid
        if(nums[mid]<target){
            start =mid+1
        }else{
            end = mid
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 搜索插入位置(简单) (opens new window)

  • 二分查找
const searchInsert =function(nums,target){
    let start = 0;
    let end =nums.length -1
    while(start <=end){
        const mid =start +((end -start) >> 1)
        if(nums[mid] ===target) return mid
        if(nums[mid]<target){
            start = mid+1
        }else{
            end =mid -1
        }
    }
    return start
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 二维数组中查找(中等) (opens new window)

  • 类似二分查找的做法：
  1. 从左下角开始寻找，因为左下角的元素是当前行最小的、当前列表最大的
  2. 比较元素,如果太大了,上移一行
  3. 如果太小了，右移一列
  4. 找到就返回true
  5. 遍历完，返回false
const findNumberIn2DArray= (matrix,target)=>{
    const [m,n] =[matrix.length, matrix[0]?.length];
    if(!m){return false}
    // 定义左下角到坐标
    let [row,col]= [m-1,0];
    // 坐标在矩阵中，就一直寻找
    while(row >= 0 && col <= n-1){
        // 当前元素
        const item = matrix[row]][col];
        if(item === target){
            //找到，返回true
            return true
        } else if(item >target){
            // 太大了，上移一行
            row--;
        } else{
            // 太小了，右移一列
            col++;
        }
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 旋转数组的最小数字(简单) (opens new window)

  • 二分查找
  1. 若mid 大于high 的数,则最小值一定在mid 右侧
  2. 若mid 小于high 的数，则最小值有两种可能：(1) 最小值在mid 最侧(2)mid 就是最小值
  3. 若mid 等于high 的数，high--
  4. 最后返回low 所在数
const minArray =numbers=>{
    let [low ,high] =[0,numbers.length -1];
    while(low <=high){
        const mid =(low + high) >>1;
        if(numbers[mid]>numbers[high]){
            //最小值一定在mid 右侧
            low =mid+1
        } else if(numbers[mid]<numbers[high]){
            //最小值在mid 左侧，或者mid 就是最小值
            high =mid
        }else{
            high-- 
        }
    }
    return numbers[low]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 最大子数组和(简单) (opens new window)

  • 暴力法（超时,不推荐）
function LSS(list){
    const len =list.length;
    let max = -Number.MAX_VALUE;
    let sum = 0;
    for(let i =0; i<len;i++){
        sum =0;
        for(let j = i ;j<len;j++){
            sum +=list[j];
            if(sum > max){
                max =sum
            }
        }
    }
    return max
}
//时间复杂度为 O(N^2)
//空间复杂度为 O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • 分治法
  1. 我们来分析一下这个问题， 我们先把数组平均分成左右两部分。

此时有三种情况：

最大子序列全部在数组左部分 最大子序列全部在数组右部分 最大子序列横跨左右数组 2. 对于前两种情况，我们相当于将原问题转化为了规模更小的同样问题。

  1. 对于第三种情况，由于已知循环的起点（即中点），我们只需要进行一次循环，分别找出 左边和右边的最大子序列即可。

  2. 所以一个思路就是我们每次都对数组分成左右两部分，然后分别计算上面三种情况的最大子序列和， 取出最大的即可。


const LSS=(list)=>{
    return helper(list,0,list.length-1)
}

const helper(list,m,n){
    if(m===n){
        return list[m]
    }
    let sum = 0;
    let lmax = - Number.MAX_VALUE;
    let rmax = - Number.MAX_VALUE;
    const mid =((n-m)>>1) + m;
    const l =helper(list,m,mid);
    const r =helper(list,mid+1,n);
    for(let i =mid; i>=m;i--){
        sum +=list[i];
        if(sum>lmax){
            lmax=sum
        }
    }
    sum =0;
    for(let i =mid+1;i<=n;i++){
        sum += list[i];
        if(sum>rmax){
            rmax=sum
        }
    }
    return Math.max(l,r,lmax+rmax);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  • 动态规划

地推关系式：Q(list, i) = Math.max(0, Q(list, i - 1)) + list[i]

function LSS(list){
    const len =list.length
    let max =list[0];
    for(let i =1;i<len;i++){
        list[i]=Math.max(0,list[i-1]) +list[i]
        if(list[i]>max) max=list[i]
    }
    return max
}
1
2
3
4
5
6
7
8
9

# Pow(x,n)(中等) (opens new window)

  • 二分查找

  1. 用一种快速幂计算的方式，也就是把 x 的 n 次方转化为 x * x 的 n / 2 次方。

  2. 比如求 2 的 10 次方可以转为 4 的 5 次方，这时候遇到奇数次方了，就转化为 4* (4 的 4 次方)。

  3. 然后对于 4 的 4 次方，再进一步转化为 16 的 2 次方，最后转为 256 的 1 次方 * 4，就得出最终解 1024。

const myPow =function (x,n){
    if(n===0) return 1;
    if(n===1) return x;
    let abs =Math.abs(n)
    let isMinus =abs !==n;
    let res =abs % 2 ===0 ?myPow(x*x ,abs/2):x * myPow(x,abs -1)
    return isMinus? 1/res :res
}
1
2
3
4
5
6
7
8
9

# 数组中对逆序对(困难) (opens new window)

  • 分治

  1. 若没了解过归并排序，建议先熟悉归并排序算法再来看本题。

  2. 直接将归并排序进行改进，把数据分成N个小数组。

  3. 合并数组 left - mid , mid+1 - right，合并时， 若array[leftIndex] > array[rightIndex],则比右边 rightIndex-mid个数大

count += rightIndex-mid

  1. 注意和归并排序的区别： 归并排序是合并数组数从小数开始，而本题是从大数开始
function InversePairs(data) {
      return mergeSort(data, 0, data.length - 1, []);
    }

    function mergeSort(array, left, right, temp) {
      if (left < right) {
        const mid = parseInt((left + right) / 2);
        const l = mergeSort(array, left, mid, temp);
        const r = mergeSort(array, mid + 1, right, temp);
        const m = merge(array, left, right, mid, temp);
        return l + m + r;
      } else {
        return 0;
      }
    }

    function merge(array, left, right, mid, temp) {
      let leftIndex = mid;
      let rightIndex = right;
      let tempIndex = right - left;
      let count = 0;
      while (leftIndex >= left && rightIndex > mid) {
        if (array[leftIndex] > array[rightIndex]) {
          count += (rightIndex - mid);
          temp[tempIndex--] = array[leftIndex--];
        } else {
          temp[tempIndex--] = array[rightIndex--];
        }
      }
      while (leftIndex >= left) {
        temp[tempIndex--] = array[leftIndex--];
      }
      while (rightIndex > mid) {
        temp[tempIndex--] = array[rightIndex--];
      }
      tempIndex = 0;
      for (let i = left; i <= right; i++) {
        array[i] = temp[tempIndex++];
      }
      return count;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

← 回溯 →