笔试时间：2025年7月27日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

为排成一列的人分配糖果，规则：每人至少1颗糖；相邻两人中评分更高者需获得更多糖果。

输入描述

评分数组ratings（如[1,0,2]）

输出描述

最少糖果总数。

样例输入

[1,0,2]

样例输出

5

参考题解

双向贪心。

C++：

// C++ (LeetCode-style)
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int candy(vector<int>& ratings) {
        if (ratings.empty()) return 0;
        int n = ratings.size();
        vector<int> cand(n, 1);
        
        // Left-to-right pass
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                cand[i] = cand[i - 1] + 1;
            }
        }
        
        // Right-to-left pass
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) {
                cand[i] = max(cand[i], cand[i + 1] + 1);
            }
        }
        
        // Sum up
        int total = 0;
        for (int x : cand) total += x;
        return total;
    }
};

Java：

// Java (LeetCode-style)
class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int n = ratings.length;
        int[] cand = new int[n];
        Arrays.fill(cand, 1);
        
        // Left-to-right pass
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                cand[i] = cand[i - 1] + 1;
            }
        }
        
        // Right-to-left pass
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                cand[i] = Math.max(cand[i], cand[i + 1] + 1);
            }
        }
        
        // Sum up
        int total = 0;
        for (int x : cand) total += x;
        return total;
    }
}

Python：

class Solution:
    def candy(self, ratings):
        if not ratings:
            return 0
        
        n = len(ratings)
        cand = [1] * n
        
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                cand[i] = cand[i - 1] + 1
        
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                cand[i] = max(cand[i], cand[i + 1] + 1)
        
        return sum(cand)

第二题

小文需要从多门课程中选择，每门课程有开始时间t1、结束时间t2和价值value。要求选择的课程时间不冲突，且总价值最大。

输入描述

第一行：n

接下来n行，每行t1, t2, value

输出描述

最大总价值（整数）

样例输入

3

1 10 10

3 4 11

4 5 3

样例输出

14

参考题解

第二题考察区间贪心+动态规划优化，首先，将所有课程按照结束时间 t2 升序排序。这样做的目的是让结束时间早的课程优先被考虑，为后续课程留出更多的时间选择空间，对于每个课程 i，我们需要找到在它之前结束且不与它时间冲突的最后一个课程 j（即 j 的结束时间 t2 小于等于 i 的开始时间 t1）。这一步可以通过二分查找来高效完成，之后我们用动态规划求最大值。定义 dp[i] 表示考虑前 i 个课程时的最大价值。状态转移方程为：- 如果不选当前课程 i，则 dp[i] = dp[i-1]。- 如果选当前课程 i，则 dp[i] = value[i] + dp[j]，其中 j 是 i 的前驱课程。- 最终 dp[i] 取这两种情况的最大值。最终答案即为dp[-1] 。

C++：

// C++17
#include <bits/stdc++.h>
using namespace std;

struct Interval {
    long long s, e, v;
};

int find_last(const vector<Interval>& cs, int i) {
    int l = 0, h = i - 1, res = -1;
    long long start_i = cs[i].s;
    while (l <= h) {
        int m = l + (h - l) / 2;
        if (cs[m].e <= start_i) {
            res = m;
            l = m + 1;
        } else {
            h = m - 1;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Interval> cs(n);
    for (int i = 0; i < n; ++i) {
        cin >> cs[i].s >> cs[i].e >> cs[i].v;
    }

    // sort by end time
    sort(cs.begin(), cs.end(), [](auto &a, auto &b) {
        return a.e < b.e;
    });

    vector<long long> dp(n);
    dp[0] = cs[0].v;

    for (int i = 1; i < n; ++i) {
        long long include_i = cs[i].v;
        int j = find_last(cs, i);
        if (j != -1) include_i += dp[j];
        dp[i] = max(dp[i - 1], include_i);
    }

    cout << dp[n - 1] << "\n";
    return 0;
}

Java：

// Java 11+
import java.util.*;

public class Main {
    static class Interval {
        long s, e, v;
        Interval(long s, long e, long v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }

    // binary search for the last interval ending ≤ cs[i].s
    static int findLast(List<Interval> cs, int i) {
        int l = 0, h = i - 1, res = -1;
        long start_i = cs.get(i).s;
        while (l <= h) {
            int m = l + (h - l) / 2;
            if (cs.get(m).e <= start_i) {
                res = m;
                l = m + 1;
            } else {
                h = m - 1;
            }