算法-基础算法

一、枚举算法

也称为穷举算法，指的是按照问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，将它们逐一与目标状态进行比较以得出满足问题要求的解。在列举的过程中，既不能遗漏也不能重复

1. 问题

公鸡一只五块钱，母鸡一只三块钱，小鸡三只一块钱。现在我们用 100 块钱买了 100 只鸡，问公鸡、母鸡、小鸡各买了多少只。

2. 思路

1. 确定枚举对象：枚举对象为公鸡、母鸡、小鸡的只数，那么我们可以用变量 x、y、z 分别来代表公鸡、母鸡、小鸡的只数。
2. 确定枚举范围：因为总共买了 100 只鸡，所以 0 ≤ x, y ,z ≤ 100，则 x、y、z 的枚举范围为 [0,100]。
3. 确定判断条件：根据题意，我们可以列出两个方程式：5*× + 3*y + 3/z=100 =100，x+y+z=100。在枚举 x、y、z 的过程中，我们可以根据这两个方程式来判断是否当前状态是否满足题意.

3. 代码

function buyChicken() {for (let x = 0; x <= 20; x++) { // 遍历公鸡数量，最多 20 只for (let y = 0; y <= 33; y++) { // 遍历母鸡数量，最多 33 只const z = 100 - x - y; // 计算小鸡数量// 检查条件：总数为 100 只鸡，价格为 100 元if (z % 3 === 0 && 5 * x + 3 * y + z / 3 === 100) {console.log(`公鸡 ${x} 只，母鸡 ${y} 只，小鸡 ${z} 只`);}}}
}// 调用函数解决鸡的购买问题
buyChicken();

二、递归算法

指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中，可以通过在函数中再次调用函数自身的方式来实现递归。

1. 问题

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

2. 代码

function fib(n) {if (n === 0) {return 0; // 基本情况：第 0 项为 0}if (n === 1) {return 1; // 基本情况：第 1 项为 1}return fib(n - 1) + fib(n - 2); // 递归调用，计算第 n 项
}// 示例用法
const n = 10; // 要计算的斐波那契数列的项数
const result = fib(n); // 计算第 n 项的值
console.log(`斐波那契数列的第 ${n} 项是 ${result}`);

三、分治算法

字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并

1. 问题

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1] 输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]

2. 代码

class Solution {// 合并两个已排序的数组merge(leftArr, rightArr) {const arr = [];while (leftArr.length && rightArr.length) {if (leftArr[0] <= rightArr[0]) {arr.push(leftArr.shift()); // 将左数组的第一个元素移入结果数组} else {arr.push(rightArr.shift()); // 将右数组的第一个元素移入结果数组}}return arr.concat(leftArr, rightArr); // 合并左右数组并返回}// 递归实现归并排序mergeSort(arr) {if (arr.length <= 1) {return arr; // 基本情况：如果数组长度小于等于 1，直接返回}const middle = Math.floor(arr.length / 2);const leftArr = arr.slice(0, middle); // 分成左半部分const rightArr = arr.slice(middle); // 分成右半部分// 递归调用排序左右部分，然后合并结果return this.merge(this.mergeSort(leftArr), this.mergeSort(rightArr));}// 入口点，用于对给定数组进行排序sortArray(nums) {return this.mergeSort(nums);}
}// 示例用法
const solution = new Solution();
const nums = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = solution.sortArray(nums);
console.log(sortedArray);

四、回溯算法

一种能避免不必要搜索的穷举式的搜索算法。采用试错的思想，在搜索尝试过程中寻找问题的解，当探索到某一步时，发现原先的选择并不满足求解条件，或者还需要满足更多求解条件时，就退回一步（回溯）重新选择，这种走不通就退回再走的技术称为「回溯法」，而满足回溯条件的某个状态的点称为「回溯点」

1. 问题

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0] 输出：[[],[0]]

2. 思路

明确所有选择：根据数组中每个位置上的元素选与不选两种选择，画出决策树，如下图所示

明确终止条件：

• 当遍历到决策树的叶子节点时，就终止了。即当前路径搜索到末尾时，递归终止

3. 代码

class Solution {subsets(nums) {const res = []; // 存放所有符合条件的结果集合const path = []; // 存放当前符合条件的结果function backtracking(index) {res.push([...path]); // 将当前符合条件的结果放入集合中for (let i = index; i < nums.length; i++) {path.push(nums[i]); // 选择元素backtracking(i + 1); // 递归搜索path.pop(); // 撤销选择}}backtracking(0);return res;}
}// 示例用法
const solution = new Solution();
const nums = [1, 2, 3];
const result = solution.subsets(nums);
console.log(result);

五、贪心算法

一种在每次决策时，总是采取在当前状态下的最好选择，从而希望导致结果是最好或最优的算法

贪心算法是一种改进的「分步解决算法」，其核心思想是：将求解过程分成「若干个步骤」，然后根据题意选择一种「度量标准」，每个步骤都应用「贪心原则」，选取当前状态下「最好 / 最优选择（局部最优解）」，并以此希望最后得出的结果也是「最好 / 最优结果（全局最优解）」。

换句话说，贪心算法不从整体最优上加以考虑，而是一步一步进行，每一步只以当前情况为基础，根据某个优化测度做出局部最优选择，从而省去了为找到最优解要穷举所有可能所必须耗费的大量时间

1. 问题

一位很棒的家长为孩子们分发饼干。对于每个孩子 i，都有一个胃口值 g[i]，即每个小孩希望得到饼干的最小尺寸值。对于每块饼干 j，都有一个尺寸值 s[j]。只有当 s[j] > g[i] 时，我们才能将饼干 j 分配给孩子 i。每个孩子最多只能给一块饼干。

现在给定代表所有孩子胃口值的数组 g 和代表所有饼干尺寸的数组 j。

要求：尽可能满足越多数量的孩子，并求出这个最大数值。

2. 思路

1. 转换问题：将原问题转变为，当胃口最小的孩子选择完满足这个孩子的胃口且尺寸最小的饼干之后，再解决剩下孩子的选择问题（子问题）。
2. 贪心选择性质：对于当前孩子，用尺寸尽可能小的饼干满足这个孩子的胃口。
3. 最优子结构性质：在上面的贪心策略下，当前孩子的贪心选择 + 剩下孩子的子问题最优解，就是全局最优解。也就是说在贪心选择的方案下，能够使得满足胃口的孩子数量达到最大

3. 代码

class Solution {// 解决分发饼干问题的方法findContentChildren(g, s) {// 对孩子的贪心因子列表和饼干的贪心因子列表进行排序g.sort((a, b) => a - b);s.sort((a, b) => a - b);let indexG = 0; // 孩子列表的指针let indexS = 0; // 饼干列表的指针let res = 0; // 用于存放满足条件的孩子数量// 使用双指针法，遍历孩子和饼干列表while (indexG < g.length && indexS < s.length) {if (g[indexG] <= s[indexS]) {res++; // 如果当前饼干满足当前孩子的贪心因子，将孩子数量加 1indexG++; // 孩子指针向后移动indexS++; // 饼干指针向后移动} else {indexS++; // 如果当前饼干不满足当前孩子的贪心因子，尝试下一个饼干}}return res; // 返回满足条件的孩子数量}
}// 示例用法
const solution = new Solution();
const g = [1, 2, 3];
const s = [1, 1];
const contentChildren = solution.findContentChildren(g, s);
console.log(contentChildren);

 ——未完待续——