【笔试复盘】2021.8.14-荣耀机试

1.将字母分为3个等级输出

import java.lang.*;
import java.util.*;

public class Main1 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input=sc.nextLine();
        getResult(input);
    }

    public static void getResult(String str){
        HashSet<Character> high=new HashSet<>();
        HashSet<Character> mid=new HashSet<>();
        HashSet<Character> low=new HashSet<>();
        char[] char1={'b','d','f','h','k','l'};
        for(int i=0;i<char1.length;i++){
            high.add(char1[i]);
        }
        char[] char2={'a','c','e','i','m','n','o','r','s','t','u','v','w','x','z'};
        for(int i=0;i<char2.length;i++){
            mid.add(char2[i]);
        }
        char[] char3={'g','j','p','q','y'};
        for(int i=0;i<char3.length;i++){
            low.add(char3[i]);
        }
        String[] result=new String[3];
        int len=str.length();

        StringBuffer res1=new StringBuffer();
        StringBuffer res2=new StringBuffer();
        StringBuffer res3=new StringBuffer();
        for(int i=0;i<len;i++){
            char ch=str.charAt(i);
            if(high.contains(ch)){
                res1.append(ch);
            }
            else if(mid.contains(ch)){
                res2.append(ch);
            }
            else if(low.contains(ch)){
                res3.append(ch);
            }
        }
        result[0]=res1.toString();
        result[1]=res2.toString();
        result[2]=res3.toString();
        for(int i=0;i<3;i++){
            if(result[i].length()==0){
                System.out.println("null");
            }
            else{
                System.out.println(sort(result[i]));
            }
        }
    }

    public static String sort(String str){
        ArrayList<Character> list=new ArrayList<>();
        for(int i=0;i<str.length();i++){
            list.add(str.charAt(i));
        }
        Collections.sort(list);
        StringBuffer res=new StringBuffer();
        for(int i=0;i<list.size();i++){
            res.append(list.get(i));
        }
        return res.toString();
    }
}

2.推荐歌曲

每首歌属于一个流派，如pop/jazz等，不清楚流派的为UnKnown Style。输入有三种情况：

I songName songStyle ： 表示将流派为songStyle的、歌名为songName的歌加载到曲库。
P songName : 表示用户完整听完了名为songName的歌。
B songName : 表示用户切歌了名为songName的歌。

如若用户完整听完一首歌，则对这首歌的喜好度+3，如若这首歌与上次完整听完的歌是一个流派，则该流派内除了这首歌的喜好度+1。如若用户切了一首歌，则对这首歌的喜好度-2，如若这首歌与上次切掉的歌是一个流派，则该流派内除了这首歌的喜好度-1。按喜好度顺序输出歌名和它的流派，若喜好度相同，按字典序排序。

 这道题目看起来复杂，起始就是根据题意模拟即可，关键在于设计双向映射的数据结构。一共用到了3个map，根据需要相互转换 

输入：
I MusicA Pop
I MusicB Pop
I MusicC Blue
I MusicD Blue
I MusicE UnkownStyle
I MusicF Pop
P MusicA
P MusicB
B MusicC
P MusicF
B MusicD
B MusicE

输出：
MusicA Pop
MusicB Pop
MusicF Pop
MusicD Blue
MusicE UnkownStyle
MusicC Blue

3.切水果的最少次数

import java.util.*;

public class Main3 {
    static Map<String,Integer> map;
    static int[][] a;
    static int step;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        map = new HashMap<>();
        a = new int[n][2];
        step = Integer.MAX_VALUE;
        for(int i = 0;i<n;i++){
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        Queue<List<Integer> > q = new LinkedList<>();
        List<Integer> root =  new ArrayList<>();
        for(int i=0;i<n;i++){
            root.add(i);
        }
        dfs(0,root);
        System.out.println(step);
    }

    public static void dfs(int cnt, List<Integer> list){
        if(cnt>step)
            return;
        if(map.containsKey(list.toString())){
            if(map.get(list.toString())<cnt)
                return;
        }

        if(list.size()==0)
            step = Math.min(step,cnt);
        List<Integer> list1,list2,list3,list4;
        Queue<List<Integer>> q= new PriorityQueue<>(new Comparator<List<Integer>>() {
            public int compare(List<Integer> o1, List<Integer> o2) {
                return o1.size()-o2.size();
            }
        });
        for(int e:list){
            int x = a[e][0];
            list1 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]!=x)
                    list1.add(ee);
            int y = a[e][1];
            list2 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][1]!=y)
                    list2.add(ee);
            int xy = a[e][0]-a[e][1];
            list3 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]-a[ee][1]!=xy)
                    list3.add(ee);
            int yx = a[e][0]+a[e][1];
            list4 = new ArrayList<>();
            for(int ee:list)
                if(a[ee][0]+a[ee][1]!=yx)
                    list4.add(ee);
            q.add(list1);
            q.add(list2);
            q.add(list3);
            q.add(list4);
        }
        while(q.size()!=0){
            List<Integer> list5 = q.poll();
            dfs(cnt+1,list5);
        }
        map.put(list.toString(),cnt);
    }

}