✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

美团-2026.03.21-算法岗

1. 小基的档案拼接升序册

问题描述

本题是美团 2026.03.21 研发岗第 1 题的原题。

小基 手里有一份长度为 的档案编号序列 。

为了观察长序列下的变化，他把这份序列原封不动地复制到末尾，一共额外拼接了 次。拼接完成后的新序列记为 ，长度为 。并且对于任意满足 的位置，都有：

现在需要你计算：在新序列 中，最长严格递增子序列的长度是多少。

这里的严格递增子序列指：从原序列中按相对顺序选出若干个元素，且后一个元素一定严格大于前一个元素。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 ，表示测试数据组数。

对于每组测试数据：

• 第一行输入一个整数 ，表示原数组长度。
• 第二行输入 个整数 ，表示原数组元素。

输出格式

对于每组测试数据，输出一行一个整数，表示新数组 的最长严格递增子序列长度。

样例输入

2
4
1 1 2 3
5
4 5 3 3 4

样例输出

3
3

样例说明

第一组数据中，可以取出的最长严格递增子序列为 ，因此答案为 。

数据范围

• 
• 
• 
• 单个测试文件内所有 的总和不超过

题解

这题表面上像要在一个超长序列上做 LIS，但真正关键点只有一个：拼接次数极大，远远大于数组里不同数值的个数。

设原数组中一共出现了 个不同的值。

由于子序列要求严格递增，所以同一个值最多只能选一次。因此答案一定不会超过不同值个数 。

接下来说明这个上界一定能取到。

把原数组里所有不同的值从小到大排序，设为：

因为新数组是把原数组重复了很多次，而 ，所以完全可以这样选：

• 在第 份数组中选一个值为 的位置；
• 在第 份数组中选一个值为 的位置；
• ...
• 在第 份数组中选一个值为 的位置。

这些位置一定严格递增，值也严格递增，所以长度为 的严格递增子序列一定存在。

因此答案就是：

做法就非常直接了：每组数据用集合去重，输出集合大小即可。

时间复杂度是 ，空间复杂度是 。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()


def solve() -> None:
    t = int(input())
    out = []
    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))

        # 严格递增子序列中，同一个值最多只能出现一次。
        # 由于复制次数极多，可以把所有不同值按升序分别放到不同副本中去选。
        out.append(str(len(set(arr))))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        unordered_set<int> st;
        st.reserve(n * 2);

        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            // 记录原数组里出现过多少种不同的值。
            st.insert(x);
        }

        // 答案就是不同元素个数。
        cout << st.size() << '\n';
    }
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    private static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

        int t = fs.nextInt();
        while (t-- > 0) {
            int n = fs.nextInt();
            HashSet<Integer> set = new HashSet<>(n * 2);

            for (int i = 0; i < n; ++i) {
                // 统计不同元素个数即可。
                set.add(fs.nextInt());
            }

            out.append(set.size()).append('\n');
        }

        System.out.print(out);
    }
}

2. 单层 GRU 最终隐藏态

问题描述

小基 正在手动复现一个单层 GRU 的前向传播过程。

现在给出：

• 输入序列 ，每一步的维度为 ；
• 初始隐藏状态 ，维度为 ；
• 权重矩阵 Wx、Wh 与偏置 b。

其中：

• Wx 的形状为 ，按列拼接为 ；
• Wh 的形状为 ，按列拼接为 ；
• b 的长度为 ，依次对应 。

GRU 在每个时刻 的计算规则如下：

这里：

• ；
• 表示逐元素乘法。

请你输出最终隐藏状态 。

所有运算都按 float64 处理，最终每个元素按 round(x, 6) 的规则保留到小数点后 位。

输入格式

输入只有一行，是一个合法 JSON 对象，字段如下：

{
  "Wx": [[...], ...],
  "Wh": [[...], ...],
  "b": [...],
  "h0": [...],
  "X": [[...], ...]
}

字段含义：

• Wx：二维数组，形状为 ；
• Wh：二维数组，形状为 ；
• b：一维数组，长度为 ；
• h0：一维数组，长度为 ；
• X：二维数组，形状为 ，按时间顺序给出每一步输入。

输出格式

输出一行一个数组，表示最终隐藏状态：

[hT_1, hT_2, ...]

数组长度为 ，顺序与隐藏维度一致。

样例输入

{"Wx":[[0.5,0,0.5,0,1,0],[0,0.5,0,0.5,0,1]],"Wh":[[0,0,0,0,0,0],[0,0,0,0,0,0]],"b":[0,0,0,0,0,0],"h0":[0,0],"X":[[0,0]]}

样例输出

[0.0, 0.0]

数据范围

• 
• 输入 JSON 合法
• 所有数值都是普通实数，不包含缺失项

题解

这道题没有隐藏优化点，本质就是把单层 GRU 的公式按时间顺序完整模拟一遍。

第一步：先把大矩阵拆成三段

题目给出的 Wx 和 Wh 都是按列拼接在一起的。

如果隐藏维度是 ，那么：

• 前 列是重置门；
• 中间 列是更新门；
• 最后 列是候选隐藏态。

也就是：

偏置 b 也同样按这三段切开。

第二步：按时间顺序递推

设当前隐藏状态是 ，当前输入是 。

先算两个门：

再算候选隐藏态：

最后用更新门把旧状态和候选状态按比例混合：

这样从 一直推到 ，最终得到的就是答案。

为什么直接模拟就够了

题目要求的只是单层 GRU 的前向传播结果：

• 不需要训练；
• 不需要反向传播；
• 不需要更新参数；
• 维度上界也只有 。

因此没有必要做任何额外优化，严格按公式实现就是最稳的做法。

复杂度分析

设输入长度为 ，输入维度为 ，隐藏维度为 。

每一步只做常数次矩阵向量乘法，复杂度为：

在本题的数据范围下，这个复杂度非常轻松。

参考代码

• Python

import json
import math
import sys


def sigmoid(x: float) -> float:
    return 1.0 / (1.0 + math.exp(-x))


def split_matrix(mat, h):
    left = [row[:h] for row in mat]
    mid = [row[h: 2 * h] for row in mat]
    right = [row[2 * h:] for row in mat]
    return left, mid, right


def affine(vec, mat, bias):
    out_dim = len(bias)
    res = bias[:]
    for i, value in enumerate(vec):
        row = mat[i]
        for j in range(out_dim):
            res[j] += value * row[j]
    return res


def fmt_num(x: float) -> str:
    y = round(x, 6)
    s = f"{y:.6f}".rstrip("0").rstrip(".")
    if "." not in s:
        s += ".0"
    if s == "-0.0":
        s = "0.0"
    return s


def solve() -> None:
    data = json.loads(sys.stdin.read())

    wx = data["Wx"]
    wh = data["Wh"]
    b = data["b"]
    h_state = data["h0"][:]
    seq = data["X"]

    h = len(h_state)
    br = b[:h]
    bz = b[h: 2 * h]
    bn = b[2 * h:]

    wxr, wxz, wxn = split_matrix(wx, h)
    whr, whz, whn = split_matrix(wh, h)

    zero = [0.0] * h

    for x in seq:
        part_r = affine(x, wxr, br)
        add_r = affine(h_state, whr, zero)
        r = [sigmoid(part_r[i] + add_r[i]) for i in range(h)]

        part_z = affine(x, wxz, bz)
        add_z = affine(h_state, whz, zero)
        z = [sigmoid(part_z[i] + add_z[i]) for i in range(h)]

        gated = [r[i] * h_state[i] for i in range(h)]
        part_n = affine(x, wxn, bn)
        add_n = affine(gated, whn, zero)
        cand = [math.tanh(part_n[i] + add_n[i]) for i in range(h)]

        h_state = [(1.0 - z[i]) * cand[i] + z[i] * h_state[i] for i in range(h)]

    sys.stdout.write("[" + ", ".join(fmt_num(v) for v in h_state) + "]")


if __name__ == "__main__":
    solve()

• Cpp

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

static vector<double> parse_1d_array(const string& s) {
    vector<double> res;
    string num;
    int depth = 0;
    for (char c : s) {
        if (c == '[') {
            ++depth;
        } else if (c == ']') {
            if (!num.empty()) {
                res.push_back(stod(num));
                num.clear();
            }
            --depth;
        } else if (depth >= 1) {
            if ((c >= '0' && c <= '9') || c == '-' || c == '+' || c == '.' || c == 'e' || c == 'E') {
                num.push_back(c);
            } else if (!num.empty()) {
                res.push_back(stod(num));
                num.clear();
            }
        }
    }
    return res;
}

static vector<vector<double>> parse_2d_array(const string& s) {
    vector<vector<double>> res;
    vector<double> row;
    string num;
    int depth = 0;
    for (char c : s) {
        if (c == '[') {
            ++depth;
            if (depth == 2) {
                row.clear();
            }
        } else if (c == ']') {
            if (!num.empty()) {
                row.push_back(stod(num));
                num.clear();
            }
            if (depth == 2) {
                res.push_back(row);
            }
            --depth;
        } else if (depth >= 2) {
            if ((c >= '0' && c <= '9') || c == '-' || c == '+' || c == '.' || c == 'e' || c == 'E') {
                num.push_back(c);
            } else if (!num.empty()) {
                row.push_back(stod(num));
                num.clear();
            }
        }
    }
    return res;
}

static string extract_array_after_key(const string& src, const string& key) {
    size_t pos = src.find("\"" + key + "\"");
    if (pos == string::npos) {
        return "";
    }
    pos = src.find('[', pos);
    int depth = 0;
    for (size_t i = pos; i < src.size(); ++i) {
        if (src[i] == '[') {
            ++depth;
        } else if (src[i] == ']') {
            --depth;
            if (depth == 0) {
                return src.substr(pos, i - pos + 1);
            }
        }
    }
    return "";
}

static double sigmoid(double x) {
    return 1.0 / (1.0 + exp(-x));
}

static vector<double> affine(const vector<double>& vec, const vector<vector<double>>& mat, const vector<double>& bias) {
    int out_dim = (int)bias.size();
    vector<double> res = bias;
    for (int i = 0; i < (int)vec.size(); ++i) {
        for (int j = 0; j < out_dim; ++j) {
            res[j] += vec[i] * mat[i][j];
        }
    }
    return res;
}

static string fmt_num(double x) {
    double y = round(x * 1e6) / 1e6;
    if (fabs(y) < 5e-13) {
        y = 0.0;
    }
    ostringstream oss;
    oss << fixed << setprecision(6) << y;
    string s = oss.str();
    while (!s.empty() && s.back() == '0') {
        s.pop_back();
    }
    if (!s.empty() && s.back() == '.') {
        s.push_back('0');
    }
    return s;
}

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

    string input((istreambuf_iterator<char>(cin)), istreambuf_iterator<char>());

    auto wx = parse_2d_array(extract_array_after_key(input, "Wx"));
    auto wh = parse_2d_array(extract_array_after_key(input, "Wh"));
    auto b = parse_1d_array(extract_array_after_key(input, "b"));
    auto h_state = parse_1d_array(extract_array_after_key(input, "h0"));
    auto seq = parse_2d_array(extract_array_after_key(input, "X"));

    int h = (int)h_state.size();

    vector<double> br(b.begin(), b.begin() + h);
    vector<double> bz(b.begin() + h, b.begin() + 2 * h);
    vector<double> bn(b.begin() + 2 * h, b.end());

    vector<vector<double>> wxr(wx.size(), vector<double>(h));
    vector<vector<double>> wxz(wx.size(), vector<double>(h));
    vector<vector<double>> wxn(wx.size(), vector<double>(h));
    vector<vector<double>> whr(wh.size(), vector<double>(h));
    vector<vector<double>> whz(wh.size(), vector<double>(h));
    vector<vector<double>> whn(wh.size(), vector<double>(h));

    for (int i = 0; i < (int)wx.size(); ++i) {
        for (int j = 0; j < h; ++j) {
            wxr[i][j] = wx[i][j];
            wxz[i][j] = wx[i][j + h];
            wxn[i][j] = wx[i][j + 2 * h];
        }
    }
    for (int i = 0; i < (int)wh.size(); ++i) {
        for (int j = 0; j < h; ++j) {
            whr[i][j] = wh[i][j];
            whz[i][j] = wh[i][j + h];
            whn[i][j] = wh[i][j + 2 * h];
        }
    }

    vector<double> zero(h, 0.0);

    for (const auto& x : seq) {
        auto part_r = affine(x, wxr, br);
        auto add_r = affine(h_state, whr, zero);
        vector<double> r(h);
        for (int i = 0; i < h; ++i) {
            r[i] = sigmoid(part_r[i] + add_r[i]);
        }

        auto part_z = affine(x, wxz, bz);
        auto add_z = affine(h_state, whz, zero);
        vector<double> z(h);
        for (int i = 0; i < h; ++i) {
            z[i] = sigmoid(part_z[i] + add_z[i]);
        }

        vector<double> gated(h);
        for (int i = 0; i < h; ++i) {
            gated[i] = r[i] * h_state[i];
        }
        auto part_n = affine(x, wxn, bn);
        auto add_n = affine(gated, whn, zero);
        vector<double> cand(h);
        for (int i = 0; i < h; ++i) {
            cand[i] = tanh(part_n[i] + add_n[i]);
        }

        vector<double> next_state(h);
        for (int i = 0; i < h; ++i) {
            next_state[i] = (1.0 - z[i]) * cand[i] + z[i] * h_state[i];
        }
        h_state.swap(next_state);
    }

    cout << "[";
    for (int i = 0; i < h; ++i) {
        if (i) {
            cout << ", ";
        }
        cout << fmt_num(h_state[i]);
    }
    cout << "]";
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    static String text;
    static int ptr;

    static String extractArrayAfterKey(String src, String key) {
        int pos = src.indexOf("\"" + key + "\"");
        if (pos < 0) {
            return "";
        }
        pos = src.indexOf('[', pos);
        int depth = 0;
        for (int i = pos; i < src.length(); i++) {
            char c = src.charAt(i);
            if (c == '[') {
                depth++;
            } else if (c == ']') {
                depth--;
                if (depth == 0) {
                    return src.substring(pos, i + 1);
                }
            }
        }
        return "";
    }

    static List<Double> parse1D(String s) {
        ArrayList<Double> res = new ArrayList<>();
        StringBuilder num = new StringBuilder();
        int depth = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '[') {
                depth++;
            } else if (c == ']') {
                if (num.length() > 0) {
                    res.add(Double.parseDouble(num.toString()));
                    num.setLength(0);
                }
                depth--;
            } else if (depth >= 1) {
                if (Character.isDigit(c) || c == '-' || c == '+' || c == '.' || c == 'e' || c == 'E') {
                    num.append(c);
                } else if (num.length() > 0) {
                    res.add(Double.parseDouble(num.toString()));
                    num.setLength(0);
                }
            }
        }
        return res;
    }

    static List<List<Double>> parse2D(String s) {
        ArrayList<List<Double>> res = new ArrayList<>();
        ArrayList<Double> row = new ArrayList<>();
        StringBuilder num = new StringBuilder();
        int depth = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '[') {
                depth++;
                if (depth == 2) {
                    row = new ArrayList<>();
                }
            } else if (c == ']') {
                if (num.length() > 0) {
                    row.add(Double.parseDouble(num.toString()));
                    num.setLength(0);
                }
                if (depth == 2) {
                    res.add(row);
                }
                depth--;
            } else if (depth >= 2) {
                if (Character.isDigit(c) || c == '-' || c == '+' || c == '.' || c == 'e' || c == 'E') {
                    num.append(c);
                } else if (num.length() > 0) {
                    row.add(Double.parseDouble(num.toString()));
                    num.setLength(0);
                }
            }
        }
        return res;
    }

    static double sigmoid(double x) {
        return 1.0 / (1.0 + Math.exp(-x));
    }

    static double[] affine(double[] vec, double[][] mat, double[] bias) {
        int outDim = bias.length;
        double[] res = Arrays.copyOf(bias, outDim);
        for (int i = 0; i < vec.length; i++) {
            for (int j = 0; j < outDim; j++) {
                res[j] += vec[i] * mat[i][j];
            }
        }
        return res;
    }

    static String fmtNum(double x) {
        double y = Math.round(x * 1_000_000.0) / 1_000_000.0;
        if (Math.abs(y) < 5e-13) {
            y = 0.0;
        }
        String s = String.format(Locale.US, "%.6f", y);
        int p = s.length() - 1;
        while (p >= 0 && s.charAt(p) == '0') {
            p--;
        }
        if (s.charAt(p) == '.') {
            p++;
        }
        s = s.substring(0, p + 1);
        if (!s.contains(".")) {
            s += ".0";
        }
        if (s.equals("-0.0")) {
            s = "0.0";
        }
        return s;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null) {
            sb.append(line);
        }
        String input = sb.toString();

        List<List<Double>> wxList = parse2D(extractArrayAfterKey(input, "Wx"));
        List<List<Double>> whList = parse2D(extractArrayAfterKey(input, "Wh"));
        List<Double> bList = parse1D(extractArrayAfterKey(input, "b"));
        List<Double> h0List = parse1D(extractArrayAfterKey(input, "h0"));
        List<List<Double>> xList = parse2D(extractArrayAfterKey(input, "X"));

        int d = wxList.size();
        int h = h0List.size();

        double[][] wxr = new double[d][h];
        double[][] wxz = new double[d][h];
        double[][] wxn = new double[d][h];
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < h; j++) {
                wxr[i][j] = wxList.get(i).get(j);
                wxz[i][j] = wxList.get(i).get(j + h);
                wxn[i][j] = wxList.get(i).get(j + 2 * h);
            }
        }

        double[][] whr = new double[h][h];
        double[][] whz = new double[h][h];
        double[][] whn = new double[h][h];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < h; j++) {
                whr[i][j] = whList.get(i).get(j);
                whz[i][j] = whList.get(i).get(j + h);
                whn[i][j] = whList.get(i).get(j + 2 * h);
            }
        }

        double[] biasR = new double[h];
        double[] biasZ = new double[h];
        double[] biasN = new double[h];
        for (int i = 0; i < h; i++) {
            biasR[i] = bList.get(i);
            biasZ[i] = bList.get(i + h);
            biasN[i] = bList.get(i + 2 * h);
        }

        double[] state = new double[h];
        for (int i = 0; i < h; i++) {
            state[i] = h0List.get(i);
        }
        double[] zero = new double[h];

        for (List<Double> row : xList) {
            double[] x = new double[row.size()];
            for (int i = 0; i < row.size(); i++) {
                x[i] = row.get(i);
            }

            double[] partR = affine(x, wxr, biasR);
            double[] addR = affine(state, whr, zero);
            double[] r = new double[h];
            for (int i = 0; i < h; i++) {
                r[i] = sigmoid(partR[i] + addR[i]);
            }

            double[] partZ = affine(x, wxz, biasZ);
            double[] addZ = affine(state, whz, zero);
            double[] z = new double[h];
            for (int i = 0; i < h; i++) {
                z[i] = sigmoid(partZ[i] + addZ[i]);
            }

            double[] gated = new double[h];
            for (int i = 0; i < h; i++) {
                gated[i] = r[i] * state[i];
            }

            double[] partN = affine(x, wxn, biasN);
            double[] addN = affine(gated, whn, zero);
            double[] cand = new do