百度2019校招笔试真题 1.混战世界 2.字符串计数

72 阅读 0 评论 48 点赞

我是靠谱客的博主开放面包，最近开发中收集的这篇文章主要介绍百度2019校招笔试真题 1.混战世界 2.字符串计数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.混战世界

【题目描述】战乱年代。整个世界各个军阀的英团泄战，你是P7军团的战略参谋，你手下n(保证为3的倍数)个士兵，第i个土兵的物理攻击数值为Ai，魔法攻击数值为Bi，你需要将这些士兵三等分为三个连，第一个连需要去物理空间参加物理对抗战争，战斗力估值W1为士兵的物理攻击数值之和；
第二个连需要去魔法空间参加魔法对抗战争，战斗力估值W2为士兵的魔法攻击数值之和；第三个连需要去虚幻空间参加物理魔法装备的综合对抗战争，战斗力估值W3为所有士兵的物理攻击数值、魔法攻击数值之和除以2。
你希望W1+W2+W3最大。这样才最有可能胜利。
原题地址：牛客网原题链接
输入描述:
第一行一个整数n，保证为3的倍数。（3≤n≤100000）
第二行n个整数，第i个数表示Ai。
第三行n个整数，第i个数表示Bi。（1≤Ai, Bi≤1000）

输出描述:
一个小数，表示最大数值和，保留两位小数（四舍五入）。
示例1
输入:
6
1 7 3 4 5 9
2 3 9 4 3 3
输出:
35.00
说明:
第一个连：士兵2，士兵6，战斗力估值W1=7+9=16

第二个连：士兵1，士兵3，战斗力估值W2=2+9=11

第三个连：士兵4，士兵5，战斗力估值W3=[(4+4)+(5+3)]/2=8

16+11+8=35

解题思路：
设一个人的物理值为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连。

import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 士兵数组
Person []persons= new Person[n];
for(int i = 0;i<n;i++){
int tmp=sc.nextInt();
// 数组中的Person对象必须先初始化
persons[i]=new Person();
persons[i].physical=tmp;
}
for(int i = 0;i<n;i++){
// 上面以及初始化过了
persons[i].magic=sc.nextInt();
}
// 按照A-B的大小进行排序
Arrays.sort(persons,new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
// 由大到小排序
return (o2.physical-o2.magic)-(o1.physical-o1.magic);
}
});
// 小数默认double型
double res = 0.0;
// 数组中前n/3个去1连，中间n/3去2连，后面3个去3连
int count = n/3;
for(int i = 0;i<n;i++){
// 前3个 物理攻击大 1连
if(0<=i && i<count ){
res += persons[i].physical;
//（A-B）中间者去3连,这里注意要乘个1.0,避免除以2会强转为int型
}else if(i >= count && i< 2 *count ){
res += ((persons[i].physical + persons[i].magic)*1.0)/2;
}else{
// 后3个 去2连
res += persons[i].magic;
}
}
DecimalFormat df = new DecimalFormat("#.00");
System.out.println(df.format(res));
}
static class Person {
public int physical;
public int magic;
public void setPhysical(int physical) {
this.physical = physical;
}
public void setMagic(int magic) {
this.magic = magic;
}
public int getPhysical() {
return physical;
}
public int getMagic() {
return magic;
}
}
}

2.字符串计数

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

解题思路：
1.利用kmp算法的next数组，可以求出字符串的最小循环周期T
2.对字符串不断进行重组，对不同的字符串进行入队，最后返回队列的大小即为不同的字符串个数

public static int getResult(String str){
int len = str.length();
int [] next = new int[len+1];
next[0] = -1;
int k = -1;
int j
= 0;
// 构建next数组
while (j < len ){
if(k== -1 || str.charAt(k) == str.charAt(j)){
next[++j] = ++k;
}else{
k = next[k];
}
}
int res = len % (len - next[len]);
if(res != 0)
return len;
else
return len-next[len];
}