华为 4.17 笔试AK

暑期实习投到现在大大小小笔试做了好多，基本都只过一题多点，昨天刚刚被xhs虐完，今天做华子的笔试，AK了，头一回AK。算是这段时间找实习处处碰壁唯一能稍微舒缓一下情绪的事情了。

希望华子能给机会

第一题 数据量不大，狠狠暴力。我这做法并不优。不过数据量小

// 4.17 1
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        HashMap<String,Integer> m = new HashMap<>();
        scan.nextLine();
        String s = scan.nextLine();
        String str = s;
        String t = rem(str);
        while(!str.equals(t)){
            str = t;
            t = rem(t);
            if(t.equals("0")) {
                str = t;
                break;
            }
        }
        System.out.print(str);

    }
    static String rem(String s){
        String[] cards = s.split(" ");
        int n = cards.length;
        StringBuilder ans = new StringBuilder();
        int i = 0;
        while(i<n){
            String t = cards[i];
            int ti = i;
            int count = 0;
            while(i<n&&t.equals(cards[i])){
                count++;
                i++;
            }
            if(count==3){
                continue;
            }else if(count == 4){
                ans.append(t);
                ans.append(' ');
            }else{
                for (int j = ti; j < i; j++) {
                    ans.append(t);
                    ans.append(' ');
                }
            }
        }
        if(ans.length() == 0)return "0";
        ans.deleteCharAt(ans.length()-1);
        return ans.toString();
    }

}

第二题 建树+bfs写的。因为是字符串，建树挺麻烦的，应该还有更好的方法，例如并查集应该能做。

//4.17 2
import java.util.*;

public class Main {
    static Set<String> fa = new HashSet<>();
    static HashMap<String, Set<String>> lm = new HashMap<>();
    static HashMap<String, int[]> nm = new HashMap<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int M = scan.nextInt();
        int N = scan.nextInt();
        scan.nextLine();
        String[] problems = new String[N];
        for (int i = 0; i < N; i++) {
            problems[i] = scan.nextLine();
        }
        for(String line:problems){
            String[] items = line.split(" ");
            String father = items[1];
            String child = items[0];
            int lev = Integer.parseInt(items[2]);
            int num = Integer.parseInt(items[3]);

            if(father.equals("*")){
                fa.add(child);
                if(!lm.containsKey(child)) lm.put(child,new HashSet<>());
                if(!nm.containsKey(child)) nm.put(child,new int[]{0,0});
            }else {
                if(!lm.containsKey(father))lm.put(father,new HashSet<>());
                if(!nm.containsKey(father)) nm.put(father,new int[]{0,0});
                if(!lm.containsKey(child))lm.put(child,new HashSet<>());
                if(!nm.containsKey(child)) nm.put(child,new int[]{0,0});
                lm.get(father).add(child);
            }
            nm.get(child)[lev]+=num;
        }
        int ans = 0;
        for (String f:fa) {
            int x = dfs(f);
            if(x>M)ans++;
        }
        System.out.println(ans);
    }
    static int dfs(String root){
        Set<String> x = lm.get(root);
        int[] my = nm.get(root);
        int cost = 5*my[0]+2*my[1];
        for(String y:x){
            cost += dfs(y);
        }
        return cost;
    }
}

第三题 dijkstra，求完再加个索引一块排序。 不过奇怪的是，给的数据n = 1e4,矩阵都1e8了，java竟然只跑180ms，不知道时间是怎么算的

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] g = new int[n][n];
        int[] cap = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = scan.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            cap[i] = scan.nextInt();
        }
        int s = scan.nextInt();
        int ms = scan.nextInt();
        int[][] res = dijkstra(g,s);
        Arrays.sort(res,(a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);
        StringBuilder ans = new StringBuilder();
        int sum = 0;
        for (int i = 1; i < n; i++) {
            sum+=cap[res[i][1]];
            ans.append(res[i][1]);
            ans.append(' ');
            if(sum>=ms)break;
        }
        ans.deleteCharAt(ans.length()-1);
        System.out.println(ans);

    }

    static int[][] dijkstra(int[][]g,int s){
        int n = g.length;
        int[] dist = new int[n];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[s] = 0;
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            int t  = -1;
            for (int j = 0; j < n; j++) {
                if(!vis[j]&&(t==-1||(dist[t]>dist[j]))){
                    t = j;
                }
            }
            vis[t] = true;
            for (int j = 0; j < n; j++) {
                if(g[t][j]<0) continue;
                if(dist[t]+g[t][j]<dist[j]){
                    dist[j] = dist[t]+g[t][j];
                }
            }
        }

        int[][]res = new int[n][2];
        for (int i = 0; i < n; i++) {
            res[i][0] = dist[i];
            res[i][1] = i;
        }

        return res;

    }

}