京东历年秋招笔试真题

如需获取完整资料，请点击下方链接领取《2024校招笔试真题秘籍》（实时更新中）

不收费，3人组团即可一块免费领取！限量免费10000个名额

手机端点击免费领取：https://www.nowcoder.com/link/campus_xzbs2

电脑端请扫码领取：

1、完全多部图

【题目描述】给定一张包含N个点、M条边的无向图，每条边连接两个不同的点，且任意两点间最多只有一条边。对于这样的简单无向图，如果能将所有点划分成若干个集合，使得任意两个同一集合内的点之间没有边相连，任意两个不同集合内的点之间有边相连，则称该图为完全多部图。现在你需要判断给定的图是否为完全多部图。

输入描述：

包含多组数据，每组输入格式为：

第一行包含两个整数N和M，1≤N≤1000，0≤M≤N(N-1)/2；

接下来M行，每行包含两个整数X和Y，表示第X个点和第Y个点之间有一条边，1≤X，Y≤N。

输出描述：

每组输出占一行，如果给定的图为完全多部图，输出Yes，否则输出No。

输入样例：

5 7

1 3

1 5

2 3

2 5

3 4

4 5

3 5

输出样例：

Yes

【解题思路】

根据给的边，可以判断哪些点应该属于一个集合。如果存在一个点同时属于多个集合，则不是完全多部图。

复杂度O(n^2)

【参考代码】

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;
int n, m;
int a[N][N];
int belong[N], cnt;
int main() {
    scanf("%d%d", &n, &m);
    while(m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u][v] = a[v][u] = 1;
    }
    for(int u = 1; u <= n; ++u) {
        if(belong[u]) continue;
        belong[u] = ++cnt;
        for(int v = u + 1; v <= n; ++v) {
            if(!a[u][v]) {
                if(belong[v] != 0) {
                    puts("No");
                    return 0;
                }
                belong[v] = cnt;
            }
        }
    }
    for(int u = 1; u <= n; ++u) {
        for(int v = u + 1; v <= n; ++v) {
            if(belong[u] == belong[v] && a[u][v] ||
               belong[u] != belong[v] && !a[u][v]) {
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
    return 0;
}

2、对比

【题目描述】现有n个物品，每个物品有三个参数，定义i物品不合格品的依据是:若存在物品j,且，则称i物品为不合格品。

现给出n个物品的a,b,c参数，请你求出不合格品的数量。

输入描述：

第一行包含一个整数n(1<=n<=500000),表示物品的数量。接下来有n行，每行有三个整数，表示第i个物品的三个参数

输出描述：

输出包含一个整数，表示不合格品的数量。

输入样例：

3

1 4 2

4 3 2

2 5 3

输出样例：

1

样例解释：

物品1的a,b,c均小于物品3的a,b,c,因此1为不合格品。

【解题思路】

三维偏序问题。

先对第一维排序，然后降序处理。对于第二三维，可以用一个平衡树（可以使用std::multiset）维护一个外围包络，这样可以快速判断一个点的右上方是