用這種解題方法，我解決了大部分的 leetcode 貪心算法題
“這是本人第40篇原創(chuàng)博文，每周兩篇更新，謝謝賞臉閱讀文章
今天介紹一種解決常規(guī)的貪心策略或者字典排序的題目的通用解題方法。
第一題，leetcode中等難度題目
先來(lái)一道簡(jiǎn)單的字典序排列的問(wèn)題，這個(gè)題目我這里不會(huì)用最優(yōu)解來(lái)解決這個(gè)問(wèn)題，這個(gè)是leetcode的中等難度的題目，最優(yōu)解還是需要再思考一下的，這道題目作為文章開(kāi)頭只是為了介紹我想要介紹的貪心的解題的一種思路而已，大佬請(qǐng)勿噴！！
看到這個(gè)題目，我就是想用暴力的方法解決，以便更好的理解這種解題思路。
先給出我的答案，非常暴力，但是非常好理解。
public?List?lexicalOrder(int?n)? {
????????List?list?=?new?ArrayList<>();
????????for(int?i?=?1;?i?<=?n;?i++){
????????????list.add(i?+?"");
????????}
????????Collections.sort(list,(o1,o2)->{
????????????return?o1.compareTo(o2);
????????});
????????List?iList?=?new?ArrayList<>();
????????list.stream().forEach((str)->{
????????????iList.add(Integer.parseInt(str));
????????});
????????return?iList;
????}
這個(gè)解題方法很簡(jiǎn)單，用的就是Collections.sort()方法的排序，然后重寫(xiě)一下Comparator類(lèi)而已，這里用的是lambda表達(dá)式，使得代碼更加的簡(jiǎn)潔。
最優(yōu)解大家可以去leetcode看看哈，自己動(dòng)手，豐衣足食。
所以，通過(guò)這個(gè)題目我想給出的信息就是：通常涉及到字符串排序，字典序，數(shù)字排序等等的題目，都是可以用這種思路來(lái)解決問(wèn)題的。
不信，我們?cè)倏纯雌渌}目。
第二題，leetcode中等難度題目
這是一道常見(jiàn)的topk問(wèn)題，最優(yōu)解也不是我給出的答案，目的只是為了闡述這種解題方法。
我的解題方法：用優(yōu)先級(jí)隊(duì)列，維護(hù)一個(gè)大小為k小頂堆，每次堆的元素到達(dá)k時(shí)，先彈出堆頂元素，這樣就堆總是維持著k個(gè)最大值，最終可以的到前k高的元素。
下面看看我的解答（注意：我的答案絕對(duì)不是最優(yōu)解，只是為了闡述這種方法）
class?Solution?{
????public?int[]?topKFrequent(int[]?nums,?int?k)?{
????????Queue?queue?=?new?PriorityQueue<>(k,(o1,o2)->{
????????????return?o2.num?-?o1.num;
????????});
????????HashMap?map?=?new?HashMap<>();
????????for(int?i?=?0;?i?????????????map.put(nums[i],map.getOrDefault(nums[i],0)?+?1);
????????}
????????for(int?key?:?map.keySet()){
????????????queue.offer(new?Obj(key,map.get(key)));
????????}
????????int[]?ans?=?new?int[k];
????????int?i?=?0;
????????while(i?????????????ans[i]?=?queue.poll().target;
????????????i++;
????????}
????????return?ans;
????}
????class?Obj?{
????????public?int?target;
????????public?int?num;
????????public?Obj(int?target,?int?num){
????????????this.target?=?target;
????????????this.num?=?num;
????????}
????}
}
這種方法沒(méi)有維護(hù)k的最大的堆。
class?Solution?{
??public?List?topKFrequent(int[]?nums,?int?k)? {
????HashMap?map?=?new?HashMap();
????for?(int?n:?nums)?{
??????map.put(n,?map.getOrDefault(n,?0)?+?1);
????}
????PriorityQueue?heap?=
????????????new?PriorityQueue((n1,?n2)?->?map.get(n1)?-?map.get(n2));
????for?(int?n:?map.keySet())?{
??????heap.add(n);
??????if?(heap.size()?>?k)
????????heap.poll();
????}
????
????List?top_k?=?new?LinkedList();
????while?(!heap.isEmpty())
??????top_k.add(heap.poll());
????Collections.reverse(top_k);
????return?top_k;
??}
}
這種方法維護(hù)k的最大的堆。
對(duì)比發(fā)現(xiàn)：不管維護(hù)k的最大堆還是不維護(hù)，核心的思想都是
Queue?queue?=?new?PriorityQueue<>(k,(o1,o2)->{
????????????return?o2.num?-?o1.num;
????????});
和這段代碼
PriorityQueue?heap?=
????????????new?PriorityQueue((n1,?n2)?->?map.get(n1)?-?map.get(n2));
對(duì)比第一題中的
Collections.sort(list,(o1,o2)->{
????????????return?o1.compareTo(o2);
????????});
用的都是內(nèi)部類(lèi)：Comparator，然后進(jìn)行構(gòu)建符合題意的排序規(guī)則。
第三題，更復(fù)雜點(diǎn)的
這個(gè)題目就更能明白什么是構(gòu)建符合題意的排序規(guī)則。
因?yàn)楹芏囝}目不止讓你根據(jù)一個(gè)字段進(jìn)行排序，可能是兩個(gè)字段進(jìn)行排序，或者三個(gè)字段進(jìn)行排序，所以就需要進(jìn)行“構(gòu)建”。
這個(gè)題目的解題思路：先排序再插入
排序規(guī)則：按照先H高度降序，K個(gè)數(shù)升序排序 遍歷排序后的數(shù)組，根據(jù)K插入到K的位置上
核心思想：高個(gè)子先站好位，矮個(gè)子插入到K位置上，前面肯定有K個(gè)高個(gè)子，矮個(gè)子再插到前面也滿足K的要求。
再看看解答
public?int[][]?reconstructQueue(int[][]?people)?{
????????//?[7,0],?[7,1],?[6,1],?[5,0],?[5,2],?[4,4]
????????//?再一個(gè)一個(gè)插入過(guò)程
????????//?[7,0]
????????//?[7,0],?[7,1]
????????//?[7,0],?[6,1],?[7,1]
????????//?[5,0],?[7,0],?[6,1],?[7,1]
????????//?[5,0],?[7,0],?[5,2],?[6,1],?[7,1]
????????//?[5,0],?[7,0],?[5,2],?[6,1],?[4,4],?[7,1]
????????Arrays.sort(people,?(o1,?o2)?->?o1[0]?==?o2[0]???o1[1]?-?o2[1]?:?o2[0]?-?o1[0]);
????????LinkedList<int[]>?list?=?new?LinkedList<>();
????????for?(int[]?i?:?people)?{
????????????//在i位置，插入數(shù)：i[1]是[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]的第一個(gè)數(shù)，表示前面有幾個(gè)比我高的。
????????????list.add(i[1],?i);
????????}
????????return?list.toArray(new?int[list.size()][2]);
????}
你會(huì)發(fā)現(xiàn)，核心代碼還是跟第一題和第二題一樣，只是復(fù)雜一點(diǎn)點(diǎn)。
Arrays.sort(people,?(o1,?o2)?->?o1[0]?==?o2[0]???o1[1]?-?o2[1]?:?o2[0]?-?o1[0]);
這是什么意思呢：o1和o2是一個(gè)類(lèi)似這樣[7,0]的一位數(shù)組，當(dāng)?shù)谝粋€(gè)數(shù)相等時(shí)，再比較一維數(shù)組的第二個(gè)數(shù)的大小，不相等，當(dāng)然先比較第一個(gè)數(shù)了。
這個(gè)就是多個(gè)字段比較的例子，是不是還是跟前面的思路是一樣的。
總結(jié)
最后發(fā)現(xiàn)，關(guān)于排序的，不管是，數(shù)組的排序，數(shù)字的排序，字符串的排序，還是優(yōu)先級(jí)隊(duì)列的排序，我們都是可以用Java的Comparator來(lái)解決的。
就說(shuō)這么多，只是思路，不要死磕最優(yōu)解?。。?/p>