桶排序、堆排序、奇偶排序、计数排序、阿坤老师的独特瓷器、封闭图形个数、二进制王国【算法赛】

桶排序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 N100010,idx;//res0; static String s[]new String[N]; static boolean num[]new boolean[N]; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); // int TInteger.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(arrnull|| arr.length0)return; int minzarr[0]; int maxzarr[0]; for (int i 1; i n; i) { minzMath.min(minz, arr[i]); maxzMath.max(maxz, arr[i]); } int bucketnum(maxz-minz)/arr.length1;//至少有一个桶 LinkedListLinkedListInteger buckets new LinkedList(); for (int i 0; i bucketnum; i) { buckets.add(new LinkedList()); } for (int i 0; i n; i) { int uarr[i]; int ind(u-minz)/n; buckets.get(ind).add(u); } for (int i 0; i bucketnum; i) { Collections.sort(buckets.get(i)); } int i0; for(LinkedListInteger 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 N100010,idx;//res0; static String s[]new String[N]; static boolean num[]new boolean[N]; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); // int TInteger.parseInt(br.readLine()); // String g[]br.readLine().split( ); int arr[]{3,6,8,5,90,45,37,67,29,78}; int narr.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 harr[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 largei; int left2*i1,right2*i2; if(leftn a[left]a[large]){ largeleft; } if(rightn a[right]a[large]){ largeright; } if(large!i){ int ta[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 N100010,idx;//res0; 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 brnew BufferedReader(new InputStreamReader(System.in)); int nInteger.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%20),bb(b%20); if(aabb){ return a-b; }else{ if(a%20){ 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 N100010,idx;//res0; static Integer a[]new Integer[N]; static boolean num[]new boolean[N]; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); // int nInteger.parseInt(br.readLine()); // String g[]br.readLine().split( ); int u[]{9,56,75,65,54,33,23}; int zInteger.MIN_VALUE; for (int i 0; i u.length; i) { zMath.max(z, u[i]); } int d[]new int[z1]; for (int i 0; i u.length; i) { d[u[i]]; } int id0; 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 个瓷器每个瓷器都有一个直径和高度。请你帮助阿坤老师计算出他的瓷器收藏中有多少个“独特瓷器”。输入格式输入的第一行包含一个整数 NN1≤N≤1051≤N≤105。接下来的 NN 行每行包含两个整数分别表示瓷器的直径 dd 和高度 hh1≤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 N100010,idx;//res0; //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 brnew BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); //String g[]br.readLine().split( ); for (int i 0; i n; i) { String g[]br.readLine().split( ); int dInteger.parseInt(g[0]),hInteger.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(ij)continue; if(node[i].dnode[j].d node[i].hnode[j].h){ f[i]false; } } } int res0; 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 N100010,idx;//res0; //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 brnew BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); //String g[]br.readLine().split( ); for (int i 0; i n; i) { String g[]br.readLine().split( ); int dInteger.parseInt(g[0]),hInteger.parseInt(g[1]); node[idx]new Node(d, h); } if(n1){ System.out.println(1);return; } Arrays.sort(node,0,n);//先按d降序 h升序 int maxh0,res0; for (int i 0; i n; i) { if(node[i].hmaxh){ res; maxhnode[i].h; } } System.out.println(res); } static class Node implements ComparableNode{ 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(do.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但 14411441所以数字 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×1031≤ai≤1051≤ai​≤105。对于所有评测用例1≤n≤2×1051≤n≤2×1051≤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 MapInteger, Integer mapnew HashMapInteger, Integer(); static int N2*100010,idx;//res0; 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 brnew BufferedReader(new InputStreamReader(System.in)); int nInteger.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 aacal(a),bbcal(b); if(aabb){ 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(n0)return 1; int sum0; while(n0){ summap.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​​ 户家庭。数据范围保证∑i1n∣Si∣≤2×105∑i1n​∣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 MapInteger, Integer mapnew HashMapInteger, Integer(); static int N2*100010,idx;//res0; 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 brnew BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); //String g[]br.readLine().split( ); int len0; for (int i 0; i n; i) { String sbr.readLine();//这里不能赋值给int 排序 因为可能超出int范围 stringa[i]s; } Arrays.sort(stringa, 0, n,(a,b)-{ return (ab).compareTo(ba); }); for (int i 0; i n; i) { System.out.print(stringa[i]); } } }