algorithm入门算法中的常见问题

 

二分查找(非递归)

  /**
   * 二分查找(非递归)
   * @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;
}
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

分治算法(汉诺塔)

/**
 * 分治算法:汉诺塔
 */
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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
第1个盘从A -> C
第2个盘从A -> B
第1个盘从C -> B
第3个盘从A -> C
第1个盘从B -> A
第2个盘从B -> C
第1个盘从A -> C
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

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

动态规划(背包问题)

动态规划算法介绍

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

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


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


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

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

经典场景:背包问题(01背包、完全背包)

algorithm入门算法中的常见问题
algorithm入门算法中的常见问题

/**
 * 动态规划算法: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();
        }
    }



}
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

KMP算法(next数组)

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

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

一、暴力匹配算法

算法的思想:

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

 

上一篇:LeetCode 到底怎么刷?GitHub 上多位大厂程序员亲测的高效刷题方式


下一篇:剑指 Offer 22. 链表中倒数第k个节点