牛客网春招模拟测试算法题（一）

Posted on | Edited on | In | Comments:

题目一：好多鱼

牛牛有一个鱼缸。鱼缸里面已经有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)
第三行为已经有的鱼的大小fishSizei，以空格分隔。

输出描述

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

输入例子

1 12
1
1

输出例子

3

解题思路

这基本就是个比较大小的问题，不过并不牵扯到排序。根据题目，池子里已经有一些鱼，并且每条鱼的大小已知，那么后面放进去的鱼有两种可能会互相吃掉：
1.后放进的鱼比里面的某些鱼大：后放进的鱼是这些鱼的 2~10 倍大；
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(" ");
                }
            }
        }
    }
}

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