荣耀秋招机试三道编程题（2021-08-14）
恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】
点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝
提示
- 类似华为，甚至有出现过之前的原题。
- 难度不大。
第一道：将字母分为3个等级输出（100%）
题目描述
将字母分为高中低三个等级，输入一个字符串，将三个等级的字母分开，然后排序。
思路解析
方法一：
三个按字典序排序的优先队列即可·
方法二：
用三个动态字符串StringBuilder分别存储三个等级的字符，然后通过Arrays.sort对每个等级的字符排序，所以需要提前将sb类型转为char数组，最后输出字符串。
对于这种排序问题可以使用优先队列，这个我平时不习惯用，但是看了一下人家的代码，似乎很好用。PriorityQueue是用的二叉树实现的小顶堆，可以通过add(t)添加一个节点，poll()删除堆顶元素，时间复杂度O(logN);peek()检索堆顶元素-不删除，复杂度O(1)；要生成大顶堆可以使用new PriorityQueue<>(Collections.reverseOrder())。
switch和if-else比较：二者根本区别是switch会生成一个“跳表”，跳表的索引号和case的值相同，直接通过访问跳表的索引号就可以直接定位到相应的分支，这是一种空间换时间的做法；而if-else是逐个判断，定位到相应分支的做法。相比之下，if-else结构更加灵活，适合处理非【常量】的判断条件；switch定位分支较快，一般用于判断数据不多，并且数据类型是char、int等类型比较适合。
参考代码：
方法一
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
PriorityQueue<Character> q1 = new PriorityQueue<>();
PriorityQueue<Character> q2 = new PriorityQueue<>();
PriorityQueue<Character> q3 = new PriorityQueue<>();
for(int i=0;i<s.length();i++){
switch (fun(s.charAt(i))){
case 1:q1.add(s.charAt(i));break;
case 2:q2.add(s.charAt(i));break;
case 3:q3.add(s.charAt(i));break;
default:break;
}
}
if(q1.size()!=0){
while(q1.size()!=0)
System.out.print(q1.poll());
System.out.println();
}else
System.out.println("null");
if(q2.size()!=0){
while(q2.size()!=0)
System.out.print(q2.poll());
System.out.println();
}else
System.out.println("null");
if(q3.size()!=0){
while(q3.size()!=0)
System.out.print(q3.poll());
System.out.println();
}else
System.out.println("null");
}
public static int fun(char c){
switch (c){
case 'b':
case 'h':
case 'f':
case 'k':
case 'l':
case 'd':
return 1;
case 'g':
case 'j':
case 'p':
case 'q':
case 'y':
return 3;
default:
return 2;
}
}
}
方法二
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);
}
}
// 关注TechGuide！ 大厂笔经面经闪电速递！
第二道： 推荐歌曲（100%）
题目描述
每首歌属于一个流派，如pop/jazz等，不清楚流派的为UnKnown Style。
输入有三种情况：
I songName songStyle ： 表示将流派为songStyle的、歌名为songName的歌加载到曲库。
P songName : 表示用户完整听完了名为songName的歌。
B songName : 表示用户切歌了名为songName的歌。
如若用户完整听完一首歌，则对这首歌的喜好度+3，如若这首歌与上次完整听完的歌是一个流派，则该流派内除了这首歌的喜好度+1。
如若用户切了一首歌，则对这首歌的喜好度-2，如若这首歌与上次切掉的歌是一个流派，则该流派内除了这首歌的喜好度-1。
按喜好度顺序输出歌名和它的流派，若喜好度相同，按字典序排序。
思路解析
这道题目看起来复杂，起始就是根据题意模拟即可，关键在于设计双向映射的数据结构。一共用到了3个map，根据需要相互转换。
参考代码
import java.util.*;
//Map<String,List<string>> map; 表示一个流派下有哪些歌
//Map<String,String> map2; 表示一首歌属于哪个流派
//Map<String,Integer> map3; 表示歌的分数</string>
public class Main2 {
static class Song{
String name;
String lib;
int point;
public Song(String name, String lib,int point) {
this.name = name;
this.lib = lib;
this.point = point;
}
}
static Map<String,List<String>> map;//lib - songs
static Map<String,String> map2;//song - lib
static Map<String,Integer> map3;//song - points
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
map = new HashMap<>();
map2 = new HashMap<>();
map3 = new HashMap<>();
String lastP ="";
String lastB = "";
while(scanner.hasNextLine()){
String s = scanner.nextLine();
if(s.equals(""))
break;
String type = s.split(" ")[0];
if(type.equals("I")){
List<String> list = map.getOrDefault(s.split(" ")[2], new ArrayList<>());
list.add(s.split(" ")[1]);
map.put(s.split(" ")[2],list);
map2.put(s.split(" ")[1],s.split(" ")[2]);
map3.put(s.split(" ")[1],0);
}else if(type.equals("P")){
String name = s.split(" ")[1];
map3.put(name,map3.get(name)+3);
if(map2.get(name).equals(lastP)){
String lib = map2.get(name);
for(String songNames:map.get(lib)){
if(!songNames.equals(name))
map3.put(songNames,map3.get(songNames)+1);
}
}
lastP = map2.get(name);
}else{
String name = s.split(" ")[1];
map3.put(name,map3.get(name)-2);
if(map2.get(name).equals(lastB)){
String lib = map2.get(name);
for(String songNames:map.get(lib)){
if(!songNames.equals(name))
map3.put(songNames,map3.get(songNames)-1);
}
}
lastB = map2.get(name);
}
}
Queue<Song> q = new PriorityQueue<>(new Comparator<Song>() {
<a href="/profile/992988" data-card-uid="992988" class="js-nc-card" target="_blank" from-niu="default">@Override
public int compare(Song o1, Song o2) {
if(o1.point==o2.point)
return o1.name.compareTo(o2.name);
return -o1.point + o2.point;
}
});
for(String key:map3.keySet())
q.add(new Song(key,map2.get(key),map3.get(key)));
while(q.size()!=0){
Song song = q.poll();
System.out.println(song.name+" "+song.lib);
}
}
}
// 关注TechGuide！ 大厂笔经面经闪电速递！
第三道：切水果
题目描述
在一个40*50的方格上，有若干个水果，可以横向/纵向/斜向（斜率为±1）4个角度消去一条直线上的水果，问至少需要几刀可以全部切除。
参考代码
贪心
import java.util.*;
public class MainF {
static Map<String,Integer> map;
static int[][] a;
static int step;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
map = new HashMap<>();
a = new int[n][2];
step = Integer.MAX_VALUE;
for(int i = 0;i<n;i++){
a[i][0] = scanner.nextInt();
a[i][1] = scanner.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>>() {
<a href="/profile/992988" data-card-uid="992988" class="js-nc-card" target="_blank" from-niu="default">@Override
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);
}
}
// 关注TechGuide！ 大厂笔经面经闪电速递！
恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。