笔试技巧：学会根据数据范围猜知识点               
一般1s  时间限制的题目，时间复杂度能跑到  1e8  左右（  python  和  java  会少一些，所以建议大家使用c/c++  做笔试题）。
n        范围        20        以内：
o(n*2^n)
状压搜索        /dfs        暴搜
n        范围        200        以内：
o(n^3)
三维        dp
n        范围        3000        以内：
o(n^2)
二维        dp         背包 枚举 二维前缀和等
n        范围        1e5        以内：
o(n√n)
暴力求因子等
n        范围        1e6        以内：
o(nlogn)
二分答案 使用各种        stl         并查集 欧拉筛等
n        范围        1e7        以内：
o(n)
双指针 线性        dp         差 分        /        前缀和
n        范围        1e14        以内：
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
说明
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<= 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()); //循环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)-'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的贪心和枚举怎么使用的详细内容。