360公司2019校招笔试编程题合集中的题目练习和记录。
1.城市修建
题目描述
有一个城市需要修建，给你N个民居的坐标X,Y，问把这么多民居全都包进城市的话，城市所需最小面积是多少（注意，城市为平行于坐标轴的正方形）
输入描述：
第一行为N，表示民居数目（2≤N≤1000）
输出描述：
城市所需最小面积
输入例子1：
2
0 0
2 2
输出例子1：
4
输入例子2：
2
0 0
0 3
输出例子2：
9
编程
求最小面积，相当于求正方形的最小边长，假设所给点（x，y）的最小的x坐标和最大的x坐标之差为m，最小的y坐标和最大的y坐标之差为n。则最小边长必须等于max(m,n)。
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
long lon_max,lon_min,weg_max,weg_min;
long temp1 = sc.nextLong();
long temp2 = sc.nextLong();
lon_max = temp1;
weg_max = temp2;
lon_min = temp1;
weg_min = temp2;
for(int i=0;i<length-1;i++){
temp1 = sc.nextLong();
temp2 = sc.nextLong();
lon_max = Math.max(lon_max,temp1);
weg_max = Math.max(weg_max,temp2);
lon_min = Math.min(lon_min,temp1);
weg_min = Math.min(weg_min,temp2);
}
long longlong = Math.max(Math.abs(lon_max-lon_min),Math.abs(weg_max-weg_min));
System.out.println(longlong*longlong);
sc.close();
}
}
讨论
该题目的几个难点在于：
- 自己实现输入输出，对于java语言，利用
Scanner实现读取输入，利用System.out.println实现输出。 - 利用API（
Math.max()、Math.min()、Math.abs()），或者自己编程实现排序算法，来找出坐标中的最大值和最小值。 - 不能用int型的变量存储坐标值，应该用long型，因为输入数据很大。
- 注意对于各种情况的考虑周全，比如最开始将坐标的最大值和最小值都初始化为0，就没有考虑到坐标全为正或全为负的情况，导致测试用例不能完全通过，如下图。
参考
2.圈地运动
题目描述
圈地运动，就是用很多木棍摆在地上组成一个面积大于0的多边形～
小明喜欢圈地运动，于是他需要去小红店里面买一些木棍，期望圈出一块地来。小红想挑战一下小明，所以给小明设置了一些障碍。障碍分别是：
1.如果小明要买第i块木棍的话，他就必须把前i-1块木棍都买下来。
2.买了的木棍都必须用在圈地运动中。
那么请问小明最少买多少根木棍，才能使得木棍围成的图形是个面积大于0多边形呢？
输入描述：
第一行一个数n，表示木棍个数。
第二行n个数，第i个数表示第i个木棍的长度ai
1<=n<=10000
1<=ai<=10000
输出描述：
输出一个数，表示最少需要的木棍个数，如果无解输出-1
输入例子1：
3
6 8 10
输出例子1：
3
例子说明1：
用三根6，8，10的木棍可以组成一个直角三角形的图形。
编程
问题的本质其实就是，给定n条边，问能否构成n边形，而给定n条边能构成n边形的条件是任意n-1条边的和大于第n条边，也就是说必须满足这n条边中的最大值小于剩下n-1条边的和。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
if(len<3){
System.out.println(-1);
}
int[] tar = new int[len];
for(int j=0; j<len; j++){
tar[j] = sc.nextInt();
}
int max = 0;
int sum = 0;
for(int i=0; i<len; i++){
if(tar[i]>max){
sum = sum + max;
max = tar[i];
}else{
sum = sum + tar[i];
}
if((i>1)&&(max<sum)){
System.out.println(i+1);
break;
}else{
if(i == len-1){
System.out.println(-1);
}
}
}
}
}
讨论
该题目的难点在于对多边形的构成条件的理解。还有各种基于此基本问题的变形，如参考中今日头条的笔试题目。