首页 > 8.14 荣耀-通软笔试
头像
helloRachel
编辑于 2021-08-15 20:54
+ 关注

8.14 荣耀-通软笔试

荣耀

笔试 8.14

  1. 题目将字母分为高中低三个等级,输入一个字符串,将三个等级的字母分开,然后排序。

    我的思路:用三个动态字符串StringBuilder分别存储三个等级的字符,然后通过Arrays.sort对每个等级的字符排序,所以需要提前将sb类型转为char数组,最后输出字符串。用String.valueOf(char[])转字符数组为字符串

    import java.util.Arrays;
    import java.util.Scanner;
    
    /**
     * 题目将字母分为高中低三个等级,输入一个字符串,将三个等级的字母分开,然后排序
     */
    public class Solution3 {
        public static String high = "bdfhkl";
        public static String mid = "aceimnorstuvwxz";
        public static String low = "gjqpy";
    
        public static void mySort(String str) {
            // 需要将字符串分组
            // 需要对组内字符进行排序
            StringBuilder highSb = new StringBuilder();
            StringBuilder midSb = new StringBuilder();
            StringBuilder lowSb = new StringBuilder();
            for (char c : str.toCharArray()) {
                if (high.contains(Character.toString(c)))
                    highSb.append(c);
                if (mid.contains(Character.toString(c)))
                    midSb.append(c);
                if (low.contains(Character.toString(c)))
                    lowSb.append(c);
            }
            char[] h = highSb.toString().toCharArray();
            char[] m = midSb.toString().toCharArray();
            char[] l = lowSb.toString().toCharArray();
    
            Arrays.sort(h);
            if (h.length == 0) System.out.println("null");
            else System.out.println(String.valueOf(h));
    
            Arrays.sort(m);
            if (m.length == 0) System.out.println("null");
            else System.out.println(String.valueOf(m));
    
            Arrays.sort(l);
            if (l.length == 0) System.out.println("null");
            else System.out.println(String.valueOf(l));
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str = sc.next();
            mySort(str);
        }
    }

    学习了评论区同学的代码,有两点get到的小知识:

  • 对于这种排序问题可以使用优先队列,这个我平时不习惯用,但是看了一下人家的代码,似乎很好用。PriorityQueue<T>是用的二叉树实现的小顶堆,可以通过add(t)添加一个节点,poll()删除堆顶元素,时间复杂度O(logN);peek()检索堆顶元素-不删除,复杂度O(1);要生成大顶堆可以使用new PriorityQueue<>(Collections.reverseOrder())
  • switch和if-else比较:二者根本区别是switch会生成一个“跳表”,跳表的索引号和case的值相同,直接通过访问跳表的索引号就可以直接定位到相应的分支,这是一种空间换时间的做法;而if-else是逐个判断,定位到相应分支的做法。相比之下,if-else结构更加灵活,适合处理非【常量】的判断条件;switch定位分支较快,一般用于判断数据不多,并且数据类型是char、int等类型比较适合。switch if-else 参考
  1. 啊~~就是根据需求排序,主要复杂的地方在于特征太多,包括歌曲名、类别名、操作(听完/中断)、评分。

    我的思路:创建了一堆map来存储各种关系对,包括歌曲对类别;类别对歌曲;歌曲对操作;歌曲对分数等,具体看我的代码。也可以换成其他的数据结构,因为时间问题就拿map存储了,比较好理解,写代码也快。

    有个麻烦的地方就是对map进行排序,自定义的排序传入的类型只能是List的,因此我把map的每一个entry作为list的元素,然后自定义排序。

    样例没有全对,通过了85.71%,没时间检查了~~如果有大佬发现问题的话,请指正。

    import java.util.*;
    
    /**
     * 根据习惯,判断喜好,排序
     * <p>
     * 四种分类:Pop Blue  Rock UnknownStyle
     * <p>
     * I 标识:导入音乐库,即音乐集合
     * P 标识:完整播放
     * B 标识:中断播放
     * <p>
     * 用户习惯
     * 听完 +3
     * 中断 -2
     * 连续听完,同类其他+1
     * 连续中断,同类其他-1
     * <p>
     * 输出:按照喜好度由高到低排序;同分数按照字母序由小到大排序
     */
    public class Solution2 {
        public static void print(String[] array) {
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            // 为歌曲和分类建立一个map, 分类对应的个数列表
            Map<String, String> songLabel = new HashMap<>();            // key=song value=label
            Map<String, ArrayList<String>> songMap = new HashMap<>();   // key=label value={songs}
            // 为操作建立一个数组,存在重复听歌,key是song,value是ops
            ArrayList<String[]> ops = new ArrayList<>();                // key=song,value=ops
            // 为分类建立一个map,用于存储该分类总分数,如果当前分类分数为0,key为分类名,value为XXX
            Map<String, Integer> labelsScore = new HashMap<>();              // key=label,value=score
            // 为歌曲建立一个map,用于存储歌曲的分数,key为歌曲名,value为分数
            Map<String, Integer> songScores = new HashMap<>();              // key=song,label=score
            // 键盘读取相关信息
            Scanner in = new Scanner(System.in);
            while (in.hasNextLine()) {
                String line = in.nextLine();
    //            if (line.isEmpty()) break;
                String[] temp = line.split(" ");
                if (temp[0].equals("I")) {
                    // 歌曲,分类
                    songLabel.put(temp[1], temp[2]);
                    // 分类,歌曲
                    ArrayList<String> songs = new ArrayList<>();
                    if (songMap.getOrDefault(temp[2], null) != null) {
                        songs = songMap.get(temp[2]);
                    }
                    songs.add(temp[1]);
                    songMap.put(temp[2], songs);
    
                    labelsScore.put(temp[2], 0);// 分类,0分
                    songScores.put(temp[1], 0);// 歌曲,0分
                } else {
                    ops.add(temp);
                }
            }
            // 遍历听歌行为,判断听歌状态P或者B;
            for (int i = 0; i < ops.size(); i++) {
    //            print(ops.get(i));
                String op = ops.get(i)[0];
                String song = ops.get(i)[1];
                String label = songLabel.get(song);
                if (op.equals("P")) {
                    // 其他的是否要+1,该分类大于0,说明之前喜欢同类的歌曲,其他歌曲+1
                    if (!label.equals("UnknownStyle") && labelsScore.get(label) > 0) {
                        ArrayList<String> songs = songMap.get(label);
                        for (String s : songs) {
                            if (!s.equals(song)) {
                                songScores.put(s, songScores.get(s) + 1);
    //                            System.out.println(s + " 同类歌曲喜爱 ");
                            }
                        }
                    }
                    // 当前歌曲听完了,+3
                    songScores.put(song, songScores.get(song) + 3);
                    labelsScore.put(label, labelsScore.get(label) + 3);
    //                System.out.println("喜爱" + song);
                } else { // 没听完,-2
    
                    // 其他的是否要-1
                    if (!label.equals("UnknownStyle") && labelsScore.get(label) < 0) {
                        ArrayList<String> songs = songMap.get(label);
                        for (String s : songs) {
                            if (!s.equals(song)) {
                                songScores.put(s, songScores.get(s) - 1);
    //                            System.out.println(s + " 同类歌曲中断 ");
                            }
                        }
                    }
    
                    songScores.put(song, songScores.get(song) - 2);
                    labelsScore.put(label, labelsScore.get(label) - 2);
    //                System.out.println("中断" + song);
    
                }
            }
    //        System.out.println("歌曲的分数:" + songScores);
    //        System.out.println("类别的分数:" + labelsScore);
    //        System.out.println("歌曲-类别:" + songLabel);
    //        System.out.println("类别-歌曲:" + songMap);
            // 按照歌曲分数排序
            List<Map.Entry<String, Integer>> list = new ArrayList<>(songScores.entrySet());
    
            Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                    if (o1.getValue() == o2.getValue())
                        return o1.getKey().compareTo(o2.getKey());
                    return o2.getValue() - o1.getValue();
                }
            });
    //        System.out.println(list);
            for (int i = 0; i < list.size(); i++) {
                String song = list.get(i).getKey();
                String label = songLabel.get(song);
                System.out.println(song + " " + label);
            }
    
        }
    }

    15%样例没通过的原因可能在打分这里,题目中有个条件是“若这首歌与上次完整听完的歌是一个流派,则该流派内除了这首歌的喜好度+1”,这个上次,应该需要一个变量来暂存上一首歌的类别。这里的代码片段截图自评论中同学的代码:
    图片说明

  2. 切水果~~给定一个40*50的方格,每个位置有水果,只能横竖左右切,求最少的切割次数。
    图片说明
    我的思路就是贪心法,对四个方向的节点计数,然后按照由大到小的顺序排序,逐个切除,直到水果数量为0,结束。其中存在一个问题,就是最多的水果数相同的时候,需要选择哪个方向呢?如下图所示:有三条线都有两个节点,如果最先删除了【1】那么之后还需要切两刀才可以。先切【2】【3】的效果相同。那么我的思路就是需要对相同大小的线

全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐