桶排序、堆排序、奇偶排序、计数排序、阿坤老师的独特瓷器、封闭图形个数、二进制王国【算法赛】
桶排序
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util.LinkedList; public class Main { static int N=100010,idx;//res=0; static String s[]=new String[N]; static boolean num[]=new boolean[N]; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); // int T=Integer.parseInt(br.readLine()); // String g[]=br.readLine().split(" "); int arr[]={3,6,8,5,90,45,37,67,29,78}; bucketSort(arr,arr.length); // } static void bucketSort(int arr[],int n){ if(arr==null|| arr.length==0)return; int minz=arr[0]; int maxz=arr[0]; for (int i = 1; i < n; i++) { minz=Math.min(minz, arr[i]); maxz=Math.max(maxz, arr[i]); } int bucketnum=(maxz-minz)/arr.length+1;//至少有一个桶 LinkedList<LinkedList<Integer>> buckets = new LinkedList<>(); for (int i = 0; i < bucketnum; i++) { buckets.add(new LinkedList<>()); } for (int i = 0; i < n; i++) { int u=arr[i]; int ind=(u-minz)/n; buckets.get(ind).add(u); } for (int i = 0; i < bucketnum; i++) { Collections.sort(buckets.get(i)); } int i=0; for(LinkedList<Integer> list:buckets){ for(int u:list){ arr[i++]=u; } } for (int j = 0; j < n; j++) { System.out.println(arr[j]); } } }堆排序
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N=100010,idx;//res=0; static String s[]=new String[N]; static boolean num[]=new boolean[N]; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); // int T=Integer.parseInt(br.readLine()); // String g[]=br.readLine().split(" "); int arr[]={3,6,8,5,90,45,37,67,29,78}; int n=arr.length; //建一个大根堆 每次将堆顶元素放在后面 再建一个大根堆 一次类推 //堆是一个完全二叉树的结构 我们从叶子结点开始 不断维护一个大根堆 //依次向上维护 直到拼出一个完整的大根堆 //叶子不需要维护 从最后一个非叶子结点开始维护 非叶子结点个数为floor(n/2) for (int i = n/2-1; i >=0; i--) { heap(arr,n,i); } for (int i = n-1; i >0; i--) {//每次把堆顶元素放在当前轮次的最后 int h=arr[0]; arr[0]=arr[i]; arr[i]=h; heap(arr, i,0); } for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } static void heap(int a[],int n,int i){//维护以i为父结点的子树 int large=i; int left=2*i+1,right=2*i+2; if(left<n && a[left]>a[large]){ large=left; } if(right<n && a[right]>a[large]){ large=right; } if(large!=i){ int t=a[i]; a[i]=a[large]; a[large]=t; heap(a, n, large); } } }奇偶排序【算法赛】
问题描述
小蓝所在的王国名为偶数王国，在他们王国中数字的比较通常按以下步骤进行：
- 如果两个数字的奇偶性不同，那么偶数一定大于奇数。
- 如果两个数字的奇偶性相同，则比较它们的实际数值大小。
现在给你一个正整数数组 AA，请你输出按照偶数王国规则从小到大排序后的 AA。
输入格式
第一行输入一个整数 N(1≤N≤103)N(1≤N≤103) 表示数组 AA 的长度。
第二行输入 NN 个整数 A1,A2,A3,⋯,AN(1≤Ai≤105)A1,A2,A3,⋯,AN(1≤Ai≤105) 表示数组 AA。
输出格式
输出一行 NN 个整数表示答案。
样例输入
5 1 2 3 4 5样例输出
1 3 5 2 4import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N=100010,idx;//res=0; static Integer a[]=new Integer[N]; static boolean num[]=new boolean[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); String g[]=br.readLine().split(" "); for (int i = 0; i < n ; i++) { a[i]=Integer.parseInt(g[i]); } Arrays.sort(a, 0,n, (a,b)->{//转化为Integer才能使用lamda表达式 boolean aa=(a%2==0),bb=(b%2==0); if(aa==bb){ return a-b; }else{ if(a%2==0){ return 1; }else{ return -1; } } }); for (int i = 0; i < n; i++) { System.out.print(a[i]+" "); } } }计数排序
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N=100010,idx;//res=0; static Integer a[]=new Integer[N]; static boolean num[]=new boolean[N]; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); // int n=Integer.parseInt(br.readLine()); // String g[]=br.readLine().split(" "); int u[]={9,56,75,65,54,33,23}; int z=Integer.MIN_VALUE; for (int i = 0; i < u.length; i++) { z=Math.max(z, u[i]); } int d[]=new int[z+1]; for (int i = 0; i < u.length; i++) { d[u[i]]++; } int id=0; for (int i = 0; i < d.length; i++) { while(d[i]-->0){ a[id++]=i; } } for (int i = 0; i < id; i++) { System.out.print(a[i]+" "); } } }阿坤老师的独特瓷器
问题描述
阿坤老师是一位热爱中国传统文化的老师，特别喜欢收藏各种各样的瓷器。他有一个习惯，就是在每一个瓷器底部都标注上瓷器的直径 dd 和高度 hh。
一天，阿坤老师突然想整理一下自己的瓷器收藏。他有一个特别的定义：“独特瓷器”，即对于一个瓷器 AA，如果不存在另一个瓷器 BB ，其直径和高度都严格大于瓷器 AA 的直径和高度，则称瓷器 AA 为“独特瓷器”。
阿坤老师有 NN 个瓷器，每个瓷器都有一个直径和高度。请你帮助阿坤老师，计算出他的瓷器收藏中有多少个“独特瓷器”。
输入格式
输入的第一行包含一个整数 NN（1≤N≤1051≤N≤105）。
接下来的 NN 行，每行包含两个整数，分别表示瓷器的直径 dd 和高度 hh（1≤d,h≤1061≤d,h≤106）。
输出格式
输出一个整数，表示阿坤老师的瓷器收藏中“独特瓷器”的数量。
样例输入
5 3 4 5 6 2 5 3 7 6 5样例输出3
超时：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N=100010,idx;//res=0; //static Integer a[]=new Integer[N]; static Node node[]=new Node[N]; static boolean f[]=new boolean[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); //String g[]=br.readLine().split(" "); for (int i = 0; i < n; i++) { String g[]=br.readLine().split(" "); int d=Integer.parseInt(g[0]),h=Integer.parseInt(g[1]); node[idx++]=new Node(d, h); } for (int i = 0; i < n; i++) { f[i]=true; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(i==j)continue; if(node[i].d<node[j].d && node[i].h<node[j].h){ f[i]=false; } } } int res=0; for (int i = 0; i < n; i++) { if(f[i]==true)res++; } System.out.println(res); } static class Node{ int d; int h; public Node() { // TODO Auto-generated constructor stub } public Node(int d, int h) { this.d = d; this.h = h; } } }正确：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N=100010,idx;//res=0; //static Integer a[]=new Integer[N]; static Node node[]=new Node[N]; // static boolean f[]=new boolean[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); //String g[]=br.readLine().split(" "); for (int i = 0; i < n; i++) { String g[]=br.readLine().split(" "); int d=Integer.parseInt(g[0]),h=Integer.parseInt(g[1]); node[idx++]=new Node(d, h); } if(n==1){ System.out.println(1);return; } Arrays.sort(node,0,n);//先按d降序 h升序 int maxh=0,res=0; for (int i = 0; i < n; i++) { if(node[i].h>=maxh){ res++; maxh=node[i].h; } } System.out.println(res); } static class Node implements Comparable<Node>{ int d; int h; public Node() {} public Node(int d, int h) { this.d = d; this.h = h; } @Override public int compareTo(Node o) { if(d==o.d){ return h-o.h; }else{ return o.d-d; } } } }封闭图形个数
问题描述
在蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。
封闭图形是指数字中完全封闭的空间，例如数字 11、22、33、55、77 都没有形成封闭图形，而数字 00、44、66、99 分别形成了 11 个封闭图形，数字 88 则形成了 22 个封闭图形。值得注意的是，封闭图形的个数是可以累加的。例如，对于数字 6868，由于 66 形成了 11 个封闭图形，而 88 形成了 22 个，所以 6868 形成的封闭图形的个数总共为 33。
在比较两个数的大小时，如果它们的封闭图形个数不同，那么封闭图形个数较多的数更大。例如，数字 4141 和数字 1818，它们对应的封闭图形的个数分别为 11 和 22，因此数字 4141 小于数字 1818。如果两个数的封闭图形个数相同，那么数值较大的数更大。例如，数字 1414 和数字 4141，它们的封闭图形的个数都是 11，但 14<4114<41，所以数字 1414 小于数字 4141。 如果两个数字的封闭图形个数和数值都相同，那么这两个数字被认为是相等的。
小蓝对蓝桥王国的数字大小规则十分感兴趣。现在，他将给定你 nn 个数 a1,a2,…,ana1,a2,…,an，请你按照蓝桥王国的数字大小规则，将这 nn 数从小到大排序，并输出排序后结果。
输入格式
第一行包含一个整数 nn，表示给定的数字个数。
第二行包含 nn 个整数 a1,a2,…,ana1,a2,…,an，表示待排序的数字。
输出格式
输出一行，包含 nn 个整数，表示按照蓝桥王国的数字大小规则从小到大排序后的结果，每两个数字之间用一个空格分隔。
样例输入
3 18 29 6样例输出
6 29 18样例说明
对于给定的数字序列 [18,29,6][18,29,6]，数字 1818 的封闭图形个数为 22，数字 2929 的封闭图形个数为 11，数字 66 的封闭图形个数为 11。按照封闭图形个数从小到大排序后，得到 [29,6,18][29,6,18]。
由于数字 2929 和数字 66 的封闭图形个数相同，因此需要进一步按照数值大小对它们进行排序，最终得到 [6,29,18][6,29,18]。
评测用例规模与约定
对于 50%50% 的评测用例，1≤n≤2×1031≤n≤2×103，1≤ai≤1051≤ai≤105。
对于所有评测用例，1≤n≤2×1051≤n≤2×105，1≤ai≤1091≤ai≤109。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Main { static Map<Integer, Integer> map=new HashMap<Integer, Integer>(); static int N=2*100010,idx;//res=0; static Integer a[]=new Integer[N]; //static Node node[]=new Node[N]; // static boolean f[]=new boolean[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); String g[]=br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(g[i]); } map.put(4, 1);map.put(6, 1);map.put(8, 2);map.put(9, 1);map.put(0, 1); Arrays.sort(a,0,n,(a,b)->{ int aa=cal(a),bb=cal(b); if(aa==bb){ return a-b; }else{ return aa-bb; } }); for (int i = 0; i < n; i++) { System.out.print(a[i]+" "); } } static int cal(int n){ if(n==0)return 1; int sum=0; while(n>0){ sum+=map.getOrDefault(n%10, 0); n/=10; } return sum; } }二进制王国【算法赛】
问题描述
二进制王国是一个非常特殊的国家，因为该国家的居民仅由 00 和 11 组成。
在这个国家中，每个家庭都可以用一个由 00 和 11 组成的字符串 SS 来表示，例如 101101、000000、111111 等。
现在，国王选了出 NN 户家庭参加邻国的庆典。为了符合王国的审美标准，我们需要选择一种排队顺序，使得最终形成的队伍在字典序上是最小的。
国王将这个任务交给了你，请你解决这个问题。
输入格式
第一行包含一个整数 N(1 ≤N≤2×105)N(1 ≤N≤2×105)，代表二进制家庭数量。
接下来输入 NN 行，第 ii 行输入一个二进制字符串 SiSi 表示第 ii 户家庭。
数据范围保证：∑i=1n∣Si∣≤2×105∑i=1n∣Si∣≤2×105，其中 ∣Si∣∣Si∣ 表示第 ii 个字符串的长度。
输出格式
输出一行一个字符串，表示字典序最小的排队情况。
输入样例
3 111 000 101输出样例
000101111说明
字典序最小的排队应该是 S2S3S1，形成的队伍为 000101111。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Main { static Map<Integer, Integer> map=new HashMap<Integer, Integer>(); static int N=2*100010,idx;//res=0; static Integer a[]=new Integer[N]; static String stringa[]=new String[N]; // static Node node[]=new Node[N]; // static boolean f[]=new boolean[N]; public static void main(String[] args) throws IOException { //System.out.println(100); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); //String g[]=br.readLine().split(" "); int len=0; for (int i = 0; i < n; i++) { String s=br.readLine();//这里不能赋值给int 排序 因为可能超出int范围 stringa[i]=s; } Arrays.sort(stringa, 0, n,(a,b)->{ return (a+b).compareTo(b+a); }); for (int i = 0; i < n; i++) { System.out.print(stringa[i]); } } }