2019届百度秋招笔试题【混战世界】【字符串计数】

95 阅读 0 评论 63 点赞

我是靠谱客的博主坦率冥王星，这篇文章主要介绍2019届百度秋招笔试题【混战世界】【字符串计数】，现在分享给大家，希望可以做个参考。

`混战世界`

1.题目描述

战乱年代。整个世界各个军阀的英团泄战，你是P7军团的战略参谋，你手下n(保证为3的倍数)个士兵，第i个土兵的物理攻击数值为Ai，魔法攻击数值为Bi，你需要将这些士兵三等分为三个连，

第一个连需要去物理空间参加物理对抗战争，战斗力估值W1为士兵的物理攻击数值之和:
第二个连需要去魔法空间参加魔法对抗战争，战斗力估值W2为士兵的魔法攻击数值之和:
第三个连需要去虚幻空间参加物理魔法装备的综合对抗战争，战斗力估值W3为所有士兵的物理攻击数值、魔法攻击数值之和除以2。

你希望W1+W2+W3最大。这样才最有可能胜利。
输入描述:
第一行一个整数n，保证为3的倍数。(3≤n≤1000）
第二行n个整数，第i个数表示Ai。
第三行n个整数，第i个数表示Bi。(I≤Ai， Di≤1000)
输出描述:
一个小数，表示最大数之和,保留两位小数(四舍五入)。
输入样例:
6
1 7 3 4 5 9
2 3 9 4 3 3
输出样例:
35.00

2.解题思路

设一个人的物理值为A,魔法值为B.
派去一连可得A的贡献，二连可得B, 三连可得(A+B)/2。

去一连与去三连相比差了(A-B)/2.去二连比去三连也差(A-B)/2。这样，可以根据每个人的A-B数值进行排序，
由题意可知，A越大越适合去1连，B越大越适合去2连，故（A-B）/2中，较大者1连，较小者去2连，中间的去3连。

3.代码

复制代码

import java.text.DecimalFormat;
import java.util.*;
public class Main {
public static void main(String[] args) {
//
int a[] = {1,7,3,4,5,9};
//
int b[] = {2,3,9,4,3,3};
//
System.out.println(String.format("%.2f",solution(a,b)));
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
int b[] = new int[n];
for(int i = 0;i<n;i++){
a[i] = sr.nextInt();
}
for(int i = 0;i<n;i++){
b[i] = sr.nextInt();
}
solution(a,b);
}
public static void solution(int A[],int B[]){
Diff []list= new Diff[A.length];
for(int i = 0;i<A.length;i++){
list[i] = new Diff(i,A[i] - B[i]);
}
//里面的list已经从小到大排序了
Arrays.sort(list);
double res = 0;
//取值,较小的去2连，中间的去三连，较大的去1连
int Avglen = list.length/3;
for(int i = 0;i<list.length;i++){
//（A-B）较小者去2连
if(0<=i && i<Avglen ){
res += B[list[i].index];
//（A-B）中间者去3连,这里注意要乘个1.0,避免除以2会强转为int型
}else if(i >= Avglen && i< 2 *Avglen ){
res += ((A[list[i].index] + B[list[i].index])*1.0)/2;
}else{
//(A-B)较大者去1连
res += A[list[i].index];
}
}
DecimalFormat df = new DecimalFormat("#.00");
System.out.println(df.format(res));
}
//用于存储索引坐标以及（Ai-Bi）
static class Diff implements Comparable{
int index;
int value;
public Diff(int index, int value) {
this.index = index;
this.value = value;
}
public int getIndex() {
return index;
}
//按照（A-B）/2 进行排序
@Override
public int compareTo(Object o) {
Diff diff = (Diff) o;
if(this.value > diff.value)
return 1;
else if(this.value == diff.value)
return 0;
else
return -1;
}
}
}

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
66
67
68
69
70
71
72
import java.text.DecimalFormat;
import java.util.*;
public class Main {
public static void main(String[] args) {
//
int a[] = {1,7,3,4,5,9};
//
int b[] = {2,3,9,4,3,3};
//
System.out.println(String.format("%.2f",solution(a,b)));
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
int b[] = new int[n];
for(int i = 0;i<n;i++){
a[i] = sr.nextInt();
}
for(int i = 0;i<n;i++){
b[i] = sr.nextInt();
}
solution(a,b);
}
public static void solution(int A[],int B[]){
Diff []list= new Diff[A.length];
for(int i = 0;i<A.length;i++){
list[i] = new Diff(i,A[i] - B[i]);
}
//里面的list已经从小到大排序了
Arrays.sort(list);
double res = 0;
//取值,较小的去2连，中间的去三连，较大的去1连
int Avglen = list.length/3;
for(int i = 0;i<list.length;i++){
//（A-B）较小者去2连
if(0<=i && i<Avglen ){
res += B[list[i].index];
//（A-B）中间者去3连,这里注意要乘个1.0,避免除以2会强转为int型
}else if(i >= Avglen && i< 2 *Avglen ){
res += ((A[list[i].index] + B[list[i].index])*1.0)/2;
}else{
//(A-B)较大者去1连
res += A[list[i].index];
}
}
DecimalFormat df = new DecimalFormat("#.00");
System.out.println(df.format(res));
}
//用于存储索引坐标以及（Ai-Bi）
static class Diff implements Comparable{
int index;
int value;
public Diff(int index, int value) {
this.index = index;
this.value = value;
}
public int getIndex() {
return index;
}
//按照（A-B）/2 进行排序
@Override
public int compareTo(Object o) {
Diff diff = (Diff) o;
if(this.value > diff.value)
return 1;
else if(this.value == diff.value)
return 0;
else
return -1;
}
}
}

在这里插入图片描述

拓展

java里面保留数值的位数(四舍五人)
方法1：
System.out.println(String.format("%.2f",num));
方法2：
DecimalFormat df = new DecimalFormat("#.00");
System.out.println(df.format(num));

`字符串计数`

1.题目描述

给定一个仅由小写字母组成且长度不超过10^6的字符串，将首字符移到末尾并记录所得的字符串，不断重复该操作，虽然记录了无限个字符串，但其中不同字符串的数目却是有限的，那么一共记录了多少个不同的字符串？
样例输入
abab
样例输出
2
样例解释
记录了abab和baba这2个不同的字符串。

2.解题思路

方法1：对字符串不断进行重组，对不同的字符串进行入队，最后返回队列的大小即为不同的字符串个数

方法2：利用kmp算法的next数组，可以求出字符串的最小循环周期T，这就是答案

3.代码

方法1：

复制代码

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
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);
String str = sr.nextLine();
System.out.println(solution(str));
}
public static int solution(String str){
if(str == null )
return 0;
else if(str.trim().equals(""))
return 1;
else if(str.length() == 0)
return 0;
else{
List<String> list = new ArrayList<>();
String temp = str;
list.add(str);
for(int i = 0;i<str.length();i++){
//首字符移到末尾并记录所得的字符串，
temp = temp.substring(1,temp.length())+temp.charAt(0);
//如果list里面没有该字符串则加入list
if(!list.contains(temp)){
list.add(temp);
}
}
return list.size();
}
}

请检查是否存在数组越界等非法访问情况
case通过率为50.00%

不知道哪里错了。哭泣

方法2：KMP算法

复制代码

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
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);
String str = sr.nextLine();
System.out.println(kmp(str));
}
public static int kmp(String str){
int len = str.length();
int [] next = new int[len+1];
next[0] = -1;
int k = -1;
int j
= 0;
while (j < len ){
if(k== -1 || str.charAt(k) == str.charAt(j)){
next[++j] = ++k;
}else{
k = next[k];
}
}
//next[j] = k 代表p[j] 之前的模式串子串中，有长度为k 的相同前缀和后缀，这里next[len]表示len-1之前的模式串，即为str时,有k的相同的前缀和后缀
//所以循环周期T为 总长度-相同前缀数
int res = len % (len - next[len]);
if(res != 0)
return len;
else
return len-next[len];
}
}