1、计算集合的并
算法分析
把两个集合都扔去set中，再枚举set中的所有元素
时间复杂度)
Java代码
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Main {
static int N = 10010 * 2;
static Set<Integer> set = new TreeSet<Integer>();
static int[] ans = new int[N];
static int k = 0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
for(int i = 0;i < n;i ++)
set.add(scan.nextInt());
for(int i = 0;i < m;i ++)
set.add(scan.nextInt());
for(Integer item : set)
ans[k ++] = item;
for(int i = 0;i < k;i ++)
{
if(i != k - 1) System.out.print(ans[i] + " ");
else System.out.println(ans[i]);
}
}
}
3、蒜头君学英语
算法分析
由于每个单词的大小写可以看成是等价的，因此来个单词，若单词中某个字符是大写的，统一 +32 变成小写，扔进set中处理
时间复杂度
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
public class Main {
static Set<String> set = new HashSet<String>();
static String get(String word)
{
char[] temp = word.toCharArray();
for(int i = 0;i < temp.length;i ++)
{
if(temp[i] >= 'A' && temp[i] <= 'Z')
temp[i] = (char)((int)(temp[i] + 32));
}
return String.valueOf(temp);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
while(n -- > 0)
{
String[] s1 = br.readLine().split(" ");
int op = Integer.parseInt(s1[0]);
String word = get(s1[1]);
if(op == 0)
{
set.add(word);
}
else
{
if(!set.contains(word)) System.out.println("No");
else System.out.println("Yes");
}
}
}
}
4、蒜头君面试
算法分析
输入的是n个int范围以内的数，则不能直接刷数组，需要开map存储每个数出现的次数，取出现次数最高且数最大的
时间复杂度
Java代码
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
static int N = 100010;
static Map<Integer,Integer> map = new HashMap<Integer,Integer>();
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 0;i < n;i ++)
{
int x = scan.nextInt();
map.put(x, map.getOrDefault(x, 0) + 1);
}
int res = 0;
for(Map.Entry<Integer, Integer> entry : map.entrySet())
{
res = Math.max(res, entry.getValue());
}
int value = Integer.MIN_VALUE;
for(Map.Entry<Integer, Integer> entry : map.entrySet())
{
if(entry.getValue() == res)
{
value = Math.max(value, entry.getKey());
}
}
System.out.println(value + " " + res);
}
}
5、收藏古币
算法分析
对每个盒子的古币进行从小到大排序，以a + " " + b + " " + c + " " + d + " " + e的格式放在set中
时间复杂度
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Main {
static int N = 100010;
static Set<String> set = new HashSet<String>();
static int[] a = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while(T -- > 0)
{
String[] s1 = br.readLine().split(" ");
int n = s1.length;
for(int i = 0;i < n;i ++) a[i] = Integer.parseInt(s1[i]);
Arrays.sort(a,0,n);
String s = "";
for(int i = 0;i < n;i ++)
{
if(i != n - 1) s += a[i];
else s += a[i] + " ";
}
if(set.contains(s)) System.out.println("pass");
else
{
set.add(s);
System.out.println("buy");
}
}
}
}
