Java讲解贪心算法案例

Java讲解贪心算法案例前言:通过一下一些题目来学习一下贪心算法。一、贪心算法简介1、是一种局部最功利的标准,总是做出在当前看来是最好的选择2、难点在于证明局部最功利的标准可以得到全局最优解3、贪心一般跟排序和堆有关4、贪心算法的难点在于如何证明该标准可行,但是证明往往较难,可以通过对数器来验证最终的方式是否可行二、题目实战案例1:给定一个又字符串组成的数组strs,必须把所有的字符串拼接起来,返回所有可能的拼接结果中,字典序最小的结果解答:得到字典序最…

前言:

通过一下一些题目来学习一下贪心算法。

一、贪心算法简介

1、是一种局部最功利的标准,总是做出在当前看来是最好的选择

2、难点在于证明局部最功利的标准可以得到全局最优解

3、贪心一般跟排序和堆有关

4、贪心算法的难点在于如何证明该标准可行,但是证明往往较难,可以通过对数器来验证最终的方式是否可行

二、题目实战

        案例1:给定一个又字符串组成的数组 strs,必须把所有的字符串拼接起来,返回所有可能的拼接结果中,字典序最小的结果

        解答:得到字典序最小的结果,我们可以将数组进行排序,使排序后的数组拼接的字符串的字典序最小即可。排序规则为字符串 a 和 字符串 b进行 a + b 和 b + a 的拼接后比比较这两者的字典序大小,如果 a + b 小,则字符串 a 排在 字符串 b 前。

        

public static class MyComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return (o1 + o2).compareTo(o2 + o1);
    }
}

public static String lowestString(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    Arrays.sort(strs, new MyComparator());
    String ans = "";
    for (int i = 0; i < strs.length; i++) {
        ans += strs[i];
    }
    return ans;
}



// 实例代码

public static void main(String[] args) {
    String[] strs = {"ba", "b", "cda"};
    System.out.println(lowestString(strs));
}
// 结果为:babcda

         案例2:一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。给你每一个项目的开始时间和结束时间,你来安排宣讲的日程,要求会议室进行的宣讲的场次最多。返回最多的宣讲场次,结束时间最早

        解答: 当我们思考该问题时,我们可能会想着使用开始时间最早或者宣讲时间最短来进行验证,但是这种贪心思路是错误的,正确的方法是以结束时间最早来思考这道题。找到第一个结束时间最早的会议,然后删除其余开始时间早于最早结束时间的会议,然后再找第二个结束时间最早的会议…

public static class Program {
    public int begin;
    public int end;

    public Program(int begin, int end) {
        this.begin = begin;
        this.end = end;
    }
}
public static int bestArrange(Program[] programs) {
    Arrays.sort(programs, new MyComparator());
    int timeLine = 0;
    int count = 0;
    for (int i = 0; i < programs.length; i++) {
        if (programs[i].begin >= timeLine) {
            count++;
            timeLine = programs[i].end;
        }
    }
    return count;
}
public static class MyComparator implements Comparator<Program> {
    @Override
    public int compare(Program o1, Program o2) {
        return o1.end - o2.end;
    }
}


// 实例代码
public static void main(String[] args) {
    Program[] programs = { new Program(1, 2), new Program(1, 5), new Program(3, 4), new Program(5, 6) };
    System.out.println(bestArrange(programs));
}
// 结果为:3

        案例3:一块金条切成两半,是需要花费和长度数值一样的铜板的。比如长度为20的金条,不管怎么切,都需要花费20个铜板。一群人想整分整块金条,怎么分最省铜板?输入一个数组,返回分割的最小代价        

        举例:

例如,给定数组{10, 20, 30},代表一共三个人,整块金条长度为60,要将金条分成10,20,30三个部分。

如果先把长度60的金条分成10和50,花费60;再把长度50的金条分成20和30,花费50,一共花费110的铜板

如果先把长度60的金条分成30和30,花费60,再把长度30的金条分成30和10,花费30,一共花费90铜板

        解答: 思考该题时可能会想到以最大部分的金条长度来切割,但是该贪心思路是错误的(如要分割成长度为97、98、99、100几部分,则要先将金条分成 97+98 和 99+100 两部分)。这里可以建一个小根堆,然后依次弹出堆顶两个元素相加,相加的结果就是这两块金条分割的花费,然后再将该结果入堆,继续以上步骤,直到堆中只剩一个数值

public static int lessMoney(int[] arr) {
    Queue<Integer> queue = new PriorityQueue<>();
    for(int num : arr) {
        queue.add(num);
    }
    int money = 0;
    int cur = 0;
    while(queue.size() > 1) {
        cur = queue.poll() + queue.poll();
        money += cur;
        queue.add(cur);
    }
    return money;
}


// 示例代码

public static void main(String[] args) {
    int[] arr = {10, 20, 30};
    System.out.println(lessMoney(arr));
}
// 结果为:90

        案例4:输入:正数数组 costs、正数数组 profits、正数 K、正数 M。cost[i] 表示 i 号项目的花费,profits[i] 表示 i 号项目在扣除花费之后还能挣到的钱,K 表示你只能串行的最多做 K 个项目,M 表示你初始的资金。说明:你没做完一个项目,马上获得的收益,可以支持你去做下一个项目。不能并行的做项目。输出:你最后获得的最大钱数

        解答: 可以构建一个以项目的花费从低到高的小根堆,并将所有项目入堆,再构建一个以项目的利润从高到低的大根堆,将小根堆中消费少于当前拥有的资金的项目弹出,并加入到大根堆中,取利润最高的项目进行购买,之后依次进行以上步骤

public static class Program {
    public int cost;
    public int profit;

    public Program(int cost, int profit) {
        this.cost = cost;
        this.profit = profit;
    }
}

public static class MinCostComparator implements Comparator<Program>{

    @Override
    public int compare(Program o1, Program o2) {
        return o1.cost - o2.cost;
    }

}

public static class MaxProfitComparator implements Comparator<Program>{

    @Override
    public int compare(Program o1, Program o2) {
        return o2.profit - o1.profit;
    }

}

public static int findMaximizedCapital(int K, int W, int[] profits, int[] capital) {
    Queue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
    Queue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
    for(int i = 0; i < capital.length; i++) {
        Program program = new Program(capital[i], profits[i]);
        minCostQ.add(program);
    }
    while(K > 0) {
        while(minCostQ.size() > 0 && minCostQ.peek().cost <= W) {
            maxProfitQ.add(minCostQ.poll());
        }
        if(maxProfitQ.isEmpty()) {
            break;
        }
        W += maxProfitQ.poll().profit;
        K--;
    }
    return W;
}



// 示例代码

public static void main(String[] args) {
    int[] capital = {2,1,6,4};
    int[] profits = {2,3,1,4};
    int K = 3;
    int W = 1;
    System.out.println(findMaximizedCapital(K,W,profits,capital));
}
// 结果为:10

        案例5:给定一个字符串 str,只由 ‘X’ 和 ‘.’ 两种字符构成。‘X’ 表示墙,不能放灯,也不需要点亮;’.’ 表示居民点,可以放灯,需要点亮。如果灯放在 i 位置,可以让 i-1、i 和 i+1 三个位置被点亮。返回如果点亮 str 中所有需要点亮的位置,至少需要几盏灯

        解答: 假设 index 位置是墙时,那么 index = index+1;当 index 位置是居民点时,index+1 位置为墙时,就需要一盏灯,并且 index = index+2;当 index 位置为居民点,index+1 位置为居民点,不论 index+2 位置为居民点还是墙,都需要一盏灯,并且 index = index+3

public static int minLight(String road) {
    char[] str = road.toCharArray();
    int index = 0;
    int light = 0;
    while(index<str.length) {
        if(str[index] == 'X') {
            index++;
        }else {
            light++;
            if(index+1==str.length) {
                break;
            }else {
                if(str[index+1]=='X') {
                    index=index+2;
                }else {
                    index=index+3;
                }
            }
        }
    }
    return light;
}


// 示例代码
public static void main(String[] args) {
    String road = "X.XX..X...X....X";
    System.out.println(minLight(road));
}
// 结果为:5

今天的文章Java讲解贪心算法案例分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/8833.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注