【算法笔记】贪心算法

本文阅读 6 分钟

前言: 对于贪心算法的学习主要以增加阅历和经验为主,也就是多做多积累经验,以下通过几个题目来介绍贪心算法的乐趣!

1. 贪心算法基本介绍

  • 是一种局部最功利的标准,总是做出在当前看来是最好的选择
  • 难点在于证明局部最功利的标准可以得到全局最优解
  • 贪心一般跟排序和堆有关
  • 贪心算法的难点在于如何证明该标准可行,但是证明往往较难,可以通过对数器来验证最终的方式是否可行

2. 题目

题一:给定一个由字符串组成的数组 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

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

结束时间最早

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

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

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

举例:

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

方法模板: 思考该题时可能会想到以最大部分的金条长度来切割,但是该贪心思路是错误的(如要分割成长度为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

题四:输入:正数数组 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

题五: 给定一个字符串 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
本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://t4dmw.blog.csdn.net/article/details/123167925
-- 展开阅读全文 --
BUUCTF Web [极客大挑战 2019]Knife
« 上一篇 06-24
安全面试之XSS(跨站脚本攻击)
下一篇 » 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复