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;
        }
    }
}

拓展

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：

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算法

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];
    }
}