网易互娱服务端研发 4.18笔试 3点-5点场（求第二题解）
4.18 场次的网易后台开发，大家的笔试情况如何？我的题目是
1. 寻宝游戏，'N','E','S','T' 卡牌收集
2. 据点寻宝
3. 前缀热点词汇查询
"just","java","jar","jack","jackson"4.同一陆地的国家判断。
1.第一题，怎么配，让更多的人收集齐套牌，考试时候没想通，只通过了76%，考完想想，发现应该是先配卡池中最多的开，卡池里面最少的卡应该最后用。（不知道对不对）,欢迎大佬指正。
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
public class WangYi1 {
public static int solve (char[] person_cards, char[] hide_cards) {
// write code here
//HashMap<Character,Integer> mapPlayer = new HashMap<>(); //玩家手中的
//HashMap<Character,Integer> mapHide = new HashMap<>(); //散落各地的
int result = 0;
//Card[] player = {new Card('N'),new Card('E'),new Card('S'),new Card('T')};
HashMap<Character,Integer> map = new HashMap<>();
Card[] hide = {new Card('N'),new Card('E'),new Card('S'),new Card('T')};
//将手牌和卡池情况读入数组
/* for (int i = 0; i < person_cards.length; i++) {
switch (person_cards[i]){
case 'N': player[0].setCount(player[0].getCount()+1);
case 'E': player[1].setCount(player[1].getCount()+1);
case 'S': player[2].setCount(player[2].getCount()+1);
case 'T': player[3].setCount(player[3].getCount()+1);
}
}*/
for (int i = 0; i < person_cards.length; i++) {
char c = person_cards[i];
map.put(c, map.getOrDefault(c,0) + 1);
}
for (int i = 0; i < hide_cards.length; i++) {
switch (hide_cards[i]){
case 'N': hide[0].setCount(hide[0].getCount()+1); break;
case 'E': hide[1].setCount(hide[1].getCount()+1); break;
case 'S': hide[2].setCount(hide[2].getCount()+1); break;
case 'T': hide[3].setCount(hide[3].getCount()+1); break;
}
}
//先从卡池中挑数量最小的取与人匹配
/*
顺序匹配可能存在的问题
N 10 E 4 S 100 T 4
卡池 N 100 E 4 S 100 T 4
顺序匹配的话，此时N用完了E和T,但是如果先匹配E和T，就可以多匹配几个人
*/
//先对卡池排序
Arrays.sort(hide, new Comparator<Card>() { @Override public int compare(Card o1, Card o2) {
if(o1.getCount() != o2.getCount())
return o1.getCount() - o2.getCount();
else
return o1.getCard() < o2.getCard() ? -1 : 1;
}
});
//从最小的开始配神龙
//即为先用卡池数量充足的卡
for (int i = 0; i < hide.length; i++) {
char card = hide[i].getCard();
int userCard = map.get(card);
int[] nums = new int[3];
int index = 0;
for (int j = 0; j <hide.length ; j++) {
if(hide[j].getCard() == card)
continue;
nums[index++] = hide[j].getCount();
}
int tmp = Math.min(Math.min(Math.min(userCard,nums[0]),nums[1]),nums[2]);
result += tmp;
//删卡操作
//除了本卡，其余三个都删
for (int j = 0; j < hide.length; j++) {
if(hide[j].getCard() == card)
continue;
hide[j].setCount(hide[j].getCount() - tmp);
}
}
return result;
}
public static void main(String[] args) {
char[] person_cards = {'N','N','N','N','N','N','N','N','N','N', //10
'E','E','E','E',
'S','S','S','S','S','S','S','S','S','S', //10
'T','T','T','T'};
char[] hide_cards = {'N','N','N','N','N','N','N','N','N','N', //10
'E','E','E','E',
'S','S','S','S','S','S','S','S','S','S', //10
'T','T','T','T'};
int result = solve(person_cards, hide_cards);
}
}
class Card{
private char card; //卡的类型
private int count; //卡池数量
public Card(char card) {
this.card = card;
this.count = 0;
}
public char getCard() {
return card;
}
public void setCard(char card) {
this.card = card;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
} 2.第二题完全没看懂题目的意思，哭了。蹲一个大佬指导我思路 3. 我才用了最蠢的解法，完全无视注解的要求查询O1，侥幸AC了
import java.util.ArrayList;
import java.util.HashMap;
public class WangYi3 {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 用户名搜索
* @param users string字符串一维数组 入库的用户名
* @param hot int整型一维数组 对应用户名的热度值，数组长度与users相同
* @param keyword string字符串 搜索的用户名
* @return string字符串ArrayList<ArrayList<>>
*/
public static ArrayList<ArrayList<String>> search (String[] users, int[] hot, String keyword) {
// write code here
//热度键不重复
HashMap<Integer, String> map = new HashMap<>();
for (int i = 0; i < hot.length; i++) {
map.put(hot[i],users[i]);
}
//找一个记录索引的集合
ArrayList<ArrayList<Integer>> listKey = new ArrayList<>();
ArrayList<ArrayList<String>> searchResult = new ArrayList<>();
for (Integer hotVal : map.keySet()) {
for (int i = 1; i <= keyword.length(); i++) {
//包含输入得到关键字
if(listKey.size() < i)
listKey.add(new ArrayList<>());
if(map.get(hotVal).indexOf(keyword.substring(0,i)) == 0){
listKey.get(i-1).add(hotVal);
}
}
}
//输出
for (int i = 0; i < listKey.size(); i++) {
ArrayList<Integer> integers = listKey.get(i);
integers.sort((x,y)->(y-x));
searchResult.add(new ArrayList<>());
for (Integer hotVal : integers) {
if(searchResult.get(i).size() >= 3)
break;
searchResult.get(i).add(map.get(hotVal));
}
}
return searchResult;
}
public static void main(String[] args) {
//String[] users = {"just","java","jar","jack","jackson"};
String[] users = {"just","java","jar","jack","jackson"};
int[] hot = {1,5,3,4,2};
String keyword = "jabk";
ArrayList<ArrayList<String>> search = search(users, hot, keyword);
}
} 4. 简单的无向图求连通分量，我的代码有很多冗余。还是练习的太少了。侥幸AC import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class WangYi4 {
static boolean[] marked;
static int[] id;
static int count; //连通分量计数
public static boolean[] mainlandCheck (int num, int[][] country, int[][] check) {
// write code here
if(num == 0)return new boolean[0];
//创建无向图的邻接表
HashMap<Integer, List<Integer>> map = new HashMap<>();
marked = new boolean[num];
id = new int[num];
count = 1; //连通分量计数 从1开始
boolean[] result = new boolean[check.length];
//写入所有的邻接信息
for (int i = 0; i < country.length; i++) {
int[] connect = country[i];
if(map.get(connect[0]) == null){
map.put(connect[0],new ArrayList<>());
}
if(map.get(connect[1]) == null){
map.put(connect[1],new ArrayList<>());
}
map.get(connect[0]).add(connect[1]);
map.get(connect[1]).add(connect[0]);
}
//深度优先搜索，查找连通分量
for(int key : map.keySet()){
if(!marked[key]){
dfs(map,key);
count++;
}
}
for (int i = 0; i < check.length; i++) {
if(id[check[i][0]] == id[check[i][1]])
if(id[check[i][0]] != 0 && id[check[i][1]] != 0)
result[i] = true;
}
return result;
}
private static void dfs(HashMap<Integer, List<Integer>> map, int v){
marked[v] = true;
id[v] = count;
for(int w : map.get(v)){
if(!marked[w]){
dfs(map,w);
}
}
}
public static void main(String[] args) {
int num = 4;
//int[][] country = {{1, 4}, {2,3}, {3, 5}, {6, 7}, {2, 4}, {8, 0}};
//int[][] check = {{1, 5}, {2, 6}, {1, 8}};
int[][] country = {{1,3}};
int[][] check = {{1,2},{1,0},{2,3}};
boolean[] booleans = mainlandCheck(num, country, check);
}
}