网易互娱服务端研发 4.18笔试 3点-5点场（求第二题解）

"just","java","jar","jack","jackson"

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;
    }
}

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);
    }
}

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);
    }
}