美团 3.27笔试

作者：知更鸟女孩！！
链接：https://www.nowcoder.com/discuss/625614?type=2&channel=1009&source_id=discuss_center_discuss_hot_nctrack
来源：牛客网

美团java后端实习 3.27笔试复盘

1、小美摆积木
时间限制： 3000MS
内存限制： 1048576KB

题目描述：
小美想要为小团摆一行积木，每个积木上都有一个0-9的数字。现在已经摆好了 n 块积木，小美可以把其中一块积木替换成任意一块积木（也可以不替换），使得积木看起来更符合小美的审美。请你帮小美看看，替换后最好看的积木是什么样的。
摆好后的积木上面的数字，从左到右会形成一个数字串（由数字组成的字符串）。小美会根据这个数字串来评判积木的好看程度，小美有两条审美标准：
①回文数字串相比于非回文数字串更符合小美的审美。例如：12321、2332是回文数字串，而12212、2121不是回文数字串。
②数字串形成的数字更小更好看。例如：1312比1313更好看，0102比1102更好看。
小美会按照她的审美标准来判断两个数字串哪个更好看，即先按照审美标准①判断，若无法判断再按审美标准②判断。

输入描述
第一行一个数 T，表示一共有 T 组测试数据。(1 ≤ T ≤ 100)。
接下来 T 组数据，每组数据两行，
第一行一个数 n，表示有 n 块积木。(1 ≤ n ≤ 20000)。
第二行 n 个数字，第 i 块积木上的数字是 si。(si是0-9的数字)。

输出描述
每组数据输出一行，表示最终摆好的积木形成的数字串。

样例输入
2
5
00011
5
11210
样例输出
00001
01210

提示
第一组数据：
替换一块积木，无法使数字串变成回文数字串，因此只能数字串形成的数字最小。
第二组数据：
可以把第一块积木1换成0，也可以把第五块积木0换成1，从而使得积木是回文积木。又想要积木字典序最小，所以把第一块积木1替换成0。
2、小美斗龙
时间限制： 3000MS
内存限制： 1048576KB

题目描述：
小美得到了一款游戏——斗龙。小美拥有两个技能，每个技能都能秒杀掉一条龙，但是要付出相应的MP值，第一个技能需要c1点MP值，第二个技能需要c2点MP值。只要MP足够，小美可以使用无限次技能。
小美即将遇到 n 条龙，如果不使用技能，她和第 i 条龙的战斗结果是T或者F，而如果使用任何一个技能战斗结果都是T。T表示小美成功打败龙，而F表示小美被龙打败。如果小美被龙连续打败三次，那小美就会输掉游戏。请你帮忙计算小美最少需要多少点 MP才能通关。

输入描述
第一行三个数 n, c1, c2。(1 ≤ n ≤ 100000，1 ≤ c1, c2 ≤ 1000000000)。
第二行 n 个字符，第 i 个字符 si 代表小美与第 i 场战斗的结果。si 是 T 代表小美打败龙，si 是 F 代表小美被龙打败。
输出描述
输出一个数，代表小美最少需要的MP值。

样例输入
10 7 3
FTFFFTFFFF
样例输出
6

提示
小美可以在第3场战斗、第8场战斗中使用第二个技能，需要耗费3×2=6点MP。
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
import java.util.Scanner;
public class problem2 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int c1 = sc.nextInt();
int c2 = sc.nextInt();
char []si = sc.next().toCharArray();
if(n != si.length);
int index = 0;
int count = 0;
while (index < si.length) {
//如果当前的出现F，则需要判断有几个F是连续的；
if (si[index] == 'F') {
int tmpCount = 0;
while (index < si.length && si[index] == 'F') {
index++;
tmpCount++;
}
count += tmpCount/3;
}else {
index++;
}
}
System.out.println((int)Math.min(c1, c2)*count);
}
}
3、小美记数字
时间限制： 3000MS
内存限制： 1048576KB

题目描述：
小美的记忆力超级棒，小团决定来考一考小美。小团给了小美 n 个数，从左到右排成一行，给了1 分钟让小美记住。然后小团会询问 m 次，每次都问数 x 第一次出现的位置和最后一次出现的位置，若数 x 没出现过，那么回答 0 即可。小美的记忆力好，但是 1 分钟记住这么多数实在是太难了，请你帮帮小美，完成这次不可能的挑战。

输入描述
第一行两个数 n, m。(1 ≤ n, m ≤ 50000)。
第二行 n 个数，第 i 个数是 ai。(1 ≤ ai ≤ 1000000000)。
接下来 m 行，每行一个数 x (1 ≤ x ≤ 1000000000)，代表一次询问。

输出描述
输出 m 行，若数 x 出现过，输出数 x 第一次出现的位置和最后一次出现的位置。若数 x 没出现过，输出 0。

样例输入
6 4
2 3 1 2 3 3
1
2
3
4
样例输出
3 3
1 4
2 6
0

提示
1 出现的位置有 3，所以答案为 3 3。
2 出现的位置有 1, 4，所以答案为 1 4。
3 出现的位置有 2, 5, 6，所以答案为 2 6。
4 没有出现过，所以答案为 0
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
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Scanner;
public class problem3 {
public static void main(String[] args) {
// 输入
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
}
int[] target = new int[m];
for (int i = 0; i < m; i++) {
target[i] = sc.nextInt();
}
// 记录数字出现的位置
HashMap<Integer, Deque<integer>> map = new HashMap<Integer, Deque<integer>>();
for (int i = 0; i < num.length; i++) {
Deque<integer> tmp = null;
if (map.containsKey(num[i])) {
tmp = map.get(num[i]);
} else {
tmp = new ArrayDeque<integer>();
}
tmp.add(i + 1);
map.put(num[i], tmp);
}
// 输出结果
for (int i = 0; i < target.length; i++) {
Deque<integer> tmp = map.get(target[i]);
if (tmp == null) {
System.out.println(0);
} else {
System.out.println(tmp.peekFirst() + " " + tmp.peekLast());
}
}
}
}
4、小美中奖啦
时间限制： 3000MS
内存限制： 1048576KB</integer></integer></integer></integer></integer>

题目描述：
小美超级幸运，这不今天又双叒叕中奖了！！！主办方给了小美 n 个积分球，从左到右排成一行，第 i 个积分球的积分为 ai 。让小美自行选取其中一段连续的积分球，最多选取k 个。假设小美选取了 [l, r] 这个区间中的积分球，小美获得的积分为al⊕al+1⊕…⊕ar-1⊕ar。例如，小美选取了 [3, 4, 2] 这三个积分球那么小美最终获得的积分为 3⊕4⊕2 = 5。
小美想要获得最多的积分。小美虽然幸运，但是却被这个难题难倒了，请你帮帮小美，帮她获得更多积分。
⊕：异或运算的数学符号。其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。例如：3⊕5=(011)2 ⊕ (101) 2 = (110) 2 = 6。
异或在C语言中表示为^。

输入描述
第一行两个数 n, k。(1 ≤ n, k ≤ 100000)。
第二行 n 个数，第 i 个数是 ai。(0 ≤ ai ≤ 1000000000)。

输出描述
输出一个数，代表小美能够获得的最多积分。

样例输入
3 2
1 2 4
样例输出
6

提示
小美有如下几种选择。
①选取区间 [1, 1] 中的积分球，获得积分为 1。
②选取区间 [1, 2] 中的积分球，获得积分为 3。
③选取区间 [2, 2] 中的积分球，获得积分为 2。
④选取区间 [2, 3] 中的积分球，获得积分为 6。
⑤选取区间 [3, 3] 中的积分球，获得积分为 4
这一题一开始是构造的矩阵，利用动态规划；但是内存会超过限制，后来改成了使用ArrayList数据结构
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class problem4 {
public static void main(String[] args) throws IOException {
// 输入
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strW = br.readLine().trim().split(" ");
int n = Integer.parseInt(strW[0]);
int k = Integer.parseInt(strW[1]);
String[] numW = br.readLine().trim().split(" ");
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = Integer.parseInt(numW[i]);
}
// 动态规划，构造矩阵
int max = 0;
for (int i = 0; i < n; i++) {
ArrayList<integer> list = new ArrayList<integer>();
for (int j = 0; j < k; j++) {
if(j == 0) {
list.add(num[i]);
max = Math.max(max, num[i]);
}else {
if(i + j < n) {
int tmp = list.get(list.size()-1) ^ num[i+j];
list.add(tmp);
max = Math.max(max, tmp);
}
}
}
}
System.out.println(max);
}
}
5、银杏树
时间限制： 3000MS
内存限制： 786432KB</integer></integer>

题目描述：
小美负责维护某人民公园内的所有银杏树。
公园里有 n 棵银杏，编号为 1…n，第i棵树的高度为 hi。但是树木太多，她自己一个人肯定无法完成任务，于是她找了一些同学，并将他们分为两组。
为了公平，小美要确定两组的工作量（总爬树高度）一样多，而且小美也要参与工作。于是小美这样安排：自己先选一棵树 x 进行修剪，编号为 [x + 1, n] 的树重新编号为 [x，n - 1]，[1，x - 1] 的部分编号不变。对于新的编号，奇数编号的树由一队同学修剪，偶数编号的树由另一队同学修剪。
请帮小美计算，自己选择可以选择修剪哪些树才能让两组同学的工作量（总爬树高度）一样多。并输出方案数。

输入描述
第一行一个正整数 n，表示一共有 n 棵树；
第二行 n 个正整数 hi，第 i 个正整数表示第 i 棵树高度为 hi。
1 ≤ n ≤ 2×105, 1 ≤ hi ≤ 104。

输出描述
如果无论小美怎么选择，都没有一种方案可以使得两组工作量相同，则只输出一行一个数 0。
否则输出两行，第一行输出一个正整数表示小美选择树的方案数，第二行从小到大输出小美可以选择修剪树的编号，每两个编号之间有一个空格。请不要输出行末空格。

样例输入
4
1 4 2 3
样例输出
1
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class problem5 {
public static void main(String[] args) throws IOException {
// 输入
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] numW = br.readLine().trim().split(" ");
int[] height = new int[n];
for (int i = 0; i < n; i++) {
height[i] = Integer.parseInt(numW[i]);
}

    PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
    for (int i = 0; i < height.length; i++) {
        //确定树的编号
        int sumOdd = 0,sumOuShu = 0;
        for (int j = 0; j < height.length; j++) {
            if (j < i) {//编号不变i+1
                int bianhao = j + 1;
                if (bianhao % 2 == 0) {
                    sumOdd += height[j];
                }else {
                    sumOuShu += height[j];
                }
            }else if(j > i) {//编号+1：i+1-1=i
                int bianhao = j;
                if (bianhao % 2 == 0) {
                    sumOdd += height[j];
                }else {
                    sumOuShu += height[j];
                }
            }
        }
        if(sumOdd == sumOuShu) {
            queue.add(i + 1);
        }
    }
    System.out.println(queue.size());
    while (!queue.isEmpty()) {
        if (queue.size() == 1) {
            System.out.print(queue.poll()+" ");
        }else {
            System.out.print(queue.poll()+" ");
        }
    }
}

}