2019届爱奇艺秋招笔试题【局长的食物】【清雨的自助餐】【库特君的面条】

笔试题

局长的食物

1.题目描述

  每天局长会吃一份食物，或者买一份食物（即每天只能进行吃或买其中的一种动作），这样过了M天现在局长想知道M天后第p种食物的份数排名（从大到小，相同算并列，例如3 3 2，则排名为1 1 3）N,M,P<=100,Ai<=1000。
输入描述：
 第一行N M P
 第二行N个数Ai
 接下来M行，每行Ai或者Bi分别表示买一份食物i，吃一份食物i
输出
 一个答案
输入样例:
 3 4 2 5 3 1 B 1 A 2 A 2 A 3
输出样例：
 1

2.解题思路

方法1：
   模拟吃东西的过程：关键在于吃一份食物还是买一份食物数据的存储方式，本次的数据存储方式为 List<List< String > >,注意后面的Integer.parseInt的转型。更好的方法是用对象存储
方法2：
    用class存储数据

3.代码

方法1: 用List<List< String > >存储数据

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
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int N  = sr.nextInt();
        int M  = sr.nextInt();
        int P  = sr.nextInt();
        int a[] = new int[N];
        for(int i = 0;i<N;i++){
            a[i] = sr.nextInt();
        }
        List<List<String>> list = new ArrayList<>();
        for(int i = 0;i<M;i++){
            List<String> temp= new ArrayList<>();
            temp.add(sr.next());
            temp.add(sr.next());
            list.add(temp);
        }
         System.out.println(solution(list,P,a));
    }

    private static int  solution(List<List<String>> list, int p, int[] a) {
        for(int i = 0;i<list.size();i++){
            // 买一份食物
            if(list.get(i).get(0).equals( "A")){
                int index = Integer.parseInt(list.get(i).get(1)) - 1;
                a[index] ++;
            }else{
                //吃一份食物
                int index = Integer.parseInt(list.get(i).get(1)) - 1;
                a[index] --;
            }
        }
        //第p种食物的份数排名
        int res = 1;
        for(int i = 0;i<a.length;i++){
            if(a[p-1]<a[i]){
                res++;
            }
        }
        return res;
    }
}

在这里插入图片描述
方法2：用对象存储

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
58
59
60
61
62
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int N  = sr.nextInt();
        int M  = sr.nextInt();
        int P  = sr.nextInt();
        int a[] = new int[N];
        for(int i = 0;i<N;i++){
            a[i] = sr.nextInt();
        }
        List<Category> lists = new ArrayList<>();
        for(int i = 0;i<M;i++){
            lists.add(new Category(sr.next(),sr.nextInt()));
        }
        System.out.println(solution(lists,P,a));
    }

    private static int  solution(List<Category> lists, int p, int[] a) {
        for(int i = 0;i<lists.size();i++){
            //买一份食物
            if(lists.get(i).x.equals("A")){
                a[lists.get(i).getIndex()-1]++;
            }else{
            //吃一份食物
                a[lists.get(i).getIndex()-1]--;
            }
        }
        //第p种食物的份数排名
        int res = 1;
        for(int i = 0;i<a.length;i++){
            if(a[p-1]<a[i]){
                res++;
            }
        }
        return res;
    }
    }
 //存储 [A 2] 等数据
 class Category{
    String x;
    int index;
    public Category(String x, int index) {
        this.x = x;
        this.index = index;
    }
    public String getX() {
        return x;
    }
    public void setX(String x) {
        this.x = x;
    }
    public int getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
}

在这里插入图片描述

清雨的自助餐

1.题目描述

  清雨又在吃自助餐了。
 排在清雨面前的有N种食物，排成一排，清雨可以选择其中的若干种食物，但是不能连续选择相邻的食物。因为清雨很挑食，当所有食物都不合口味时，他可以一种都不选，即一个都不选也算为一种方法。
请问他有多少种选择食物的方法呢？
输入
 一个整数n（1 <= n <= 90）
输出
 一个正整数表示答案
样例输入
 3
样例输出
 5

2. 解题思路

动态规划问题：dp[i]表示有(i+1)种食物的时候有多少种选择的方法

  • 初始化
    • dp[0] = 2，表示有1种食物，可以选择吃或者不吃2种方法
    • dp[1] = 3,表示有两种食物，可以选择不吃，吃第一种，吃第二种 3种方法
  • 动态规划状态转移矩阵
    • 如果选这个食物(第i+1种食物)，则选择为dp[i-2]种选法，若不选择这个食物,则方法数为dp[i-1]{因为相邻而不能选}即
    • dp[i] = dp[i-2] + dp[i-1];

注：该题也可以用斐波那契数列的应用，只是初始值变了，具体参看剑指offer_【7】斐波那契数组:https://blog.csdn.net/qq_17556191/article/details/94436130

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int N = sr.nextInt();
        System.out.println(solution(N));
    }
    public static long solution(int num) {
        if (num == 0)
            return 1;
        else if (num == 1)
            return 2;
        else {
            long dp[] = new long[num];
            dp[0] = 2;  //只有一种食物，可以选择 吃 或者不吃2种方法
            dp[1] = 3;  //有2种食物，选择 不吃 ，吃第一种食物，吃第二种食物。
            for (int i = 2; i < num; i++) {
                dp[i] = dp[i - 2] + dp[i - 1];
            }
            return dp[num - 1];
        }
    }
}

在这里插入图片描述

库特君的面条

1.题目描述

题目描述：
库特君在吃面条！
 他将面条放在了数轴上，每根面条对应数轴上的两个点a和b，他想知道在任意两根面条不重叠(端点可以重叠）的情况下最多能选出多少根面条。
1 <= n <= 100
-999 <= a
输入描述：
  第一行为一个整数N
  接下来，N行每行N个整数a和b
输出描述：
  一个数的答案
输出样例：
  3 6 3 1 3 2 5
输出样例：
  2

2.解题思路

贪心算法的区间调度问题

  • 贪心策略：在不与已选区域重叠的前提下，优先选择右端点最小的区间，所以按照区间右端点排序后，依次检查，不重叠就选择，并更新已选区域的最右端，方便判断重叠。

算法设计：

  • 如果被检查的活动i的开始时间小于最近选择的活动j的结束时间，则不选择活动i,否则选择活动i
    • 1.选择最早结束的面条，便是最开始要选择的没有重叠的第一根面条
    • 2.选择第一根面条结束后[右端点值]才开始的第二根面条[该面条的左端点大于等于第一根面条的右端点]，并且此时右端点结束最早的面条，这将是要选择的第二根面条。
    • 3.更新右端点值，重复以上。

3.代码

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
58
59
60
61
62
63
64
65
import java.util.*;
//贪心算法的区间调度问题
public class Main {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int N = sr.nextInt();
        List<Work> lists = new ArrayList<>();
        for(int i = 0;i<N;i++){
            int x1 = sr.nextInt();
            int x2 = sr.nextInt();
            //题目说了x1<x2,但是给出的样例出现了问题，故用个if语句
            if(x1<x2)
                lists.add(new Work(x1,x2));
            else
                lists.add(new Work(x2,x1));
        }
        System.out.println(solution(lists));
}
    //解决方法
    private static int solution(List<Work> works) {
        //works里面已经按end从小到大排序了，这时在将start进行排序，找到第一个要进行的工作
        Collections.sort(works);
        int count = 1;
        //当前工作的结束时间
        int endTime = works.get(0).getEnd();
        for(int i = 1;i<works.size();i++){
            // 第二根面条的开始时间大于第一个面条的结束时间
            if(endTime<=works.get(i).getStart()){
                //这个面条可选，没有覆盖之前的面条
                count++;
                //更新右端点
                endTime = works.get(i).getEnd();
            }
        }
        return count;
    }

    static class Work implements Comparable{
    private int start;
    private int end;
    public Work(int start, int end) {
        this.start = start;
        this.end = end;
    }
    //end 从小到大排序
    @Override
    public int compareTo(Object o) {
        Work work = (Work) o;
        if(this.end > work.getEnd()){
            return 1;
        }else if(this.end == work.getEnd()){
            return 0;
        }else{
            return -1;
        }
    }
    public int getStart() {
        return start;
    }
    public int getEnd() {
        return end;
    }
}

}

在这里插入图片描述
题目整理自牛客技术篇
个人想法，如有错误请指出！！

本文标题:2019届爱奇艺秋招笔试题【局长的食物】【清雨的自助餐】【库特君的面条】

文章作者:qiulig

发布时间:2019-07-27, 17:20:15

最后更新:2019-07-27, 17:21:21

文章字数:2k

原始链接:http://blogs.qiulig.website/2019/07/2019届爱奇艺秋招笔试题【局长的食物】【清雨的自助餐】【库特君的面条】/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 局长的食物
    1. 1.1. 1.题目描述
    2. 1.2. 2.解题思路
    3. 1.3. 3.代码
  2. 2. 清雨的自助餐
    1. 2.1. 1.题目描述
    2. 2.2. 2. 解题思路
    3. 2.3. 3.代码
  3. 3. 库特君的面条
    1. 3.1. 1.题目描述
    2. 3.2. 2.解题思路
    3. 3.3. 3.代码
| 139.6k