🔥 10.9 奇安信笔试面经 - 编程题 & 题解

考试平台： 牛客

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

考试题型: 选择题 + 2道编程题(核心编程模式)

投递岗位： Java 开发

P1

在一年一度的芭莎明星慈善夜上，组织者邀请了一众国际知名的明星参加。为了能够筹得更多的善款，组织者特地安排了一场名为”凝聚爱心，美育未来”的活动。 每位明星都愿意为慈善事业贡献一定的善款，捐赠金额各不相同。然而，由于一些私人恩怨或者竞争关系，一些明星不愿意与他们不喜欢的明星一起捐款。为了避免尴尬的情况发生，如果明星i捐款，那么他旁边的两位明星i-1 和+1就会拒绝捐款。

由于晚会的座位是围成一个圆圈的，因此第一位明星和最后一位明星会坐在一起即，如果第一位明星捐款，最后一位明星会拒绝捐款:反之亦然

活动组织者希望能够筹集到最大限度的善款，因此他们需要制定一个策略，来决定哪些明星应该捐款。他们聘请了你，作为数据科学家和算法专家，来帮助他们解决这个问题

示例1

输入：
[10, 3,2, 5,7,8,11]

输出：
[23]

说明：
捐款的明星是第1位、第4位和第6位

示例2

输入：
[10, 3, 2, 5, 7, 8]

输出：
19

说明：
捐款的明星是第1位、第3位和第5位

备注

输入： 一个整数数组，包含n个元素，元素值为X。其中 .

输出： 最大限度的善款值

题解

动态规划, LCR 090. 打家劫舍 II 原题

/**
 * P1
 * @author code5bug (同v)
 */
class Solution {
    public int maximizeDonations(int[] d) {
        int n = d.length;
        if (n == 0) return 0;
        else if (n == 1) return d[0];
		
        // 不选最后一个元素时
        int[] arr1 = Arrays.copyOfRange(d, 0, n - 1);
        // 不选第一个元素时
        int[] arr2 = Arrays.copyOfRange(d, 1, n);
        return Math.max(solve(arr1), solve(arr2));
    }

    public int solve(int[] arr) {
        int n = arr.length;

        // dp[i][0] 表示前 i 个元素中，第 i 个元素不选时的最大值
        // dp[i][1] 表示前 i 个元素中，第 i 个元素选择时的最大值
        int[][] dp = new int[n + 1][2];
        for (int i = 0; i < n; i++) {
            int max = Math.max(dp[i][0], dp[i][1]);
            dp[i + 1][0] = max;
            // 选择当前元素时
            dp[i + 1][1] = Math.max(dp[i][0] + arr[i], max);
        }
        return Math.max(dp[n][0], dp[n][1]);
    }
}

P2

在一个受欢迎的多人在线战术游戏《战略与征服》中，玩家可以通过各种任务和挑战收集资源。在这个游戏中，当玩家收集一个资源时，系统会记录一个“1”，而消耗一个资源时，系统会记录一个“0”。为了保持游戏的公平性和平衡性，游戏开发者希望验证玩家的资源收集和消耗记录的合法性，确保没有玩家能够通过非法手段获取或消耗资源。给定一个整数数组，其中“1”代表玩家收集一个资源，“0”代表玩家消耗一个资源，你需要编写一个程序来判断这个记录序列是否是合法的。一个合法的序列需要满足以下两个条件：

• 序列中收集和消耗的资源数量相等。
• 序列的任意前缀中，收集的资源数量都不少于消耗的资源数量。

示例1

输入：
[1, 0, 1, 1, 1, 0, 0, 1, 0, 0]

输出：
true

示例2

输入：
[1, 0, 1, 1,1,0, 0, 1, 0]

输出：
false

题解

简单模拟

/**
 * P2
 * @author code5bug (同v)
 */
class Solution {
    public boolean solve(int[] a) {
        int cnt = 0;
        for (int t : a) {
            cnt += (t == 1) ? 1 : -1;
            
            // 序列的任意前缀中，收集的资源数量都不少于消耗的资源数量。
            if (cnt < 0) return false;
        }

        // 序列中收集和消耗的资源数量相等
        return cnt == 0;
    }
}

算法辅导，秋招助力，需题解欢迎笔试真题投稿

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