24号京东笔试编程题经验分享
首先我是个菜鸡
其次第二题有没有AC的，我想求个解答，我过了18%，但是想不明白。。
顺带分享一下我的第一题思路。。
第一题
创建三个数组：
int[] height 保存每个人身高
int[] leftMax 下标为i的学生左边(包括他自己)最高的学生
int[] rightMin 下标为i的学生右边(包括他自己)最低的学生
如果一个下标i，左边最高的(包括他自己) <= 右边最低的(不包括他自己)，那么就可以以他左边为界限分开
代码：
import java.util.Scanner;
/**
* @author 桀骜(Geolo)
* @version 1.0
* @date 2019/8/24
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int count = scanner.nextInt();
// 特殊情况
if (count == 0) {
System.out.println(0);
continue;
}
if (count == 1) {
System.out.println(1);
continue;
}
// 获取身高
int[] height = new int[count];
for (int i = 0; i < count; i++) {
height[i] = scanner.nextInt();
}
int[] leftMax = new int[count];
int[] rightMin = new int[count];
leftMax[0] = height[0];
rightMin[count - 1] = height[count - 1];
for (int i = 1; i < count; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
for (int i = count - 2; i >= 0; i--) {
rightMin[i] = Math.min(rightMin[i + 1], height[i]);
}
int res = 1;
for (int i = 0; i < count - 1; i++) {
if (leftMax[i] <= rightMin[i + 1]) {
res++;
}
}
System.out.println(res);
}
}
}
最后也没说超时，死活都是18%通过率，有没有大佬给解答下的，或者发现我代码的问题
import java.util.*;
/**
* @author 桀骜(Geolo)
* @version 1.0
* @date 2019/8/24
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int studentCount = scanner.nextInt() * 2;
int relationCount = scanner.nextInt();
List<Student> students = new ArrayList<>(studentCount);
HashMap<Integer, Student> numberMap = new HashMap<>(studentCount, 0.5f);
for (int i = 0; i < studentCount; i++) {
Student student = new Student(i + 1, relationCount);
students.add(student);
numberMap.put(i + 1, student);
}
for (int i = 0; i < relationCount; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
numberMap.get(a).getFriends().add(b);
numberMap.get(b).getFriends().add(a);
}
Comparator<Student> comparator = new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
int subCount = o2.getFriends().size() - o1.getFriends().size();
if (subCount != 0) {
return subCount;
} else {
return o1.number - o2.number;
}
}
};
List<Student> outStudents = new ArrayList<>(studentCount);
while (relationCount != 0) {
students.sort(comparator);
Student student = students.get(0);
if (student.getFriends().size() == 0) {
break;
}
Iterator<Integer> iterator = student.getFriends().iterator();
while (iterator.hasNext()) {
int friendNumber = iterator.next();
Student friend = numberMap.get(friendNumber);
friend.getFriends().remove(student.number);
students.remove(student);
numberMap.remove(student.number);
}
relationCount -= student.friends.size();
outStudents.add(student);
}
System.out.println(outStudents.size());
for (int i = 0; i < outStudents.size(); i++) {
System.out.print(outStudents.get(i).number + " ");
}
}
}
public static class Student {
private int number;
private Set<Integer> friends;
public Student(int number, int initialCapacity) {
this.number = number;
friends = new HashSet<>(initialCapacity);
}
public Set<Integer> getFriends() {
return friends;
}
}
}
联想公司福利 620人发布
