🔥 10.8 金山笔试面经 - 编程题 & 题解

考试平台： 牛客

考试时间: 2023-10-08 (120 分钟)

考试题型: 40 分选择题 + 60 分编程题

P1

小红有很多小写字母。她准备用一些字母构造一个单词。已知一个合法的单词不能有两个辅音相邻，例如“cat”是合法的单词，但“than"”不是合法的单词。小红想知道，自己能构造的最大长度的单词有多长?注:元音字母有”a、e、i、0、u"五种。

输入描述

一个只包含小写字母的字符串，长度不超过100000

输出描述

小红可以组成的最大单词长度

示例1

输入：
aaatra

输出：
6

说明：
taaraa为一种合法的构造。

示例2

输入：
tqqa

输出：
3

说明：
gaq为一种合法的构造。

题解

贪心

import java.util.Scanner;

/**
 * P1
 * 
 * @author code5bug (同v)
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] cs = in.next().toCharArray();

        // cnt 元音字母个数
        int n = cs.length, cnt = 0;
        for (char c : cs) {
            if ("aeiou".indexOf(c) > -1) cnt++;
        }

        // 不能有两个辅音相邻，因此辅音字母最多 cnt+1 个
        System.out.println(cnt + Math.min(n - cnt, cnt + 1));
    }
}

P2

某次篮球比赛前，需要将站成一排的n名球员分为两队(两队人数可以不同)，每名球员的能力值为 。 有两名教练轮流挑选队员，第一个教练先挑选。每位教练每次选人时，都会选择当前剩余的所有人中，能力值最大的那一个。当选择一个人后，会将他左右两侧各m个人一起挑选走 (若某一侧可选的人数不够m人，则将这一侧能选的人都选上)。请输出此规则下，分到两队的具体成员情况。

输入描述

第一行两个正整数，球员人数n，一起挑走的球员左右各m人;

第二行几个正整数，每名球员的能力值 。

输出描述

一个长度为n的字符串，第i位只包含 A和B，A表示第名球员被挑选到第一个队伍，B代表第二个队伍。

示例1

输入：
7 1
3 6 1 7 2 5 4

输出：
BBAAABA

说明：
A先挑选7，按规则带走7的两边各一人1和2，剩余的球员为3 6 5 4;
B挑选6，按规则带走6的两边各一人3和5，剩余的球员为4;
A挑选4，组队结束。

示例2

输入：
10 2
4 8 9 10 7 6 5 3 2 1

输出：
BAAAAABBBA

说明：
A先挑选10，按规则带走10的左边的8 9和右边的7 6，剩余的球员为4 5 3 2 1；
B挑选5，按规则带走5的左边的4和右边的3 2，剩余的球员为1，
A挑选1，组队结束。

题解

模拟

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * P2
 * @author code5bug (同v)
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[] a = new int[n];
        PriorityQueue<Integer> queue = new PriorityQueue<>((i1, i2) -> a[i2] - a[i1]);
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            queue.offer(i);
        }

        int user = 0, select = 0;
        char[] rs = new char[n];
        while (select < n) {
            while (rs[queue.peek()] != 0) queue.poll();
            int idx = queue.poll(); // 能力值最大的球员

            // 左侧 m + 1个元素
            for (int cnt = m + 1, i = idx; cnt > 0 && i >= 0; i--) {
                if (rs[i] == 0) {
                    rs[i] = (user % 2 == 0) ? 'A' : 'B';
                    cnt--;
                    select++;
                }
            }

            //右侧　ｍ　个元素
            for (int cnt = m, i = idx + 1; cnt > 0 && i < n; i++) {
                if (rs[i] == 0) {
                    rs[i] = (user % 2 == 0) ? 'A' : 'B';
                    cnt--;
                    select++;
                }
            }

            PriorityQueue<Integer> temp = new PriorityQueue<>((i1, i2) -> a[i2] - a[i1]);
            while (!queue.isEmpty()) {
                Integer i = queue.poll();
                if (rs[i] == 0) temp.offer(i);
            }
            queue = temp;

            user++;
        }

        System.out.println(new String(rs));
    }
}

P3

已知山体上的雪球向下滚动时，雪球每向下滚动1的距离，体积会膨胀x倍。

例如，海拔高度为2的、初始大小为1雪球，当它滚到海拔高度为0的地面时，若x=5其大小会变成1*5*5=25。

现在每个海拔为 i 的高度都生成了个大小为1的雪球。当它们全部滚动到地面时请你求出所有雪球的大小总和。答案对10^9+7取模。

输入描述

在第一行中，给出山的高度H和雪球增加的程度 x。 在第二行到H+1行表示在山上生成的雪球数量，其中第 i + 1行的数字表示在高度为 i 处制成的雪球的数量 。

输出描述

输出从山上滚下的所有雪球的大小总和，答案对10^9+7取模。

示例1

输入：
4 5
1
3
2
4

输出：
2860

说明：
通过累加计算全部雪球的大小总和为1x5+3x25+2x125+4x625=2830

示例2

输入：
3 1
1
2
3

输出：
6

说明：
通过累加计算全部雪球的大小总和为1X1 + 2X1 + 3x1 = 6

题解

模拟

import java.util.Scanner;

/**
 * P3
 * @author code5bug (同v)
 */
public class Main {
    static int MOD = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int H = in.nextInt(), x = in.nextInt();

        long rs = 0L, f = 1L;
        for (int i = 1; i <= H; i++) {
            int a = in.nextInt();
            f = (f * x) % MOD;
            rs = (rs + f * a) % MOD;
        }
        System.out.println(rs);
    }
}

如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。