小红书笔试 08.28 AC

小红书选择题真的变态，C++、Java、Python、Go 语言都有，招全才呢。

第一题

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), id = sc.nextInt();
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] == b[0]? a[1]-b[1]:b[0]-a[0]);
        for(int i = 0; i < n; i++){
            int cnt = 0;
            for(int j = 0; j < m; j++) {
                cnt+= sc.nextInt();
            }
            pq.add(new int[]{cnt, i+1});
        }
        int cnt = 0;
        while(!pq.isEmpty()){
            cnt++;
            int tmp[] = pq.poll();
            if(tmp[1] == id) {
                System.out.println(cnt);
            }
        }
    }

第二题

    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        long arr[] = new long[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextLong();
        }
        Arrays.sort(arr);
        long ret = 0;
        for(int i = 0; i < n-1; i++){
            long value = arr[i];
            int left = i+1, right = n-1;
            while(left < right) {
                int mid = (left+right)/2;
                if(value * arr[mid] >= k) {
                    right = mid;
                }else{
                    left = mid+1;
                }
            }
            if(value * arr[left] >= k){
                ret += n - left;
            }
        }
        System.out.println(ret*2);
    }

第三题

map 用于记忆，避免重复计算；

dfs 方法用于仿照树进行深搜，其中pre用于记录当前节点的父节点，canuse 用来表示当前节点是否可用。

如果当前节点不可用，则子节点均可用；

如果当前节点均可用，则（1）子节点均可用（2）当前节点和其中一个子节点建立连接，该子节点不可用，其余子节点可用。

有没有更简单的方法呀，感觉还是有点麻烦

   static Map<Integer, Integer> map;
    static ArrayList<Integer>[] edges;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new HashMap<>();
        edges = new ArrayList[n+3];
        for(int i = 0; i < n+3; i++) {
            edges[i] = new ArrayList<Integer>();
        }
        for(int i = 0; i < n-1; i++) {
            int tmp = sc.nextInt();
            edges[tmp].add(i+2);
            edges[i+2].add(tmp);
        }
        System.out.println(dfs(1, 1, -1));
    }

    static int dfs(int canuse, int idx, int pre) {
        int arr = idx * canuse;
        if (map.containsKey(arr)) {
            return map.get(arr);
        }
        int cnt = 0;
        for (int next : edges[idx]) {
            if (next != pre) {
                cnt += dfs(1, next, idx);
            }
        }
        int ret = cnt;
        if (canuse == 1) {
            for(int next: edges[idx]) {
                if(next != pre) {
                    int f = dfs(-1, next, idx);
                    int t = dfs(1, next, idx);
                    ret = Math.max(ret, cnt - t + f + 1);
                }
            }
        }
        map.put(arr, ret);
        return ret;
    }

#小红书##笔试##校招##23届秋招笔面经#