Rubin's Blog

  • 首页
  • 关于作者
  • 隐私政策
享受恬静与美好~~~
分享生活的点点滴滴~~~
  1. 首页
  2. 数据结构和算法
  3. 正文

算法思维

2022年 1月 5日 974点热度 0人点赞 0条评论

贪心算法

概念

贪婪算法(Greedy)的定义:是一种在每一步选中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法

由于贪心算法的高效性以及所求得答案比较接近最优结果,贪心算法可以作为辅助算法或解决一些要求结果不特别精确的问题

注意:当下是最优的,并不一定全局是最优的。举例如下:

有硬币分值为10、9、4若干枚,问如果组成分值18,最少需要多少枚硬币?

采用贪心算法,选择当下硬币分值最大的:10

18-10=8

8/4=2

即:1个10、2个4,共需要3枚硬币

实际上我们知道,选择分值为9的硬币,2枚就够了

18/9=2

如果改成:

有硬币分值为10、5、1若干枚,问如果组成分值16,最少需要多少枚硬币?

采用贪心算法,选择当下硬币分值最大的:10

16-10=6

6-5=1

即:1个10,1个5,1个1 ,共需要3枚硬币

即为最优解

由此可以看出贪心算法适合于一些特殊的情况,如果能用一定是最优解

经典问题:部分背包

背包问题是算法的经典问题,分为部分背包和0-1背包,主要区别如下:

部分背包:某件物品是一堆,可以带走其一部分

0-1背包:对于某件物品,要么被带走(选择了它),要么不被带走(没有选择它),不存在只带走一部分的情况

部分背包问题可以用贪心算法求解,且能够得到最优解

假设一共有N件物品,第 i 件物品的价值为 Vi ,重量为Wi,一个小偷有一个最多只能装下重量为W的背包,他希望带走的物品越有价值越好,可以带走某件物品的一部分,请问:他应该选择哪些物品?

假设背包可容纳50Kg的重量,物品信息如下表:

贪心算法的关键是贪心策略的选择

将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品

按照我们的贪心策略,单位重量的价值排序: 物品A > 物品B > 物品C

因此,我们尽可能地多拿物品A,直到将物品1拿完之后,才去拿物品B,然后是物品C 可以只拿一部分…..

package com.rubin.algorithm.greedy;

public class Goods {

    private String name; //名称
    private double weight; //重量
    private double price; //价格
    private double value; //价值

    public Goods(String name, double weight, double price) {
        this.name = name;
        this.weight = weight;
        this.price = price;
        this.value=price/weight;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    public double getValue() {
        return value;
    }

    public void setValue(double value) {
        this.value = value;
    }

}
package com.rubin.algorithm.greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 背包问题
 * 贪心算法实现
 *
 * 在不考虑排序的前提下,贪心算法只需要一次循环,所以时间复杂度是O(n)
 *
 * 优点:性能高,能用贪心算法解决的往往是最优解
 * 缺点:在实际情况下能用的不多,用贪心算法解的往往不是最好的
 */
public class Bag {

    private double maxWeight;

    public Bag(double maxWeight) {
        this.maxWeight = maxWeight;
    }

    public void take(List<Goods> goods) {
        goods = goods.stream().sorted(Comparator.comparingDouble(Goods::getValue).reversed()).collect(Collectors.toList());
        double sumWeight = 0.00;
        for (Goods good : goods) {
            sumWeight += good.getWeight();
            if (sumWeight < maxWeight) {
                System.out.println(good.getName() + "取" + good.getWeight() + "kg");
            } else {
                System.out.println(good.getName() + "取" + (good.getWeight() - sumWeight + maxWeight) + "kg");
                return;
            }
        }
    }

    public static void main(String[] args) {
        Bag bag = new Bag(50);
        Goods g1 = new Goods("A", 10, 60); //6
        Goods g2 = new Goods("B", 20, 100); //5
        Goods g3 = new Goods("C", 30, 120); //4
        Goods[] goods = {g1, g2, g3}; // 价值倒序
        bag.take(Arrays.asList(goods));
    }

}

时间复杂度

在不考虑排序的前提下,贪心算法只需要一次循环,所以时间复杂度是O(n)

优缺点

优点:性能高,能用贪心算法解决的往往是最优解

缺点:在实际情况下能用的不多,用贪心算法解的往往不是最好的

适用场景

针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大

每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据(局部最优而全局最优)

大部分能用贪心算法解决的问题,贪心算法的正确性都是显而易见的,也不需要严格的数学推导证明

在实际情况下,用贪心算法解决问题的思路,并不总能给出最优解

分治算法

概念

分治算法(divide and conquer)的核心思想其实就是四个字,分而治之 ,也就是将原问题划分成 n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解

关于分治和递归的区别:分治算法是一种处理问题的思想,递归是一种编程技巧

分治算法的递归实现中,每一层递归都会涉及这样三个操作:

  • 分解:将原问题分解成一系列子问题
  • 解决:递归地求解各个子问题,若子问题足够小,则直接求解
  • 合并:将子问题的结果合并成原问题

比如:

将字符串中的小写字母转化为大写字母

“abcde”转化为"ABCDE"

我们可以利用分治的思想将整个字符串转化成一个一个的字符处理

经典问题

求X的n次幂的问题,比如:

2^10 2的10次幂

一般的解法是循环10次

public static int commpow(int x,int n){
    int s=1;
    while(n>=1){
      s*=x;
      n--;
     }
    return s;
}

该方法的时间复杂度是:O(n)

采用分治法

package com.rubin.algorithm.ra;

/**
 * 求x的n次方
 * 使用分治算法来算
 * T = O(logn)
 */
public class HalfPow {

    public static int halfPow(int x, int n) {
        if (n == 1) {
            return x;
        }
        int half = halfPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }

    public static void main(String[] args) {
        System.out.println(halfPow(5, 4));
    }

}

时间复杂度

根据拆分情况可以是O(n)或O(logn)

优缺点

优势:将复杂的问题拆分成简单的子问题,解决更容易,另外根据拆分规则,性能有可能提高

劣势:子问题必须要一样,用相同的方式解决

适用场景

分治算法能解决的问题,一般需要满足下面这几个条件:

  • 原问题与分解成的小问题具有相同的模式
  • 原问题分解成的子问题可以独立求解,子问题之间没有相关性,这一点是分治算法跟动态规划的明显区别
  • 具有分解终止条件,也就是说,当问题足够小时,可以直接求解
  • 可以将子问题合并成原问题,而这个合并操作的复杂度不能太高,否则就起不到减小算法总体复杂度的效果了

回溯算法

概念

回溯算法实际上一个类似枚举的深度优先搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回(也就是递归返回),尝试别的路径

回溯的处理思想,有点类似枚举(列出所有的情况)搜索。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走

经典问题

N皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击

我们把这个问题划分成 8 个阶段,依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中,我们不停地检查当前放法,是否满足要求。如果满足,则跳到下一行继续放置棋子;如果不满足,那就再换一种放法,继续尝试

代码如下:

package com.rubin.algorithm.back;

/**
 * n皇后问题
 * <p>
 * 使用回溯算法
 */
public class NQueen {

    private static final int QUEENS = 8;

    //下标表示行,值表示queen存储在哪一列
    private static final int[] result = new int[QUEENS];

    public static void setQueens(int row) {
        if (row >= QUEENS) {
            print();
            return;
        }
        for (int col = 0; col < QUEENS; col++) {
            if (isOK(row, col)) {
                result[row] = col;
                setQueens(row + 1);
            }
        }
    }

    /**
     * 判断是否OK的标准 同一行上方、左上角、右下角不能有皇后
     *
     * @param row
     * @param col
     * @return
     */
    private static boolean isOK(int row, int col) {
        int leftup = col - 1;//左对角线
        int rightup = col + 1;//右对角线
        for (int i = row - 1; i >= 0 ; i--) {
            if (result[i] == col) {
                return false;
            }
            if (leftup >= 0) {
                if (result[i] == leftup) {
                    return false;
                }
            }
            if (rightup < QUEENS) {
                if (result[i] == rightup) {
                    return false;
                }
            }
            leftup--;
            rightup++;
        }
        return true;
    }

    private static void print() {
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result.length; j++) {
                if (result[i] == j) {
                    System.out.print("Q|");
                } else {
                    System.out.print("*| ");
                }
            }
            System.out.println();
        }
        System.out.println("-------------------");
    }

    public static void main(String[] args) {
        setQueens(0);
    }

}

时间复杂度

N皇后问题的时间复杂度为:O(n!) 实际为 n!/2

优缺点

优点:回溯算法的思想非常简单,大部分情况下,都是用来解决广义的搜索问题,也就是,从一组可能的解中,选择出一个满足要求的解。回溯算法非常适合用递归来实现,在实现的过程中,剪枝操作是提高回溯效率的一种技巧。利用剪枝,我们并不需要穷举搜索所有的情况,从而提高搜索效率

劣势:效率相对于低

适用场景

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题,我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况,然后对比得到最优解。不过,回溯算法的时间复杂度非常高,是指数级别的,只能用来解决小规模数据的问题。对于大规模数据的问题,用回溯算法解决的执行效率就很低了

动态规划

概念

动态规划(Dynamic Programming),是一种分阶段求解的方法

动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决

首先是拆分问题,我的理解就是根据问题的可能性把问题划分成一步一步,这样就可以通过递推或者递归来实现。关键就是这个步骤,动态规划有一类问题就是从后往前推导。有时候我们很容易知道:如果只有一种情况时,最佳的选择应该怎么做,然后根据这个最佳选择往前一步推导,得到前一步的最佳选择,然后就是定义问题状态和状态之间的关系。我的理解是前面拆分的步骤之间的关系,用一种量化的形式表现出来,类似于高中学的推导公式,因为这种式子很容易用程序写出来,也可以说对程序比较亲和(也就是最后所说的状态转移方程式) 。我们再来看定义的下面的两段,我的理解是比如我们找到最优解,我们应该将最优解保存下来,为了往前推导时能够使用前一步的最优解,在这个过程中难免有一些相比于最优解差的解,此时我们应该放弃,只保存最优解,这样我们每一次都把最优解保存了下来,大大降低了时间复杂度

动态规划中有三个重要概念:

  • 最优子结构
  • 边界
  • 状态转移公式(递推方程)dp方程

经典问题

再谈斐波那契数列

优化递归:

通过上边的递归树可以看出在树的每层和上层都有大量的重复计算,可以把计算结果存起来,下次再用的时候就不用再计算了,这种方式叫记忆搜索,也叫做备忘录模式

代码如下:

package com.rubin.algorithm.dp;

/**
 * 优化版本 使用备忘录模式
 */
public class FibonacciRecord {

    private static final int[] records = new int[20];

    public static int findFibonacciItem(int index) {
        if (index <= 1) {
            return index;
        }
        if (records[index] == 0) {
            records[index] = findFibonacciItem(index -1) + findFibonacciItem(index - 2);
        }
        return records[index];
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.print(findFibonacciItem(i) + " ");
        }
    }

}

dp方程:

if(i < 2) 则

dp[0] = 0, dp[1] = 1

if(i >= 2) 则

dp[i] = dp[i - 1] + dp[i - 2]

最优子结构: fib[9]=finb[8]+fib[7]

边界:a[0]=0; a[1]=1

dp方程:fib[n]=fib[n-1]+fib[n-2]

实现代码如下:

package com.rubin.algorithm.dp;

/**
 * 优化版本 使用方程递推模式
 * T = O(n)
 */
public class FibonacciFunction {

    public static int findFibonacciItem(int index) {
        int[] records = new int[index + 1];
        records[0] = 0;
        records[1] = 1;
        for (int i = 2; i <= index; i++) {
            records[i] = records[i-1] + records[i-2];
        }
        return records[index - 1];
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            System.out.print(findFibonacciItem(i) + " ");
        }
    }

}

0-1背包问题

有n件物品和一个最大承重为W的背包,每件物品的重量是w[i],价值是v[i]

在保证总重量不超过W的前提下,选择某些物品装入背包,背包的最大总价值是多少?

注意:每个物品只有一件,也就是每个物品只能选择0件或者1件

分析:

假设:W=10,有5件物品,重量和价值如下:

w[1]=2,v[1]=6

w[2]=2,v[2]=3

w[3]=6,v[3]=5

w[4]=5,v[4]=4

w[5]=4,v[5]=6

dp数组的计算结果如下表:

i:选择i件物品 j:最大承重

解法:

dp方程:

如果:

可以选这一件物品

j < w[i]

不选:

dp[i, j] = dp[i - 1, j]

选了:

dp[i, j] = v[i] + dp[i - 1, j - w[i]]

两者取价值最大的数:Max( dp[i - 1, j] , v[i] + dp[i - 1, j - w[i]] )

不可以选这件物品:

j < w[i] 则:

dp[i, j] = dp[i - 1, j]

代码如下:

package com.rubin.algorithm.dp;

/**
 * 0-1背包问题
 * 有n件物品和一个最大承重为W的背包,每件物品的重量是w[i],价值是v[i],在保证总重量不超过W的前提下,选择某些物品装入背包,背包的最大总价值是多少?
 * 注意:每个物品只有一件,也就是每个物品只能选择0件或者1件
 * <p>
 * 分析:
 * 假设:W=10,有5件物品,重量和价值如下:
 * w[1]=2,v[1]=6
 * w[2]=2,v[2]=3
 * w[3]=6,v[3]=5
 * w[4]=5,v[4]=4
 * w[5]=4,v[5]=6
 * dp数组的计算结果如下表:
 * i\j 0 1 2 3 4 5 6 7 8 9 10
 * 0 0 0 0 0 0 0 0 0 0 0 0
 * 1 (w[1]=2,v[1]=6) 0 0 6 6 6 6 6 6 6 6 6
 * 2(w[2]=2,v[2]=3) 0 0 6 6 9 9 9 9 9 9 9
 * 3(w[3]=6,v[3]=5) 0 0 6 6 9 9 9 9 11 11 14
 * 4(w[4]=5,v[4]=4) 0 0 6 6 9 9 9 10 11 13 14
 * 5(w[5]=4,v[5]=6) 0 0 6 6 9 9 12 12 15 15 15
 * i:选择i件物品 j:最大承重
 *
 * T = O(i*j)
 */
public class BagDP {

    public static int maxValue(int[] values, int[] weights, int max) {
        if (values == null || weights == null || max <= 0 || values.length == 0 || weights.length == 0) {
            return 0;
        }
        int[][] DP = new int[values.length + 1][max + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= max; j++) {
                if (j < weights[i - 1]) {
                    DP[i][j] = DP[i - 1][j];
                } else {
                    DP[i][j] = Math.max(DP[i - 1][j], values[i - 1] + DP[i - 1][j - weights[i - 1]]);
                }
            }
        }
        int maxValue = DP[values.length][max];
        int j = max;
        for (int i = values.length; i > 0; i--) {
            if (DP[i][j] > DP[i - 1][j]) {
                System.out.println("选择了:w=" + weights[i - 1] + ",v=" + values[i - 1]);
                j -= weights[i - 1];
                if (j <= 0) {
                    break;
                }
            }
        }
        return maxValue;
    }

    public static void main(String[] args) {
        int[] values = {60, 30, 50, 40, 60};
        int[] weights = {2, 2, 6, 5, 4};
        int max = 10;
        System.out.println("最大价值是:" + maxValue(values, weights, max));
    }

}

此种解法时间复杂度为O(i * j)

使用动态规划四个步骤

  1. 把当前的复杂问题转化成一个个简单的子问题(分治)
  2. 寻找子问题的最优解法(最优子结构)
  3. 把子问题的解合并,存储中间状态
  4. 递归+记忆搜索或自底而上的形成递推方程(dp方程)

时间复杂度

新的斐波那契数列实现时间复杂度为O(n)

优缺点

优点:时间复杂度和空间复杂度都相当较低

缺点:难,有些场景不适用

适用场景

尽管动态规划比回溯算法高效,但是,并不是所有问题,都可以用动态规划来解决。能用动态规划解决的问题,需要满足三个特征,最优子结构、无后效性和重复子问题。在重复子问题这一点上,动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题,不能有重复子问题,而动态规划正好相反,动态规划之所以高效,就是因为回溯算法实现中存在大量的重复子问题

环形链表问题

给定一个链表,判断链表中是否有环。存在环返回 true ,否则返回 false

解法:

1、定义快慢两个指针:slow=head; fast=head.next;

2、遍历链表:快指针步长为2:fast=fast.next.next; 慢指针步长为1:slow=slow.next;

3、当且仅当快慢指针重合(slow==fast),有环,返回true

4、快指针为null,或其next指向null,没有环,返回false,操作结束

代码实现:

package com.rubin.algorithm.ring;

/**
 * 链表节点
 */
public class Node {
    int id;
    String name;
    Node next;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }
}
package com.rubin.algorithm.ring;

/**
 * 判断链表是否有环
 */
public class RingList {
    /**
     * 判断链表是否有环
     * @param head
     * @return
     */
    public static boolean isRing(Node head){
        if(head==null) return false;
        //定义快慢指针
        Node slow=head; //慢
        Node fast=head.next; //快

        while(fast!=null&&fast.next!=null){
            //追击相遇 有环
            if(slow==fast){
                return true;
            }
            fast=fast.next.next; //步长为2
            slow=slow.next;//步长为1

        }
        //无环
        return false;
    }

    public static void main(String[] args) {
        Node n1=new Node(1,"张飞");
        Node n2=new Node(2,"赵云");
        Node n3=new Node(3,"关羽");
        Node n4=new Node(4,"黄忠");
        Node n5=new Node(5,"狄仁杰");

        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        n5.next=n1;

        System.out.println(isRing(n1));
    }
}

以上就是本文的全部内容。欢迎小伙伴们积极留言交流~~~

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数据结构和算法
最后更新:2022年 6月 9日

RubinChu

一个快乐的小逗比~~~

打赏 点赞
< 上一篇

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复
文章目录
  • 贪心算法
    • 概念
    • 经典问题:部分背包
    • 时间复杂度
    • 优缺点
    • 适用场景
  • 分治算法
    • 概念
    • 经典问题
    • 时间复杂度
    • 优缺点
    • 适用场景
  • 回溯算法
    • 概念
    • 经典问题
      • N皇后问题
    • 时间复杂度
    • 优缺点
    • 适用场景
  • 动态规划
    • 概念
    • 经典问题
      • 再谈斐波那契数列
      • 0-1背包问题
    • 使用动态规划四个步骤
    • 时间复杂度
    • 优缺点
    • 适用场景
  • 环形链表问题
最新 热点 随机
最新 热点 随机
问题记录之Chrome设置屏蔽Https禁止调用Http行为 问题记录之Mac设置软链接 问题记录之JDK8连接MySQL数据库失败 面试系列之自我介绍 面试总结 算法思维
Kafka之集群与运维 SpringBoot之缓存 Spring之手写IoC框架 java面试系列之Linux Redis之Codis集群搭建 MongoDB之集群高可用

COPYRIGHT © 2021 rubinchu.com. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

京ICP备19039146号-1