Here's to Change

请问你真的有在努力吗 ?

0%

牛客网春招模拟测试算法题(一)

题目一:好多鱼

牛牛有一个鱼缸。鱼缸里面已经有n条鱼,每条鱼的大小为fishSize[i] (1 ≤ i ≤ n,均为正整数),牛牛现在想把新捕捉的鱼放入鱼缸。鱼缸内存在着大鱼吃小鱼的定律。经过观察,牛牛发现一条鱼A的大小为另外一条鱼B大小的2倍到10倍(包括2倍大小和10倍大小),鱼A会吃掉鱼B。考虑到这个,牛牛要放入的鱼就需要保证:
1、放进去的鱼是安全的,不会被其他鱼吃掉
2、这条鱼放进去也不能吃掉其他鱼
鱼缸里面已经存在的鱼已经相处了很久,不考虑他们互相捕食。现在知道新放入鱼的大小范围minSize,maxSize,牛牛想知道有多少种大小的鱼可以放入这个鱼缸,

输入描述

输入数据包括3行.
第一行为新放入鱼的尺寸范围minSize,maxSize(1 ≤ minSize,maxSize ≤ 1000),以空格分隔。
第二行为鱼缸里面已经有鱼的数量n(1 ≤ n ≤ 50)
第三行为已经有的鱼的大小fishSize[i](1 ≤ fishSize[i] ≤ 1000),以空格分隔。

输出描述

输出有多少种大小的鱼可以放入这个鱼缸。考虑鱼的大小都是整数表示

输入例子

1 12
1
1

输出例子

3

解题思路

这基本就是个比较大小的问题,不过并不牵扯到排序。根据题目,池子里已经有一些鱼,并且每条鱼的大小已知,那么后面放进去的鱼有两种可能会互相吃掉:
1.后放进的鱼比里面的某些鱼大:后放进的鱼是这些鱼的 210 倍大;
2.后放进的鱼比里面的某些鱼小:里面的鱼是后放进鱼的 2
10 倍大;
用 size 代表后放进的鱼的大小,fishes[i] 代码里面的鱼的大小,则当:
1 : fish[i] * 2 <= size <= fish[i] * 10 ,此时后放进去的鱼会吃掉原有的鱼;
2 : size * 2 <= fishes[i] <= size * 10,此时原有的鱼会吃掉后放进的鱼;
这两个条件要同时不满足,才能保证不会有鱼被吃掉;
只要不是这两种情况,那么所有的鱼都可以存活,也就是满足:
(size > fishes[i] * 10 || size < fishes[i] * 2) && (fishes[i] > size * 10 || fishes[i] < size * 2 )
因为比较大小功能比较单一,可以抽象出一个 boolean compareTo(int fishSize,int[] fishes) 方法来,那么就有如下代码:

Java 实现(已AC)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Scanner;

/**
* Created by Alpha on 2017/3/7.
*/
public class EatFish {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String size = in.nextLine();
String[] sizes = size.split(" ");
int minSize = Integer.parseInt(sizes[0]);//后放鱼的最小值
int maxSize = Integer.parseInt(sizes[1]);//后放鱼的最大值
int fishCount = in.nextInt();//浴池中鱼的个数
int fishInCount = 0;//可以放入的个数
int[] fishes = new int[fishCount];
int p = 0;
while (p < fishCount && in.hasNext()) {//每条鱼的大小
fishes[p] = in.nextInt();
p++;
}
for (int i = minSize; i <= maxSize; i++) {
if (compareTo(i, fishes)) {//如果可以放入
fishInCount++;
}
}
System.out.println(fishInCount);

}

static boolean compareTo(int size, int[] fishes) {
int tag = 0;
for (int i = 0; i < fishes.length; i++) {
//同时满足两个条件
if ((size > fishes[i] * 10 || size < fishes[i] * 2)
&& (fishes[i] > size * 10 || fishes[i] < size * 2)) {
tag++;
if (tag == fishes.length) {
return true;
}
}
}
return false;
}
}

题目二:序列和

给出一个正整数N和长度L,找出一段长度大于等于L的连续非负整数,他们的和恰好为N。答案可能有多个,我我们需要找出长度最小的那个。
例如 N = 18 L = 2:
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
都是满足要求的,但是我们输出更短的 5 6 7

输入描述

输入数据包括一行:
两个正整数N(1 ≤ N ≤ 1000000000),L(2 ≤ L ≤ 100)

输出描述

从小到大输出这段连续非负整数,以空格分隔,行末无空格。如果没有这样的序列或者找出的序列长度大于100,则输出No

输入例子

18 2

输出例子

5 6 7

解题思路

这道题我昨晚模拟考试的时候并没有做出来,知道最后时间结束也只有 10% 的 case 通过测试。然后今天又奋战了一早晨,知道下午一点多才完全测试通过。

从输入描述来看输入的正整数会非常大,因此一定得考虑时间复杂度的问题,否则当输入的数为 1000000000 的时候会等待个十几秒乃至更久,所以其实我也是根据测试用例的提示一点点改进的,中间推翻了好几次之前的思路。

虽然输入数据很大,但是题目显示序列长度最长不能超过 100 ,这个数字利用起来,就能大幅度节省循环的时间。我们知道,若和为 m ,连续序列的长度为 n ,那么这个序列的起始数字肯定不会大于这些序列的平均值,所以 起始数字的范围最大到 m/n ;而序列起始值的最小范围也值得斟酌:m/n 是最大的可能值,既然是 n 个数字,又是连续的,那么第一个数字 至少要从 m/n-n/2 开始算起,例如和为 100 ,序列长度为 4,那么可能起始的值的最大值不会超过25,最小值不会小于 100/4-4/2 也就是 23 ;你可以用任何满足要求的数字和长度进行试验。
当然在当前长度可能找不到满足要求的序列,那么就需要增加序列的长度,然后重新计算起始值的最小最大范围。

Java 实现(已AC)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.Scanner;

/**
* Created by Alpha on 2017/3/7.
*/
public class ArraySum {
public static void main(String[] args) {
//读取输入
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
int n = Integer.parseInt(line.split(" ")[0]);
int l = Integer.parseInt(line.split(" ")[1]);
//最短长度
int minLength = l;
//最小起始点,可以从 0 开始
int minStart = n / 100 - 50 >= 0 ? n / 100 - 50 : 0;
//长度不能超过 100
while (minLength <= 100) {
int sum = 0;
//每当长度增长的时候,重新计算可能的最小起始值,可以从 0 开始
int currentStart = n / minLength - minLength / 2 >= 0 ? n / minLength - minLength / 2 : 0;
//起始值绝对不会超多最小长度个数的平均值
for (int start = currentStart; start <= n / minLength; start++) {
int length = minLength;
int tag = 0;//记录已经相加的个数
sum = 0;
while (length > 0 && sum < n) {//仅当长度大于0并且和小于 n 的时候继续相加
sum += start + tag;//被加数每次需要+1,表示下一个被加的数
tag++;
length--;
}
if (sum == n && tag >= l) {//若求和相等并且长度在题目范围之内
minStart = start;
break;//第一次的长度就是最短长度了
} else if (sum > n) {
continue;
}
}
if (sum == n) {
break;
}
minLength++;
}

//输出信息
if (minLength > 100) {
System.out.println("No");
} else {
for (int i = minStart; minLength-- > 0; i++) {
System.out.print(i);
if (minLength != 0) {
System.out.print(" ");
}
}
}
}
}

做了两道题就已经感觉有点头昏脑涨了,果然算法题更加容易耗费脑细胞 ~~
感觉自己做算法题都是凭借逻辑性来做,对题目并没有整体性的认识和判断,比如题目属于什么类型,有什么可供参考的解题思路,所以我还是得多看看算法书啊。