Java的貪心和枚舉怎么使用

今天小編給大家分享一下Java的貪心和枚舉怎么使用的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

筆試技巧：學(xué)會(huì)根據(jù)數(shù)據(jù)范圍猜知識(shí)點(diǎn)               

一般1s  時(shí)間限制的題目，時(shí)間復(fù)雜度能跑到  1e8  左右（  python  和  java  會(huì)少一些，所以建議大家使用c/c++  做筆試題）。

貪心：

貪心指每一步都做出當(dāng)前最優(yōu)的選擇。一般解決的問題有如下特點(diǎn)：局部最優(yōu)能導(dǎo)致全局最優(yōu)。

請(qǐng)注意，貪心并不是萬能的！

有n個(gè)物品。每個(gè)物品有價(jià)值v[i]，以及重量w[i]。

現(xiàn)在取總重量不超過m的物品，問取的物品價(jià)值最大是多少？（背包問題）

• 策略1：按照價(jià)值降序排列，每次取價(jià)值最高的。

• 策略2 ：按照重量升序排列，每次取重量最輕的。

• 策略3 ：按照價(jià)值/重量（即單位價(jià)值）降序排列，每次取單位價(jià)值最高的。

枚舉：

1.樸素枚舉

顧名思義，用for循環(huán)枚舉所有情況。

2.狀壓枚舉   

借助n進(jìn)制的性質(zhì)進(jìn)行枚舉。

適合場(chǎng)景：共有n個(gè)物品，每個(gè)物品有m種狀態(tài)，枚舉所有物品的所有狀態(tài)，復(fù)雜度為O(m^n)。

二進(jìn)制狀壓枚舉的寫法：

典型場(chǎng)景： 總共有n個(gè)數(shù)：a1、a2……an，每個(gè)數(shù)可以取也可以不取，枚舉所有方案。      

for(int i=0;i<1<<n;i++){  //i為1到2^n的狀態(tài)壓縮值   2^n
	int p=i;          //先將i取出
	int sum=0;        //用一個(gè)變量維護(hù)取出的數(shù)之和
	for(j=0;j<n;j++){   //轉(zhuǎn)為二進(jìn)制進(jìn)行操作
		sum+=p%2*a[j];    //這句話是求取出來的數(shù)之和。p%2為對(duì)應(yīng)二進(jìn)制位
                  		 //這里也可以進(jìn)行其他操作，不一一舉例。
		p/=2;            //求下一個(gè)二進(jìn)制位
     	}
     //這里可以添加想要的操作。
   }

算法題1：

chika和蜜柑（PriorityQueue+Comparator的使用）

難度 ??

chika很喜歡吃蜜柑。每個(gè)蜜柑有一定的酸度和甜度，chika喜歡吃甜的，但不喜歡吃酸的。

一共有n個(gè)蜜柑，chika吃k個(gè)蜜柑，將獲得所吃的甜度之和與酸度之和。chika想獲得盡可能大的甜度總和。如果有多種方案，她希望總酸度盡可能小。

她想知道，最終的總酸度和總甜度是多少？

題目信息：先按甜度降序排序，后按酸度升序排序（保持之前的甜度降序排序優(yōu)先，酸度升序排序次之） 

輸入描述:

第一行有兩個(gè)正整數(shù)n和k，分別代表蜜柑總數(shù)和chika吃的蜜柑數(shù)量。(1≤k≤n≤200000)

第二行有n個(gè)正整數(shù)ai，分別代表每個(gè)蜜柑的酸度。（1≤ai≤1e9）

第二行有n個(gè)正整數(shù)bi，分別代表每個(gè)蜜柑的甜度。（1≤bi≤1e9）

輸出描述:

兩個(gè)正整數(shù)，用空格隔開。分別表示總酸度和總甜度。

示例

輸入

3 2

1 3 4

2 2 5

輸出

5 7

說明

選擇1號(hào)和3號(hào)蜜柑，總酸度為5，總甜度為7，為最優(yōu)解。

import java.io.*;
import java.util.*;
public class Main{
    public static class Orange{
            int acid;
            int sweet;
            public Orange(int acid, int sweet){
                this.acid = acid;
                this.sweet = sweet;
            }
            public Orange(){}
        }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = br.readLine().split(" ");
        int n = Integer.parseInt(tmp[0]);
        int k = Integer.parseInt((tmp[1]));
        String[] ai = br.readLine().split(" ");
        String[] bi = br.readLine().split(" ");
        //定義一個(gè)優(yōu)先隊(duì)列，并根據(jù)指定的比較器對(duì)其元素進(jìn)行排序。
        PriorityQueue<Orange> queue = new PriorityQueue<>((Orange o1, Orange o2)->{
            //匿名內(nèi)部類以lambda的形式定義排序規(guī)則
            if(o1.sweet == o2.sweet){
                return o1.acid - o2.acid;
            }else{
                return o2.sweet - o1.sweet;
            }
        });
        for(int i = 0; i < n; i++){
            Orange orange = new Orange();
            orange.acid = Integer.parseInt(ai[i]);
            orange.sweet = Integer.parseInt(bi[i]);
            queue.add(orange);
        }
        long totalAcid = 0;
        long totalSweet = 0;
        for(int i = 0; i < k; i++){
            Orange o = queue.poll();
            totalAcid += o.acid;
            totalSweet += o.sweet;
        }
        System.out.println(totalAcid + " " + totalSweet);
    }
}

目的：

了解什么是貪心，當(dāng)設(shè)計(jì)到優(yōu)先級(jí)時(shí)可以考慮使用PriorityQueue+Comparator。

算法題2：

you和帆船 

難度 ??

you的父親是一名船長(zhǎng)。因此you從小就很喜歡大海。這天，她乘著一艘帆船出發(fā)了。

大海上有很多寶藏，每個(gè)寶藏的坐標(biāo)是已知的。you的初始坐標(biāo)是（0,0）。她想探索兩個(gè)寶藏，然后回到初始點(diǎn)。

you希望航線盡可能短。她想知道，最短航線的長(zhǎng)度是多少？

題目信息：兩個(gè)for循環(huán)枚舉一下，再保存最短路徑即可。

輸入描述:

第一行一個(gè)正整數(shù)n，代表寶藏的數(shù)量。（2≤n≤2000）

接下來的n行，每行2個(gè)正整數(shù)xi，yi，代表第i個(gè)寶藏的坐標(biāo)（-3000≤xi,yi≤3000）

不保證不存在兩個(gè)寶藏位置相同。意思是，you可以在同一個(gè)位置探索這兩個(gè)寶藏。

輸出描述:

最短路線的長(zhǎng)度。小數(shù)點(diǎn)后保留6位。

示例

輸入

2

1 0

0 1

輸出

3.414214

說明

import java.io.*;
import java.util.*;
 
class Point{
    double x;
    double y;
}
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Point[] points = new Point[n];
        for(int i=0;i<n;i++){
            String[] strings = br.readLine().split(" ");
            Point point = new Point();
            point.x = Integer.parseInt(strings[0]);
            point.y = Integer.parseInt(strings[1]);
            points[i] = point;
        }
        double min = Double.MAX_VALUE;//定義最大值，尋找較小值
        //雙層遍歷枚舉
        for (int i=0;i<n-1;i++) {
            for (int j=i+1;j<n;j++) {
                double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y) 
                        + Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y) 
                        + Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));
                min = Math.min(min, temp);
            }
        }
        System.out.println(String.format("%.6f", min));
    }
}

目的：

了解什么是枚舉，雖然是一個(gè)一個(gè)列舉，但是結(jié)合實(shí)際還是有優(yōu)化的方式。

比如此題兩層循環(huán)只枚舉了一半的情況：因?yàn)樗蟮氖蔷嚯x，跟兩個(gè)端點(diǎn)無關(guān)。

思考：

假如不止有兩個(gè)寶箱需要被獲取，那么應(yīng)該怎么辦？？？下一題可以參考一下。

算法題3： 

數(shù)位染色   

難度 ???

小紅拿到了一個(gè)正整數(shù) X 。她可以將其中一些數(shù)位染成紅色。然后她想讓所有染紅的數(shù)位數(shù)字之和等于沒染色的數(shù)位數(shù)字之和。

她不知道能不能達(dá)成目標(biāo)。你能告訴她嗎？

輸入描述:

一個(gè)正整數(shù)X ，1<= X <=10^18

輸出描述:

如果小紅能按要求完成染色，輸出"Yes"。否則輸出"No"。

示例1

輸入

1234567

輸出

Yes

說明

將3、4、7染成紅色即可，這樣3+4+7=1+2+5+6

示例2

輸入

23

輸出

No

說明

顯然無論如何都不能完成染色。

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Long x= Long.parseLong(br.readLine());
        //循環(huán)0到2^18來展現(xiàn)所有的可能性
        for(int i=0;i<1<<19;i++){
            long p=i,s1=0,s2=0,temp=x;
 
            //將p擬化為2進(jìn)制，通過j來尋尾。尋一次p就對(duì)應(yīng)的二進(jìn)制數(shù)就少一位。
            for(int j=0;j<19;j++){
                if(p%2==1)s1+=temp%10;
                else s2+=temp%10;
                p/=2;
                temp/=10;
            }
            if(s1==s2){
                System.out.println("Yes");
                System.exit(0);
            }
        }
        System.out.println("No");
    }
}

這題使用的是狀壓枚舉

只有兩種狀態(tài)就擬成2進(jìn)制，假如有3種狀態(tài)就擬成3進(jìn)制（上面的代碼會(huì)有些許改變，n種狀態(tài)也一樣）

 for(int i=0;i<1<<19;i++)  
//修改成
 for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;
 for(int i=0;i<p1[i];i++){}

當(dāng)然這題也可以使用背包或dfs來解答。

算法題4： 

ranko的手表  

難度 ????

ranko 的手表壞了，正常應(yīng)該顯示 xx:xx 的形式（4 個(gè)數(shù)字），比如下午 1 點(diǎn)半應(yīng)該顯示 13:30 ，但現(xiàn)在經(jīng)常會(huì)有一些數(shù)字有概率無法顯示。

ranko 在 t1 時(shí)刻看了下時(shí)間，過了一段時(shí)間在 t2 時(shí)刻看了下時(shí)間。她想知道， t1  和t2這兩個(gè)時(shí)刻之間相距的時(shí)間的最大值和最小值是多少？

保證t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之間。 

輸入描述:

兩行輸入兩個(gè)時(shí)間，為 xx:xx 的形式。其中 x 為數(shù)字或者字符 '?' ，問號(hào)代表這個(gè)數(shù)字沒有顯示。保證輸入是合法的。

輸出描述:

一行輸出兩個(gè)整數(shù)，分別代表 t1 和 t2 相距時(shí)間的最小值和最大值（單位分鐘）。

示例1

輸入

18:0?

2?:1?

輸出

121 319

說明

相距最小的時(shí)間為 18:09 到 20:10 ，相距121分鐘。

相距最大的時(shí)間為 18:00 到 23:19 ，相距319分鐘。

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        ArrayList<Integer> a1 = new ArrayList<>();
        ArrayList<Integer> a2 = new ArrayList<>();
        for(int i = 0; i < 60*24; i++){
            int hour = i/60, minute = i%60;
            if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&
               (hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&
               (minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&
               (minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);
            if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&
               (hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&
               (minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&
               (minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);
        }
        int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int i = 0; i<a1.size();i++){
            for(int j = 0; j<a2.size();j++){
                if(a1.get(i)<a2.get(j)){
                    min = Math.min(min,a2.get(j)-a1.get(i));
                    max = Math.max(max,a2.get(j)-a1.get(i));
                }
            }
        }
        System.out.print(min + " " + max);
    }
}

以上就是“Java的貪心和枚舉怎么使用”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。