搜尋

首頁 >Java >java教程 >Java的貪心和枚舉怎麼使用

Java的貪心和枚舉怎麼使用

王林
王林轉載
2023-05-20 11:46:461125瀏覽

筆試技巧：學習根據資料範圍猜知識點              

一般1s  時間限制的題目，時間複雜度能跑到 1e8  筆試題）。

狀壓縮搜尋       /dfs        暴搜二維       dp         背包列舉二維前綴和等#以暴力求因素等n        範圍       1e6        以內：O(nlogn) 

n        範圍       20        以內：

O(n*2#n)

1

n        範圍     #1200        範圍以#   # #200  ^3)

 三維##O(n^2)

#n範圍       1e5        以內：

 O(n√n)

以告訴

##cooo 171 篩等
n        範圍       1e7        以內：

 O(n)

 雙指標線性       dp         差異      /        前綴與

O(√n )

求約數與約數個數

#

貪心：

貪心指每一步都做出目前最優的選擇。一般解決的問題有以下特點：局部最優能導致全局最優。

請注意，貪心並不是萬能的！

有n個物品。每個物品有價值v[i]，以及重量w[i]。

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

  • 策略1：依價值降序排列，每次取價值最高的。

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

  • 策略3 ：依價值/重量（即單位價值）降序排列，每次取單位價值最高的。

枚舉：

1.樸素枚舉

#顧名思義，用for迴圈列舉所有情況。

2.狀壓枚舉   

以n進位的性質進行列舉。

適合場景：共有n個物品，每個物品有m種狀態，列舉所有物品的所有狀態，複雜度為O(m^n)。

二進位狀壓枚舉的寫法：

經典問題：給定n個數a1、a2……an，每個數字可選可不選，列舉所有可能的方案。     

for(int i=0;i<1<<n;i++){  //i为1到2^n的状态压缩值   2^n
	int p=i;          //先将i取出
	int sum=0;        //用一个变量维护取出的数之和
	for(j=0;j<n;j++){   //转为二进制进行操作
		sum+=p%2*a[j];    //这句话是求取出来的数之和。p%2为对应二进制位
                  		 //这里也可以进行其他操作，不一一举例。
		p/=2;            //求下一个二进制位
     	}
     //这里可以添加想要的操作。
   }

演算法題1：

chika和蜜柑（PriorityQueue Comparator的使用）

難度 ⭐⭐

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

Chika吃了k個蜜柑，總共有n個蜜柑，她將計算所吃蜜柑的甜度和酸度之和。 chika想獲得盡可能大的甜度總和。如果有多種方案，她希望總酸度盡可能小。

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

主題資訊：先依甜度降序排序，後依酸度升序排序（維持先前的甜度降序排序優先，酸度升序排序次之） 

輸入說明:

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

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

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

輸出描述:

兩個正整數，以空格隔開。分別表示總酸度和總甜度。

範例

輸入

3 2

#1 3 4

2 2 5

##輸出

5 7

說明

選擇1號和3號蜜柑，總酸度為5，總甜度為7，為最優解。 

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(" ");
        //定义一个优先队列，并根据指定的比较器对其元素进行排序。
        PriorityQueue<Orange> queue = new PriorityQueue<>((Orange o1, Orange o2)->{
            //匿名内部类以lambda的形式定义排序规则
            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);
    }
}

目的：

了解什麼是貪心，當設計到優先順序時可以考慮使用PriorityQueue Comparator。

演算法題2：

#you和帆船 

難度 ⭐⭐

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

大海上有許多寶藏，每個寶藏的座標是已知的。 you的初始座標是（0,0）。她想探索兩個寶藏，然後回到初始點。

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

題目資訊：兩個for迴圈列舉一下，再儲存最短路徑即可。

輸入描述:

第一行一個正整數n，代表寶藏的數量。 （2≤n≤2000）

接下來的n行，每行2個正整數xi，yi，代表第i個寶藏的座標（-3000≤xi,yi≤3000）

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

輸出描述:

最短路線的長度。小數點後保留6位。

範例

輸入

2

1 0

0 1

輸出

3.414214

說明

Java的貪心和枚舉怎麼使用

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));
    }
}

目的：

了解什麼是列舉，雖然是一個列舉，但是結合實際還是有優化的方式。

比如此題兩層循環只列舉了一半的情況：因為所求的是距離，跟兩個端點無關。

思考：

假如不止有兩個寶箱需要被獲取，那麼該怎麼辦？ ？ ？下一題可以參考一下。

演算法題3： 

數位染色   

#難度 ⭐⭐⭐

小紅拿到了一個正整數 X 。她可以將其中一些數字染成紅色。然後她想讓所有染紅的數字數字總和等於沒染色的數字數字總和。

她不知道能不能達成目標。你能告訴她嗎？

輸入描述:

一個正整數X ，1輸出描述:

輸出"Yes"是在小紅能夠依要求完成染色的前提下。否則輸出"No"。

範例1

輸入

1234567

輸出

Yes

#說明

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

範例2

輸入

23

輸出

No

說明

#########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());
        //循环0到2^18来展现所有的可能性
        for(int i=0;i<1<<19;i++){
            long p=i,s1=0,s2=0,temp=x;
 
            //将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。
            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");
    }
}

这题使用的是状压枚举

只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）

 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++){}

当然这题也可以使用背包或dfs来解答。

算法题4： 

ranko的手表  

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

Ranko checked the time at t1 and then again at t2 after some time had passed.。她想弄清楚t1和t2两个时间点之间的最大和最小时间间隔是多少

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

输入描述:

两行输入两个时间，为 xx:xx 的形式。x可以是数字或字符'?'，当为'?'时表示该数字未显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例1

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 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)-&#39;0&#39; || s1.charAt(0) == &#39;?&#39;) &&
               (hour%10 == s1.charAt(1)-&#39;0&#39; || s1.charAt(1) == &#39;?&#39;) &&
               (minute/10 == s1.charAt(3)-&#39;0&#39; || s1.charAt(3) == &#39;?&#39;) &&
               (minute%10 == s1.charAt(4)-&#39;0&#39; || s1.charAt(4) == &#39;?&#39;)) a1.add(i);
            if((hour/10 == s2.charAt(0)-&#39;0&#39; || s2.charAt(0) == &#39;?&#39;) &&
               (hour%10 == s2.charAt(1)-&#39;0&#39; || s2.charAt(1) == &#39;?&#39;) &&
               (minute/10 == s2.charAt(3)-&#39;0&#39; || s2.charAt(3) == &#39;?&#39;) &&
               (minute%10 == s2.charAt(4)-&#39;0&#39; || s2.charAt(4) == &#39;?&#39;))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的貪心和枚舉怎麼使用的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述：
本文轉載於：yisu.com。如有侵權，請聯絡admin@php.cn刪除
上一篇：Java字串編碼解碼效能怎麼提升下一篇：Java字串編碼解碼效能怎麼提升

相關文章

看更多