程序员社区

牛客网2021校招模拟笔试一模(三月份)编程题解析

题目1:天弃之子

标题:天弃之子

时间限制: 3秒 内存限制: 262144k 语言限制:不限

有一款游戏,过关的方式是按按钮。游戏一共有几关,每一关有a[i]个按钮,其中只有唯一一个按钮是可以通关的,按下其他的按钮游戏就会失败。

好在这个游戏可以重来,而且由于设计者的疏忽,每一关的通关按钮是不变的,所以你可以记住前几关的按钮,重来时就可以直接通关。

但是你的运气似乎用在了其他地方,你使用了最多的按按钮次数才成功通关。求这个最多的按按钮次数吧!

解题思路

题目提炼: 游戏共有n关,每一关有a[i]个按钮,其中只有一个可以过关,选择错误就会重新开开始,玩家可以通过试错记住正确的按钮。

问玩家运气最差时(每一.关都要试a[i]次才过关)共需要按多少次按钮才能通关。

这道题最重要的环节就是读懂题目,从题意中分析出:每一关都要试a[i]次。 之后就比较容易了。

对于每一关来说,都要进行a[i]-1次失败

每次失败要先通过前面的i-1关,再算上当前这关,需要按i次按钮

所以往答案里累加(a[i]-1)*i

最后再算上最终成功的那一次,通过n关需要按n次按钮即可

代码(两种写法)


public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param buttons int整型一维数组 * @return long长整型 * 没有转long就会报错,所以一定要转。 */
    public long findMaxButtons (int[] buttons) {
   
        // write code here
        long count = 0;
        for(int i =0;i<buttons.length;i++){
   
            if(buttons[i]==1) {
   
                count += 1;
                continue;
            }
            else{
   
                long tmp = (i+1)*(buttons[i]-1)+1;
                count+=tmp;
            }
        }
        return count;
    }

}
 public long findMinButtons2(int[] a){
   
        long res = a.length;
        for (int i = 0; i < a.length; i++) {
   
            res+=(long) (a[i]-1)*(i+1);
        }
        return res;
    }

题目2:刷墙

解题思路

思路:枚举+前缀和

前缀和不懂的可以看一下下图。

image-20210318222912399

题目提炼:一个长度为n的01串,要把串变成某个位置及其左边全是1,右边全是0至少要修改几个字符

image-20210318223907990

把【1,i】这个区间内的数全变成1的次数,等于这个区间内0的个数

把【i+1,n】这个区间内的数全变成0的次数,等于这个区间1的个数

所以我们只要去枚举每一位要转变的次数,取最小的那个值即可。

为了简化时间复杂度,我们可以预处理前缀和 s u m [ i ] sum[i] sum[i] [ 1 , i ] [1,i] [1,i]中的个数

然后就可以在O(1)的时间复杂度内求出每个分界点要变化的数的个数,更新答案即可。

代码

import java.util.Scanner;

/** * Author:Viper * Data:2021/3/18 * description: */
public class shuaqiang {
   
    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //开始连一个空格,使得s.charAt(0)为空,数组从1开始,方便计算。
        String s = ' '+sc.next();
        int[] sum = new int[n+1];
        for (int i = 1; i <=n ; i++) {
   
            sum[i]=sum[i-1]+s.charAt(i)-'0';
        }
        int res = n;
        for(int i=0;i<=n;i++){
   
// [1,i]中0的个数为i-sum[i]
// [i+1, n]中‘1’的个数为sum[n]-sum[i]
            res = Math.min(res,i-sum[i]+sum[n]-sum[i]);
        }
    }
}

题目3:胜者为王

标题:胜者为王

时间限制:1秒 内存限制: 262144k |语言限制:不限

小明,小王,小李三人正在进行一个游戏。游戏有n个回合,每个人都有一个字符串,三人的字符串长度相等。

每个回合他们必须更改自己字符串中的一个字母。最后每个人的分数是字自己的字符串中出现字符最多的字母的数量。

分数最高者获胜,输出获胜者名字,小明获胜输出xiaoming,小王获胜输出xiaowang,小李获胜输出xiaoli,如果有两个或者两个以上相同的最高分输出draw.

image-20210318225130165

输出描述:输出一行一个字符串,表示游戏结果。

示例:

输入

7
treasurehunt
threefriends
hicodeforces

输出

xiaowang

解题思路

**题目提取:**三个人各自拥有一个字符串,他们的字符串长度相等,游戏进行n,回合,每回合每个人必须修改自己字符串中的一个字母,每个人最终得分是他字符串中出现次数最多的字母数量,判断谁最终得分最多。

本题可以采用贪心,选择每个人出现最多的一个字母,并且尽量将其他字母改为这个字母。

设出现次数最多的字母数量是X,再进行n回合,这个字母就可以有min(x+n,len)个

代码

import java.util.Arrays;
import java.util.Scanner;

/** * Author:Viper * Data:2021/3/18 * description: */
public class shengzheweiwang {
   

    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String a = sc.next();
        String b = sc.next();
        String c = sc.next();
        int[] cnt = new int[256];
        int x = 0, y = 0, z = 0;
        for (int i = 0; i < a.length(); i++) {
   
            x = Math.max(x, ++cnt[a.charAt(i)]);
        }
        Arrays.fill(cnt, 0);
        for (int i = 0; i < a.length(); i++) {
   
            y = Math.max(y, ++cnt[b.charAt(i)]);
        }
        Arrays.fill(cnt, 0);
        for (int i = 0; i < a.length(); i++) {
   
            z = Math.max(z, ++cnt[c.charAt(i)]);
        }

        int len = a.length();
        x = Math.min(x + n, len);
        y = Math.min(y + n, len);
        z = Math.min(z + n, len);
        if (x > y && x > z) System.out.println("xiaoming");
        else if (y > x && y > z) System.out.println("xiaowang");
        else if (z > x && z > y) System.out.println("xiaoli");
        else System.out.println("draw");
    }
}

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 牛客网2021校招模拟笔试一模(三月份)编程题解析

一个分享Java & Python知识的社区