美文网首页
算法(一)-算法思想

算法(一)-算法思想

作者: Stan_Z | 来源:发表于2019-12-30 22:05 被阅读0次
一、算法思想介绍

常用的算法包含但不限于以下几种:

  • 分治: 分而治之,将问题拆解为形式相同子问题处理,然后合并为原问题解。
  • 穷举: 无差别例举每一种可能解。
  • 迭代: 不断用变量的旧值推出新值。
  • 回溯: 按条件走,走不通就退回重新再走,回溯的核心在递归。
  • 递归: 函数调用自身来处理相同逻辑。
  • 贪心: 将问题拆解为子问题来处理,每一步都先考虑当前最优(贪心)选择。
  • 动态规划:将问题拆解为子问题来处理,整体问题的最优解依赖各个子问题的最优解,自下而上求解,需要记录之前的所有局部最优解。
二、经典案例分析
1)二分查找 (分治)

题干:在一个有序数组中,在不增加空间复杂度的前提下,高效查找目标数。

public static int binarySearch(int[] arr, int target, int low, int high) {
    if (target < arr[low] || target > arr[high] || low > high) {
        return -1;
    }
    int middle = (low + high) / 2;
    if (target < arr[middle]) {
        return binarySearch(arr, target, low, middle);
    } else if (target > arr[middle]) {
        return binarySearch(arr, target, middle, high);
    } else {
        return middle;
    }
}

注:这里用了递归来简化逻辑。

2)鸡兔共笼 (穷举)

题干:一个笼子里关有鸡兔共35头,一共94只脚,笼中鸡兔各有多少只?

public static void exhaustion(int head, int foot) {
    int chicken ;
    int rabbit ;
    for (int i = 0; i <= head; i++) {
       chicken = i;
        rabbit = head - i;
        if (2 * chicken + 4 * rabbit == foot) {
            System.out.println("chicken:" + chicken + "; rabbit:" + rabbit);
        }
    }
}
3)Fibonacci数列 (迭代)

题干:求Fibonacci数列:1、1、2、3、5、8、13、21、34、…… 第N位元素值

public static int iteration(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1 || n == 2) {
        return 1;
    } else if (n > 2) {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    return -1;
}
4)八皇后问题 (回溯)

题干:将八个皇后放在棋盘上,没有任何两个皇后在同一行、同一列或者同一对角线上

static int count = 0;
static int size = 4;
public static void main(String[] args) {
    LinkedList<Location> arr = new LinkedList<>();
    traceBack(arr, 0, 0);
    printResult(arr);
    System.out.println("八皇后共有: " + count + "种摆放方式");
}
static class Location {
    int x;
    int y;
    public Location(int x, int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}
public static void printResult(LinkedList<Location> arr) {
    if (arr.size() == 0) {
        return;
    }
    System.out.println("第" + (count + 1) + "种:");
    for (int i = 0; i < arr.size(); i++) {
        System.out.print(arr.get(i).toString() + "\t");
    }
    System.out.println();
    count++;
}
public static void traceBack(LinkedList<Location> arr, int x, int y) {
    if (arr.size() == size) {
        printResult(arr);
    }
    for (int i = x; i < size; i++) {
        Location location = new Location(i, y);
        if (isOk(arr, location)) {//判断是否满足排列要求,不满足回溯到上一层 判断同行的下一列位置
            arr.offer(location);//保存摆好的皇后
            System.out.println("offer:" + "(" + location.x + ", " + location.y + ")");
            traceBack(arr, 0, y + 1);//开始排下一行的皇后
            arr.pollLast();//当前不满足条件则取消上一次摆放方案,重新摆放
            System.out.println("polllast:" + "(" + location.x + ", " + location.y + ")");
        }
    }
}
public static boolean isOk(LinkedList<Location> arr, Location oriLocation) {
    for (Location loc : arr) {
        if (loc.x == oriLocation.x || loc.y == oriLocation.y) { //同行同列判断
            return false;
        } else if (Math.abs(loc.x - oriLocation.x) == Math.abs(loc.y - oriLocation.y)) {//斜对角线判断
            return false;
        }
    }
    return true;
}
5)剪绳子问题 (贪心与动态规划)

题干:一根长度为n的绳子,请把绳子剪成m段,最终每段绳子长度的乘积最大值是多少?例如,当绳子的长度为8时,我们剪成3,3,2三段,最大乘积是18。
动态规划解:

public static int dp(int len) {
    if (len < 2)
        return 0;
    if (len == 2)
        return 1;
    if (len == 3)
        return 2;
    //子问题的最优解存储在arr数组中,第i个元素表示把长度为i的绳子剪成若干段后各段长度乘积的最大值
    int[] arr = new int[len + 1];
    //这些情况下,不剪的时候长度比剪的时候长,所以作为初始条件
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 3;
    for (int i = 4; i <= len; i++) {
        int max = 0;
        for (int j = 1; j <= i / 2; j++) {
            //动态规划:以上一个子问题的最优解为依据来求下一个子问题的最优解
            int num = arr[j] * arr[i - j];
            System.out.println("i:" + i + " arr[" + j + "] * " + "arr[" + (i - j) + "]" + " " + "num:" + num);
            if (max < num)
                max = num;
        }
        arr[i] = max;
    }
    return arr[len];
}

贪心解:

public static int greedy(int len) {
    /**
     * 先找规律
     * len = 1  1
     *
     * len = 2  1
     * len = 3  2
     *
     * len = 4  2*2 4
     * len = 5  2*3 6
     * len = 6  3*3 9
     * len = 7  3*2*2 12
     * len = 8  3*3*2 18
     * len = 9  3*3*3 27
     * len = 10 3*3*2*2 36
     * ...
     * 从5开始,就由3和2组成,有3尽量满足3,如何最后剩余3和1则转为2*2
     * 贪心:有最优解3,尽量凑成3,最后3*1 的情况特殊考虑转为2*2
     */
    if (len == 1) {
        return 1;
    }
    if (len > 1 && len < 4) {
        return len - 1;
    }
    if (len == 4) {
        return len;
    }
    if (len % 3 == 1) {
        return (int) Math.pow(3, len / 3 - 1) * (int) Math.pow(2, 2);
    } else {
        return (int) Math.pow(3, len / 3) * 2;
    }
}

相关文章

  • 算法总结篇-(1)--算法思想

    算法包括三部分:算法思想 + 排序算法 + 查找算法 算法思想: 算法思想 就是 解题思路。常见的解题思路有如下:...

  • 匈牙利算法

    算法思想 算法流程 算法步骤 算法实现 python 算法应用

  • 算法(一)-算法思想

    一、算法思想介绍 常用的算法包含但不限于以下几种: 分治: 分而治之,将问题拆解为形式相同子问题处理,然后合并为...

  • 第三章:高级排序算法

    归并排序算法(mergeSort) 算法思想:Python使用函数实现: 自底向上的归并排序算法 算法思想:Pyt...

  • 排序算法详解与python实现

    Note:写后感:理解算法思想很重要!理解算法思想很重要!理解算法思想很重要!之后尝试自己独立码代码对算法的理解更...

  • 呕心之作,一篇博客带你精通五大核心算法

    目录 一、分治法 思想原理 具体步骤 例题1 算法结语 二、动态规划算法 思想原理 具体步骤 算法实现 算法结语 ...

  • 数据结构与算法参考书籍

    数据结构与算法分析 算法 算法导论 java编程思想

  • 图的最短路径

    Dijkstra算法&Floyd算法 一、Dijkstra算法 Dijkstra算法思想: 只计算v0出发到其他顶...

  • 第二章:排序基础

    选择排序算法(selectionSort) 算法思想: 算法图示: 使用模板(泛型)编写算法:随机生成算法测试用例...

  • 2018-06-30

    排序算法之归并排序 归并排序算法是排序算法中的经典算法之一,其核心思想是利用归并的思想实现的排序方法,该算法采用经...

网友评论

      本文标题:算法(一)-算法思想

      本文链接:https://www.haomeiwen.com/subject/illvoctx.html