贝壳笔试---2020

1、题目：输入n个正整数，要求找出相邻两个数字中差的绝对值最小的一对数字，如果有差的绝对值相同的，则输出前面的一对数。【2<=n<=100，正整数都在10^16范围内】
思路：暴力做法，直接全部遍历，找到最小的，保留下标。
import java.util.Scanner;
public class A {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] arr = new long[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextLong();
long res = Math.abs(arr[1] - arr[0]);
int index = 0;
for (int i = 1; i < n - 1; i++) {
if (res > Math.abs(arr[i] - arr[i + 1])) {
res = Math.abs(arr[i] - arr[i + 1]);
index = i;
}
}
System.out.println(arr[index] + " " + arr[index + 1]);
sc.close();
}
}

2、题目：琪琪有n个数字，琪琪想知道有多少个数字恰好可以用剩下的n-1个数字中的两个数和表示。【0<=n<=100,0<=数字<=10000】
思路：先对数组排序，前两个数字肯定不符合条件，从第3个开始，开始从头遍历到i结束，找到则退出，遍历下一个。
import java.util.Arrays;
import java.util.Scanner;
public class D {
public static void main(String[] args) {
// 输入数组长度n，数组存放在int[] inputArr中。
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int result = 0;
Arrays.sort(a);
// 前两个没有
for (int i = 2; i < n; i++) {
int sum = a[i];
for (int j = 0; j < i; j++) {
//从j+1开始找，到i结束
int find = getLatestNum(sum - a[j], a,j+1,i);
if (find != -1) {
result++;
break;
}
}
}
System.out.println(result);
sc.close();
}
public static int getLatestNum(int number, int[] arr,int k,int n) {
int rs = -1;
for (int i = k; i < n; i++) {
if (number == arr[i]) {
rs = i;
break;
}
}
return rs;
}
}

3、题目：小希偶然得到了传说中的月光宝盒，然而打开月光宝盒需要一串密码。虽然小希并不知道密码具体是什么，但是月光宝盒的说明书上有着一个长度为n（2<=N<=50000）的序列a(-10^9<=a[i]<=10^9)的范围内。下面写着一段话，密码是这个序列的最长的严格上升子序列的长度（严格上升子序列是指，子序列的元素是严格递增的，例如：[5,1,6,2,4]的最长严格上升子序列为[1,2,4]），请你帮小希找到这个密码。【1<=n<=5000,1<=ai<=10^9】
思路：外层循环一次遍历数组，利用临时数组保存当前的上升子序列，再利用二分法对临时数组的值和当前的值比较大小，size保存的是临时数组的有效长度，同时也是上升子序列的长度。
import java.util.Scanner;
public class C {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int[] arr = new int[m];
for (int i = 0; i < m; i++) {
arr[i] = sc.nextInt();
}
System.out.println(lengthOfLIS(arr));
sc.close();
}
public static int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int low= 0, hight = size;
while ( low!= hight) {
int m = (low + hight) / 2;
if (tails[m] < x)
low = m + 1;
else
hight= m;
}
tails[i] = x;
if (i == size)
++size;
}
return size;
}
}

4、题目：小C在做一种特殊的服务器负装测试，对于一个请求从列中的清求，每一个请求都有一个负荷值，为了保证服务器稳定，请求队列中的请求负荷必须按照先递增后递减的规律【仅递增，仅递减也可以】，比如[1,2,8,4,3],[1,3,5]和[10]这些是满足规律的，还有一些不满足的，比如[1.2.2.1],[2,1,2]和[10，10]，现在给你一个请求队列，你可以对请求的负荷值进行增加，要求你调整队列中请求的负荷值，使数组满足条件，最后输出使队列满足条件最小的增加总和。【1<=n<=5000,1<=ai<=10^9】
思路：用一个临时数组保存原来的数据，原来数组的每一项都假设是一个最大值，分别比较左边的【必现是递增】和右边的数【必须是递减】，看哪一项当最大值满足条件且所加的数之和最小，每次比较完后，重新赋值成原始的数据。
import java.util.Scanner;;
public class A {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextLong();
}
long[] kk = new long[n];
for (int i = 0; i < n; i++) {// 保留原始数据
kk[i] = arr[i];
}
long minn = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {// 假设i为最大值的下标
long ac = 0;// 每次循环的最小值
for (int j = 1; j <= i; j++) {// 最大值的左边
if (arr[j - 1] >= arr[j]) {// 最大值的左边必须是递增的
ac += arr[j - 1] - arr[j] + 1;
arr[j] = arr[j - 1] + 1;// 如果递减了，右边的数等于左边的数+1
}
}
for (int k = n - 1; k > i; k--) {// 最大值的右边必现是递减的
if (arr[k - 1] <= arr[k]) {
ac += arr[k] - arr[k - 1] + 1;
arr[k - 1] = arr[k] + 1;
}
}
minn = Math.min(minn, ac);
//继续按原数据再比较
for (int a = 0; a < n; a++)
arr[a] = kk[a];
}
System.out.println(minn);
sc.close();
}
}

5、题目：举重大赛开始了，为了保证公平，要求比赛的双方体重较小值要大于等于较大值的90%，那么对于这N个人最多能进行多少场比赛呢，任意两人之间最多进行一场比赛。输入 5 1 1 1 1 1 输出 10。
思路：先对输入的数组进行排序，有两层循环，外层先固定一个人，里层循环是从剩下的人中找到满足条件的人【跟排列组合有点像】。
import java.util.Arrays;
import java.util.Scanner;
public class B {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n;
int[] m;
while (scanner.hasNextInt()) {
n = scanner.nextInt();
m = new int[n];
for (int i = 0; i < n; i++) {
m[i] = scanner.nextInt();
}
System.out.println(count(n, m));
scanner.close();
}
}
private static int count(int n, int[] m) {
int res = 0;
Arrays.sort(m);
for (int i = 0; i < n; i++) {
double temp = m[i] / 0.9;
int j = i + 1;
while (j < n && m[j] <= temp) {
res++;
j++;
}
}
return res;
}
}

贝壳笔试---2020

全站热榜