京东笔试京东笔试题 0809

笔试时间：2025年8月9日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：子序列的字典序

现在有一个长度为 n 的数字序列，每个数都在 1~k 的范围内，且 1~k 内每个数字都至少出现过一次。现在我们想在这其中找一个子序列，使得 1~k 恰好出现一次，且字典序最小。请你通过程序得出结果。我们认为：B 是 A 的子序列，当且仅当可以从 A 中删除 0 个或任意个元素之后按照原来的顺序拼接起来得到 B。序列 A 的字典序小于 B，当且仅当存在一个位置 k，使得 A[k] < B[k] 且 A[i] = B[i]（i = 1..k-1）。

输入描述

第一行两个空格隔开的正整数 n 和 k；

第二行 n 个空格隔开的正整数，表示该数字序列 a。

约束：1 ≤ k ≤ n ≤ 5×10⁴，1 ≤ aᵢ ≤ k

输出描述

输出一行 k 个数字，表示字典序最小的子序列。不要输出行末空格。

样例输入

5 3

2 1 3 3 2

样例输出

1 3 2

提示：其中一种可行的方案为：2（1）3（3）2，选定括号中的数字，构成子序列，可知此时字典序最小。

参考题解

本题使用贪心+单调栈的的思路，问题本质分析：需要从原数组中选出长度为 k 的子序列（保持原顺序），且该子序列的字典序最小。字典序最小的核心是「前面的元素尽可能小」，这天然指向「贪心策略」—— 每一步都选择当前能选的最小元素。贪心的约束：选择小元素时不能 “只顾眼前”，必须保证后面还有足够的元素来凑齐 k 个。例如，若当前栈顶元素较大，但后面再也没有该元素了，就不能弹出它（否则凑不够 k 个）。因此需要统计每个元素剩余的出现次数，作为能否弹出栈顶的依据。单调栈的适配性：要维护 “前面元素尽可能小” 的序列，单调栈是天然的工具。栈可以动态维护已选元素，通过弹出 “较大且后续仍有出现” 的栈顶元素，确保新加入的元素能让序列更优（字典序更小）。同时栈的长度可以直观地控制在 k 以内，满足子序列长度要求。去重需求：若问题隐含 “子序列元素不重复”（从代码中 inStack 的判断可推测），则需要额外记录元素是否已在栈中，避免重复加入破坏唯一性。因此，贪心策略保证了 “选最小” 的核心目标，单调栈提供了动态维护序列的高效方式，剩余次数统计解决了 “凑够 k 个” 的约束

C++：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> smallestSubsequence(vector<int>& a, int k) {
    int n = a.size();
    // 统计每个数字剩余出现的次数
    unordered_map<int, int> count;
    for (int num : a) {
        count[num]++;
    }

    vector<int> stack;
    // 记录栈中是否已经包含某个数字
    unordered_map<int, bool> inStack;

    for (int num : a) {
        // 每遍历一个数字，该数字剩余出现次数减 1
        count[num]--;

        // 如果数字已经在栈中，跳过
        if (inStack[num]) continue;

        // 维护单调栈的字典序最小性质
        while (!stack.empty() && stack.back() > num && count[stack.back()] > 0) {
            inStack[stack.back()] = false;
            stack.pop_back();
        }

        stack.push_back(num);
        inStack[num] = true;

        // 当栈的大小达到 k 时，提前终止（已经找到结果）
        if (stack.size() == k) break;
    }

    return stack;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> result = smallestSubsequence(a, k);

    for (int i = 0; i < k; i++) {
        cout << result[i];
        if (i != k - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

Java：

import java.util.*;

public class SmallestSubsequence {
    public static List<Integer> smallestSubsequence(int[] a, int k) {
        int n = a.length;
        // 统计每个数字剩余出现的次数
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : a) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        Deque<Integer> stack = new ArrayDeque<>();
        // 记录栈中是否已经包含某个数字
        Map<Integer, Boolean> inStack = new HashMap<>();

        for (int num : a) {
            // 每遍历一个数字，该数字剩余出现次数减 1
            count.put(num, count.get(num) - 1);

            // 如果数字已经在栈中，跳过
            if (inStack.getOrDefault(num, false)) {
                continue;
            }

            // 维护单调栈的字典序最小性质
            while (!stack.isEmpty() && stack.peekLast() > num && count.get(stack.peekLast()) > 0) {
                inStack.put(stack.peekLast(), false);
                stack.pollLast();
            }

            stack.offerLast(num);
            inStack.put(num, true);

            // 当栈的大小达到 k 时，提前终止（已经找到结果）
            if (stack.size() == k) {
                break;
            }
        }

        return new ArrayList<>(stack);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        List<Integer> result = smallestSubsequence(a, k);

        for (int i = 0; i < k; i++) {
            System.out.print(result.get(i));
            if (i != k - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }
}

Python：

from collections import defaultdict

def smallest_subsequence(a, k):
    n = len(a)
    # 统计每个数字剩余出现的次数
    count = defaultdict(int)
    for num in a:
        count[num] += 1

    stack = []
    # 记录栈中是否已经包含某个数字
    in_stack = defaultdict(bool)

    for num in a:
        # 每遍历一个数字，该数字剩余出现次数减 1
        count[num] -= 1

        # 如果数字已经在栈中，跳过
        if in_stack[num]:
            continue

        # 维护单调栈的字典序最小性质
        while stack and stack[-1] > num and count[stack[-1]] > 0:
            in_stack[stack[-1]] = False
            stack.pop()

        stack.append(num)
        in_stack[num] = True

        # 当栈的大小达到 k 时，提前终止（已经找到结果）
        if len(stack) == k:
            break

    return stack

if __name__ == "__main__":
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    k = int(input[idx])
    idx += 1
    a = []
    for i in range(n):
        a.append(int(input[idx]))
        idx += 1

    result = smallest_subsequence(a, k)

    for i in range(k):
        print(result[i], end="")
        if i != k - 1:
            print(" ", end="")
    print()

第二题：01串划分

小钟有一个长度为 n 的 01 串 s（仅由字符 0 和 1 组成），另外还有 m 个数字，分别用 a₁, a₂, ..., aₘ 表示。小钟想知道，能否选择 m 个不相交的区间 [l₁, r₁], [l₂, r₂], ..., [lₘ, rₘ]，使得对于任意的 aᵢ，其二进制表示（没有前导 0，0 的二进制表示就是 0 ），都能用 s 的某个连续子串 s[lⱼ, lⱼ + 1, ..., rⱼ] 来表示。