十大常用算法（待更新）

二分查找

二分查找-非递归

1. 二分查找法只适用于从有序的数列中进行查找（比如数字和字母等），将数列排序后再进行查找
2. 二分查找法的运行时间为对数时间O(log ₂ n)，即查找到需要的目标位置最多只需要log₂n步
3. 二分查找也是分治算法的一种体现

代码

package cn.jyc.suanfa;

/**
 * @version: java version 1.8
 * @Author: Jyc
 * @description:
 * @date: 2023-11-06 15:32
 */
public class ErFenChaZhaoSuanFa01 {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 6, 7, 8, 10, 11, 14, 21, 55, 66};
        int tag = 11;
        int result = erFenChaZhao(arr, tag);
        System.out.println("结果为：" + result);
    }

    public static int erFenChaZhao(int[] arr, int target) {
        // 最左边的索引
        int left = 0;
        // 最右边的索引
        int right = arr.length - 1;
        // 左边的索引不能大于右边的索引
        while (left <= right) {
            // 通过将数组的第一个元素位置 left 和最后一个元素位置 right 相加，
            // 再除以2来得到中间索引值的。这种计算方式可能会导致整数溢出，
            // 因为当数组非常大时，left 和 right 的和可能会超过 int 类型的最大值
//            int mid = (left + right) / 2;
            // 通过将数组的第一个元素位置 left 和最后一个元素位置 right 的差值除以2，
            // 再加上 left 来得到中间索引值的。（先减再除最后加）
            // 这种计算方式避免了整数溢出的问题
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return -1;
    }
}

分治算法

1. 分治算法介绍

   1. 分治算法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（快速排序，归并排序），傅里叶变换（快速傅里叶变换）……
   2. 分治算法可以求解的一些经典问题：二分搜索、大整数乘法、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔

2. 分治算法的基本步骤

   分治算法在每一层递归上都有三个步骤：

   1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
   2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
   3. 合并：将各个子问题的解合并为原问题的解

3. 分治算法最佳实践-汉诺塔

4. 汉诺塔传说思路分析

   1. 如果是有一个盘，A->C
   2. 如果我们有N>=2情况，我们总是可以看做两部分盘（最下面的一个盘，上面的所有盘）
      1. 先把最上面的盘A->B
      2. 把最下边的盘A->C
      3. 把B塔的所有盘从B->C

5. 代码

package cn.jyc.suanfa;

/**
 * @version: java version 1.8
 * @Author: Jyc
 * @description: 分治算法-汉诺塔
 * @date: 2023-11-06 16:22
 */
public class HanoiTowerSuanFa02 {
    public static void main(String[] args) {
        hanoiTower(3, 'A', 'B', 'C');
    }

    public static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) { // 只有一个盘子直接从A移动到C
            System.out.println("将第" + num + "个盘子从"+a+"移动到"+c);
        } else { // 若是有多个盘子，思路是将A最下边的盘子放在C的最下边，剩余的先放在B
            // 把剩下的放在B
            hanoiTower(num - 1, a, c, b);
            // 移动最下边的盘子
            System.out.println("将第" + num + "个盘子从"+a+"移动到"+c);
            // 最后再把B上的盘子放在C上
            hanoiTower(num - 1, b, a, c);
        }
    }
}

动态规划

1. 动态规划算法介绍

   1. 动态规划算法的核心思想是：将大问题划分为小问题解决，从而一步步获取最优解的处理算法
   2. 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
   3. 与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的
   4. 动态规划可以通过填表的方式来逐步推进，得到最优解

2. 动态规划算法最佳实践-背包问题

   有一个背包，容量为4磅，现有如下物品

   物品	重量	价格
   吉他（G）	1	1500
   音响（S）	4	3000
   电脑（L）	3	2000

   要求：

   1. 要求达到的目标为装入的背包总价值最大，并且重量不超出
   2. 要求装入的物品不能重复

3. 思路分析

   1. 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大
   2. 其中问题分两种，01背包和完全背包（完全背包指的是：每种物品都有无限件可选）
   3. 这里的问题属于01背包，即每种类物品最多放一个。而无限背包可以转化为01背包
   4. 算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值，公式和解释如下：
      1. w[i]表示第i个商品的重量，v[i]表示第i个商品的价值，j表示当前背包的容量
      2. v[i][0]=v[0][j]=0; //表示填入表第一行和第一列是0
      3. 当w[i]>j时：v[i][j]=v[i-1][j]; //当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
      4. 当j>w[i]时：v[i][j]=max{v[i-1][j],v[i]+v[i-1][j-w[i]]}; // 当准备加入的新增的商品的容量小于等于当前背包的容量（其中max内的参数分两个，比较出最大的一个，赋值给v[i][j]，具体解释：v[i-1][j]：即上一个单元格的装入的最大值（已有的值），v[i-1][j-w[i]]：装入i-1商品，到剩余空间为j-w[i]的最大值

分治算法和动态规划的比较

KMP

贪心算法

普里姆算法

克鲁斯卡尔算法

迪杰斯特拉算法

弗洛伊德算法

马踏棋盘算法

雪花算法