常见算法思维

常见算法思维：

1. 分治法
2. 迭代法
3. 枚举法
4. 回溯法
5. 贪心法
6. 动态规划

1. 分治法#

英语里面叫做 divide and Conquer

核心思想

将一个复杂的问题分解成多个简单的子问题，递归地求解这些子问题，如果子问题还是比较复杂，那么就继续进行拆分。最后再将所有子问题的解合并成最终解。

核心步骤

1. 分解：将原来的问题分解为多个小问题
2. 求解：递归的解决所有的子问题
3. 合并：将所有子问题的解合并成原来问题的解。

举例：归并排序

归并排序就是典型的使用的是分治的思想：

整个归并排序会经历：

1. 分解：将待排序的数组不断的分成两个部分，直到不能再分解
2. 求解：递归的将两个部分的数组进行归并排序
3. 合并：将两个排序后的数组将其合并为一个排序好的数组

分治法的优缺点

• 优点：简化问题。通过分解一个大问题，将其全部转换为较为简单的子问题，从而易于求解。
• 缺点：往往需要一些额外的空间。空间复杂度一般在 O(n) 左右。分治法往往需要额外的存储空间来存储分解后的子问题。

2. 迭代法#

英语叫做 Iteration

核心思想

重复执行一系列步骤，直到满足某个条件或达到预定目标。每次迭代都在一定程度上修改问题的状态，最终通过不断的更新和计算得到问题的解。

核心步骤

1. 初始化：先设置一个初始值，准备进入迭代。

2. 条件判断：在每次迭代开始之前，需要检查当前状态是否满足结束条件，如果满足结束条件，那么就停止迭代。

3. 更新：需要不停的去更新状态，从而进入下一次迭代。

4. 重复：一直执行迭代

其实，循环就是典型的迭代的思想。

举例：计算递增序列的和

1+2+3+4+ …+ 99+100

let sum = 0
for (let i = 1; i <= 100; i++) {
  sum += i
}

上面的解法，背后采用的就是迭代的思想。

3. 枚举法#

英语叫做 Enumeration

核心思想

列出所有可能的选项，并逐一检查每一个选项，判断是否符合问题的约束条件。

核心步骤

1. 穷举所有可能的解
2. 检查每个解：看每一个解是否符合要求
3. 选择合适的解

举例：力扣第 1 题

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

示例 1

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

示例 2

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3

输入：nums = [3,3], target = 6
输出：[0,1]

这道题大家能够想到的就是枚举的方式，从第一个数开始，和后面的数进行组合，看是否符合要求。

function twoSum(nums, target) {
  // 遍历数组从第一个到倒数第二个
  for (let i = 0; i < nums.length - 1; i++) {
    // 遍历数组从第二个到最后一个
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

const nums = [2, 7, 11, 15]
const target = 9
console.log(twoSum(nums, target))

const nums2 = [3, 2, 4]
const target2 = 6
console.log(twoSum(nums2, target2))

虽然上面的算法也用到了迭代的操作，但是我们迭代是为了枚举出所有的和，迭代仅仅是实现手段，算法背后的核心思想仍然是枚举。

-EOF-