前端必须了解数据结构和算法系列分区 (X)

最编程 2024-05-21 14:47:31

...

1. 什么是分治

分而治之是算法设计中的一种方法。它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。

分而治之算法可以分成三个部分:

(1) 分解原问题为多个子问题（原问题的多个小实例）。
(2) 解决子问题，用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题。
(3) 组合这些子问题的解决方式，得到原问题的解

如下图示例：

与动态规划区别：最优重复性。动态规划。最近重复性，分治，回溯

2. 分治代码模版

js版本

function divide_conquer(problem, params) {
    // 递归终止符 recursion terminator 
    if (problem == null) {
        console.log(result)
        return;
    } 

    // 准备数据 prepare data 
    data = prepare_data(problem) 
    subproblems = split_problem(problem, data) 

    // 解决子问题 conquer subproblems 
    subresult1 = divide_conquer(subproblems[0], p1) 
    subresult2 = divide_conquer(subproblems[1], p1) 
    subresult3 = divide_conquer(subproblems[2], p1) 
    …

    // 处理并生成最终结果 process and generate the final result 
    result = process_result(subresult1, subresult2, subresult3, …)

    // 还原当前级别状态 revert the current level states
}

python版本

def divide_conquer(problem, param1, param2, ...): 
  # recursion terminator 
  if problem is None: 
	print_result 
	return 

  # prepare data 
  data = prepare_data(problem) 
  subproblems = split_problem(problem, data) 

  # conquer subproblems 
  subresult1 = self.divide_conquer(subproblems[0], p1, ...) 
  subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
  subresult3 = self.divide_conquer(subproblems[2], p1, ...) 
  …

  # process and generate the final result 
  result = process_result(subresult1, subresult2, subresult3, …)
	
  # revert the current level states

3. 分治场景

3.1 场景1:归并排序

分: 把数组从中间一分为二。
解: 递归地对两个子数组进行归并排序。
合: 合并有序子数组。

3.2 场景2:快速排序

分: 选基准，按基准把数组分成两个子数组。
解: 递归地对两个子数组进行快速排序。
合: 对两个子数组进行合并。

3.3 场景3: 二分搜索

分：计算 mid 并搜索数组较小或较大的一半。
解：在较小或较大的一半中搜索值。
合：这步不需要，因为我们直接返回了索引值。

function binarySearchRecursive( 
 array, value, low, high
) { 
    if (low <= high) { 
        const mid = Math.floor((low + high) / 2); 
        const element = array[mid]; 
        if (element < value) {
            return binarySearchRecursive(array, value, mid + 1, high); 
        } else if (element > value) {
            return binarySearchRecursive(array, value, low, mid - 1); 
        } else { 
            return mid;
        } 
    } 
    return undefined;
} 

function binarySearch(array, value) { 
    const sortedArray = array.sort((a, b) => a - b); 
    const low = 0; 
    const high = sortedArray.length - 1; 
    return binarySearchRecursive(array, value, low, high); 
}

过程如下图：

4. leetcode常见考题

4.1 easy

1.猜数字大小

难度：简单

题解：二分搜索

2.翻转二叉树

难度：简单

题解：翻转二叉树(分治与迭代)

3.相同的树

难度：简单

题解：相同的树DFS(分治)

4.对称二叉树

难度：简单

题解：对称二叉树(递归法分治，迭代法)

5.多数元素

难度：简单

题解：多数元素(分治)

4.2 medium

1. Pow(x, n)

难度：中等

题解：Pow(x, n)分治

上一篇：数据结构和算法代码实践解析：分区算法

下一篇：分治算法