集合框架（数组，Arrays.sort，list,map,set,stack,queue）蓝桥杯习题

前言(基本知识)

List集合

有序，接口，

List<引用数据类型> list=new ArrayList<>();

方法： add()  size()  get()//索引index从0开始，返回对应的值

isEmpty()判断是否包含该元素,不包含返回true，包含返回false

contains() // 是否包含指定元素 ,包含true  remove()//删除并返回被删除的元素

数组，集合排序

Arrays.sort() //默认升序，定义数组使用引用数据类型           

Collections.sort() 

Set集合

不允许重复，无序

方法： Set<Integer> set=new HashSet<>();

常用于判断重复元素时

add()  size()  contains() // 是否包含指定元素 ,包含true 

remove()//删除元素,删除成功返回true

clear() //清除所有元素

Map集合

散列表（key-value）映射，无序

方法：Map<Integer,Integer> map=new HashMap<>();

put(键,值)   get(键)//对应键的值，没有返回null  size()

entrySet() //map集合的每个键值转换entry对象，返回entry对象组成的Set集合。

for(entry<Integer,Integer> entry map.entrySet()){

//遍历map集合的一种方法（模板），通过map集合的entrySet方法将map集合转化成一个entry类型的数组

         System.out.print(map.getKey()+" " map.getValue());

}

getOrDefault(键,值)//获取键对应的值，找不到返回默认值

Stack集合

先进后出

方法：Stack<Integer> stack=new Stack<>();

pop()//删除顶部元素  peek();//查看顶部元素并返回   push()//从顶部压入 

isEmpty();//判断是否为空

Queue集合

先进先出

方法：Queue<Integer> queue=new Linkedlist<>();

是 boolean add();//队尾压入元素，并返回是否压入成功 poll()//删除并返回被删除的元素

peek()//查看队尾元素  isEmpty()//队列是否为空

编号1389二分查找数组元素

题目描述

给定一个数组，其采用如下代码定义：

int data[200];
for(i = 0 ; i < 200 ; i ++）data[i] = 4 * i + 6;

先给定某个数（在 data 数组中），请你求出它在数组中的位置。

输入描述

输入一个待查找的整数（该整数一定在数组data中）。

输出描述

输出该整数在数组中的指标。

输入输出样例

示例 1

输入

262

输出

64

示例 2

输入

438

输出

108

代码

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int []data=new int[200];for(int i=0;i<200;i++){data[i]=4*i+6;}int a=scan.nextInt();int c=0;for(int i=0;i<200;i++){if(a==data[i]){c=i;}}System.out.println(c);scan.close();}
}

编号539明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入描述

第 1 行为 1 个正整数，表示所生成的随机数的个数：N。

第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。

输出描述

输出 2 行，第 1 行为 1 个正整数 M，表示不相同的随机数的个数。

第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

输入输出样例

示例 1

输入

10
20 40 32 67 40 20 89 300 400 15

输出

8
15 20 32 40 67 89 300 400

代码

直接使用list.contain()也能完成去重操作

package lanqiaoyun;
import java.util.*;public class jihe539 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int []arr=new int [n];List<Integer> list=new ArrayList<>();for(int i=0;i<n;i++) {arr[i]=scan.nextInt();//System.out.print(list);}for(int i=0;i<n;i++) {if(!list.contains(arr[i])) {list.add(arr[i]);}}Collections.sort(list);System.out.println(list.size());for(int x:list) {System.out.print(x+" ");}}}

使用set.contain()

package lanqiaoyun;
import java.util.*;public class jihe539 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int []arr=new int [n];List<Integer> list=new ArrayList<>();Set<Integer> set=new HashSet<>();for(int i=0;i<n;i++) {arr[i]=scan.nextInt();//System.out.print(list);}for(int i=0;i<n;i++) {if(!set.contains(arr[i])) {set.add(arr[i]);list.add(arr[i]);}}Collections.sort(list);System.out.println(list.size());for(int x:list) {System.out.print(x+" ");}}}

编号map

问题描述

输入一个数字n（n<=1e5），然后输入一个长度为n的数组an(-1e9<=ai<=1e9),请你输出出现频率最大的数。如果由多个数频率相同，按从小到大依次输出。

示例：

输入 5  1 1 2 2 0

输出 1 2

代码

package lanqiaoyun;
import java.util.*;
import java.util.Map.Entry;public class teshu {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();Map<Integer,Integer> map=new HashMap<>();/*for(Entry <Integer,Integer> entry:map.entrySet()) {System.out.println(entry.getKey()+" "+entry.getValue());}System.out.println(max);for(Entry <Integer,Integer> entry:map.entrySet()) {if( map.entryValue()==max) {//System.out.print(a[i]+" ");}}*/for(int i=0;i<n;i++) {int a=scan.nextInt();map.put( a, map.getOrDefault(a, 0)+1);}long max=Integer.MIN_VALUE;for(Entry<Integer, Integer> entry:map.entrySet()) {if(entry.getValue()>max) {max=entry.getValue();}}List<Integer> list=new ArrayList<>();for(Entry<Integer, Integer> entry:map.entrySet()) {if(entry.getValue()==max) {list.add(entry.getKey());//	System.out.print(entry.getKey()+" ");}}Collections.sort(list);for(int i:list) {System.out.print(i+" ");}}}

编码2490小蓝的字符串

问题描述

小蓝有一个长度为 n 的括号串，括号串仅由字符 ( 、 ) 构成，请你帮他判断一下该括号串是否合法，合法请输出 Yes ，反之输出 No 。

合法括号序列：

1. 空串是合法括号序列。

2. 若 s 是合法括号序列，则 ( s ) 也是合法括号序列。

3. 若 s,t 都是合法括号序列，则 st 也是合法括号序列。

例如 ()() ， (()) ， (())() 均为合法括号序列。

输入格式

第一行包含一个正整数 n ，表示括号串的长度。

第二行包含一个长度为 n 的括号串。

输出格式

输出共 11 行，若括号串合法请输出 Yes ，反之输出 No 。

样例输入1

10
(()(()))()

样例输出1

Yes

样例输入2

5
()()(

样例输出2

No

代码 

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();char []a=scan.next().toCharArray();Stack<Character> stack=new Stack<>();int count=n;for(int i=0;i<n;i++) {if(a[i]=='(') {stack.push(a[i]);}else if(a[i]==')') {if(!stack.isEmpty()) {stack.pop();count=count-2;	}else {//System.out.println("No");break;}}}if(stack.isEmpty()&&count==0) {System.out.println("Yes");}else {System.out.println("No");}}}

编号1265排序

题目描述

给定一个长度为 N 的数组 A，请你先从小到大输出它的每个元素，再从大到小输出它的每个元素。

输入描述

第一行包含一个整数 N。

第二行包含 N 个整数a1​,...,an​，表示数组 A 的元素。

1≤N≤5×105,−109≤ai​≤109。

输出描述

输出共两行，每行包含 N 个整数，表示答案。

输入输出样例

示例 1

输入

5
1 3 2 6 5

输出

1 2 3 5 6
6 5 3 2 1

代码

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);long n=scan.nextLong();List<Long> list=new ArrayList<>();for(long i=0;i<n;i++){list.add(scan.nextLong());}Collections.sort(list);for(long x:list) {System.out.print(x+" ");}Collections.sort(list,new Comparator<Long>(){@Overridepublic int compare(Long o1, Long o2) {// TODO Auto-generated method stubreturn Long.compare(o2, o1);}});System.out.println(" ");for(long x:list) {System.out.print(x+" ");}}}

编号782拼数

问题描述

给定 n 个正整数a1​,a2​,…,an​，你可以将它们任意排序。

现要将这 n 个数字连接成一排，即令相邻数字收尾相接，组成一个数。

问，这个数最大可以是多少。

输入格式

第一行输入一个正整数 n（1≤n≤20）。

第二行输入 n 个正整数a1​,a2​,…,an​（1≤ai​≤105）。

输出格式

输出一个整数，表示答案。样例输入

3
13 312 343

样例输出

34331213

 代码

package lanqiaoyun;
import java.util.*;public class a782 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();String []str=new String[n];for(int i=0;i<n;i++) {str[i]=scan.next();}Arrays.sort(str,(o1,o2)->(o2+o1).compareTo(o1+o2));StringBuilder st=new StringBuilder();for(String i:str) {st.append(i);}System.out.println(st);/*for(int i=0;i<n;i++) {list.add(scan.nextLong());}/** for(int x:list) {}*/}}

 编号2122数位排序

问题描述

小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当 两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时, 将数值小的排在前面。

例如, 2022 排在 409 前面, 因为 2022 的数位之和是 6, 小于 409 的数位 之和 13 。

又如, 6 排在 2022 前面, 因为它们的数位之和相同, 而 6 小于 2022 。

给定正整数 n,m, 请问对 1 到 n 采用这种方法排序时, 排在第 m 个的元 素是多少?

输入格式

输入第一行包含一个正整数 n 。

第二行包含一个正整数 m 。

输出格式

输出一行包含一个整数, 表示答案。

样例输入

13
5

样例输出

3

代码

import java.util.Scanner;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n = scan.nextInt();int m = scan.nextInt();Integer[] array = new Integer[n];for (int i = 0; i < n; i++) {array[i] = i + 1;}Arrays.sort(array, (o1, o2) -> digitSum(o1) != digitSum(o2) ? digitSum(o1) - digitSum(o2) : o1 - o2);System.out.println(array[m - 1]);scan.close();}private static int digitSum(Integer num) {int ans = 0;while (num > 0) {ans += num % 10;num /= 10;}return ans;}
}

残缺品（通过率有问题）

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...long n=scan.nextLong();long m=scan.nextLong();List<Long> list=new ArrayList<>();for(long i=0;i<n;i++) {list.add(i+1);}Collections.sort(list,new Comparator<Long>() {@Overridepublic int compare(Long o1, Long o2) {// TODO Auto-generated method stubint c=(int) (o2-o1);if(su(o1)>su(o2)) {c=(int) (o1-o2);}else if(su(o1)==su(o2)) {if(o1>o2) {c=(int) (o1-o2);}}return c;}public long su(long x) {long sum=0;while(x!=0) {sum=sum+x%10;x=x/10;}return sum;}});/*for(long x:list) {System.out.print(x+"  ");}*/System.out.println(list.get((int) m-1));}}