第12章 常用C ++ STL

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");
            }
        }
    }
}