algorithm入门算法中的常见问题

KMP算法（next数组）

二分查找（非递归）

  /**

   * 二分查找（非递归）

   * @param arr 从小到大的排序数组

   * @param target 目标查找值

   * @return

   */

public static int binarySearch(int[] arr,int target){

    int left = 0;

    int right = arr.length - 1;

    while (left <= right){

        int mid = (left + right )/2;

        if (arr[mid] == target){

            return mid;

        }else if (arr[mid] > target ){

            right = mid - 1;

        }else {

            left = mid + 1;

        }

    }

    return -1;

}

分治算法（汉诺塔）

/**

 * 分治算法：汉诺塔

 */

public class Hannoitower {

    public static void main(String[] args) {

        hannoitower(3,'A','B','C');

    }

    /**

     * 递归汉诺塔

     * @param num 盘得个数

     * @param a 代表 a塔

     * @param b 代表 b塔

     * @param c 代表 c塔

     */

    public static void hannoitower(int num, char a , char b ,char c){

        if (num == 1){

            System.out.println("第1个盘从" + a + " -> " + c);

        }else {

            // 如果n>=2情况，需要将整个塔看作两部分，最上面的整体和最下面的一个盘

            //1.首先，把上面得整体移动到b

            hannoitower(num - 1,a ,c,b);

            //2.其次，把最下面得盘从a移动到c

            System.out.println("第" + num +"个盘从" + a + " -> " + c);

            //3.最后把b塔得所有盘移动到c

            hannoitower(num - 1,b,a,c);

        }

    }

}

第1个盘从A -> C

第2个盘从A -> B

第1个盘从C -> B

第3个盘从A -> C

第1个盘从B -> A

第2个盘从B -> C

第1个盘从A -> C

总结：
分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并：将各个子问题的解合并为原问题的解。

动态规划（背包问题）

动态规划算法介绍

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 (即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )

对比汉诺塔的分治算法，是将大问题分解成小问题，每个小问题独立求解，最后合并就是大问题的解。这是我们在大脑里就可以静态的划分好的。
但是动态规划，每个小问题可能要依赖于上一个问题的解。

动态规划可以通过填表的方式来逐步推进，得到最优解.

经典场景：背包问题（01背包、完全背包）

/**

 * 动态规划算法：01背包问题

 */

public class KnapsackProblem {

    public static void main(String[] args) {

        int[] w = {1,4,3};//物品的重量

        int[] val = {1500,3000,2000}; //物品的价值

        int m = 4;//背包容量

        int n = val.length;// 物品的数目

        //创建二维数组

        int[][] v = new int[n+1][m+1];

        //处理二维数组的第0行第0列，赋值为0

        for (int i = 0; i < v.length; i ++){

            v[i][0] = 0;

        }

        for (int j = 0; j < v.length; j ++){

            v[0][j] = 0;

        }

        //根据规则，填充二维数组

        for (int i = 1; i < v.length ; i ++){

            for (int j = 1; j < v.length; j ++){

                v[i][j] = 1;

            }

        }

        //打印二维数组

        for (int i = 0; i < v.length ; i ++){

            for (int j = 0; j < v.length; j ++){

                System.out.print(v[i][j] + " ");

            }

            System.out.println();

        }

    }

}

KMP算法（next数组）

应用场景：字符串匹配问题

字符串匹配问题：：
有一个字符串 str1= ““硅硅谷尚硅谷你尚硅尚硅谷你尚硅谷你尚硅你好””，和一个子串 str2=“尚硅谷你尚硅你”
现在要判断 str1 是否含有 str2, 如果存在，有就返回子串第一次出现的位置, 如果没有，则返回-1

一、暴力匹配算法

算法的思想：

使用两个下标指示字符串的每个元素，一一进行匹配
如果 i 指向的元素和 j 指向的元素不等，说明匹配失败。回溯 j 得从头再来，i 从下一个元素再次开始。

巴特西

algorithm入门算法中的常见问题

二分查找（非递归）

分治算法（汉诺塔）

动态规划（背包问题）

KMP算法（next数组）

最新文章

热门文章