8.14 荣耀-通软笔试
荣耀
笔试 8.14
题目将字母分为高中低三个等级，输入一个字符串，将三个等级的字母分开，然后排序。
我的思路：用三个动态字符串
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 参考
啊~~就是根据需求排序，主要复杂的地方在于特征太多，包括歌曲名、类别名、操作（听完/中断）、评分。
我的思路：创建了一堆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”，这个上次，应该需要一个变量来暂存上一首歌的类别。这里的代码片段截图自评论中同学的代码：
切水果~~给定一个
40*50的方格，每个位置有水果，只能横竖左右切，求最少的切割次数。
我的思路就是贪心法，对四个方向的节点计数，然后按照由大到小的顺序排序，逐个切除，直到水果数量为0，结束。其中存在一个问题，就是最多的水果数相同的时候，需要选择哪个方向呢？如下图所示：有三条线都有两个节点，如果最先删除了【1】那么之后还需要切两刀才可以。先切【2】【3】的效果相同。那么我的思路就是需要对相同大小的线
莉莉丝游戏公司福利 40人发布
