京东2019秋招笔试题（Java）

时间：20180909   19：00~21：00

一、完全多部图

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

输入
第一行输入一个整数T表示数据组数，1≤T≤10。

每组数据格式为：

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

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

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

样例输入
2
5 7
1 3
1 5
2 3
2 5
3 4
4 5
3 5
4 3
1 2
2 3
3 4
样例输出
Yes
No

import java.util.Scanner;

/**
 * 完全多部图
 * 就是每个一种集合里点的个数加上出度比总点数大。比如一个完全图，每个点出度都是n-1，你就可以分成n个集合，
 * 每个点的出度加上自己这个1，就是n。这个题就问你集合了，没说别的，你也不要用考虑分几个集合。
 * 直接写成加起来比总量大就行了。比如一个10个点的图，里面有一个度为1的点，
 * 它就永远不可能跟其他集合里面任意的点连起来。想要连起来，需要9和度为1的点才行。
 * 也就是9个都连一个上面，拆成两个集合，一个是度为9的，另一个是9个度为1的。
 * 
 */
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		while (a-- != 0) {
			int b = sc.nextInt();
			int c = sc.nextInt();
			int row = 0;
			int wid = 0;
			int[] sum = new int[b + 1];
			for (int i = 0; i < c; i++)
			{
				row = sc.nextInt();
				wid = sc.nextInt();
				sum[row]++;
				sum[wid]++;
			}
			int t = 0;
			for (int i = 0; i < b - 1; i++)
			{
				int key = 0;
				for (int j = 1; j < b + 1; j++)
					if (sum[j] == i)
						key++;
				if (key + i < b && key != 0)
				{
					t++;
					break;
				}
			}
			if (t == 0)
				System.out.println("Yes");
			else
				System.out.println("No");
		}
	}
}

这道题的解法是看的赛格网上的大神的答案（原模原样），拿来借鉴一下。

二、对比

题目描述：
现有n个物品，每个物品有三个参数 ai , bi , ci ，定义i物品不合格品的依据是 : 若存在物品 j , 且aj>ai , bj>bi , cj>ci，则称i物品为不合格品。

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

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

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

样例输入
3
1 4 2
4 3 2
2 5 3
样例输出
1

Hint
样例解释
物品1的a,b,c均小于物品3的a,b,c,因此1为不合格品。

import java.util.ArrayList;
import java.util.List;
/**
 * 对比
 */
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Thing> list = new ArrayList();
		for(int i = 0; i < n; i++){
			list.add(new Thing(sc.nextInt(),sc.nextInt(),sc.nextInt()));
		}
		int count = judge(list);
		System.out.println(count);
	}

	private static int judge(List<Thing> list) {
		int count = 0;
		for(int i = 0; i < list.size(); i++){
			for(int j = 0; j < list.size(); j++){
				if(list.get(j).a>list.get(i).a&&list.get(j).b>list.get(i).b&&list.get(j).c>list.get(i).c){
					count++;
					break;
				}
					
			}
		}	
		return count;
	}
}
class Thing{
	int a;
	int b;
	int c;
	public Thing(int a, int b, int c) {
		super();
		this.a = a;
		this.b = b;
		this.c = c;
	}
}