要参加小红书笔试了？来看看去年的小红书秋招题目长啥样吧

✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：山峰探险

1️⃣：定义特定条件的"山峰数组"，要求有一个最高点，两侧严格递减

2️⃣：通过预处理每个位置的左侧递增长度和右侧递减长度

3️⃣：遍历数组找出最长满足条件的子数组

难度：中等

这道题目要求在数组中找出特定模式的子数组。通过预处理技巧，我们可以在O(n)的时间内解决问题，避免了暴力枚举所有子数组的高复杂度。关键在于理解"山峰数组"的定义，并巧妙利用两次遍历来记录关键信息。

题目二：小兰的美观排列

1️⃣：理解"不美观程度"的定义：相邻两本书类别不同的情况数

2️⃣：使用动态规划计算最优解，状态转移考虑固定书和可移动书

3️⃣：通过记忆化搜索优化状态空间，降低计算复杂度

难度：中等

这道题目结合了组合优化和动态规划思想，需要找出一种排列方式使"不美观程度"最小。通过巧妙设计状态表示和转移方程，我们可以在O(n²)的时间复杂度内解决问题，有效处理题目给定的数据范围。

题目三：小兰的彩色树木园

1️⃣：在树结构中寻找最优切割点（红色节点）

2️⃣：通过深度优先搜索计算每个子树中黑色节点的数量

3️⃣：对每个红色节点评估切割后黑色节点的最大连通分量

难度：中等偏难

这道题目是典型的树形DP问题，需要理解树的连通性和切割操作对结构的影响。通过一次DFS遍历，我们可以获取解决问题所需的所有信息，并在O(n)的时间复杂度内找到最优解，展现了图算法在实际问题中的应用。

01. 山峰探险

问题描述

K 小姐是一位热爱探险的旅行者，她对山峰情有独钟。最近，她在一片神秘的山脉中发现了一些连续的山峰。为了研究这些山峰的形状，她决定将山峰的高度记录下来，并寻找其中最长的"山峰数组"。

一个"山峰数组"定义为：在某个位置存在一个最高点，且该位置左右两边的高度依次严格递减。用数学语言描述，即存在 使得 且 。例如， 和 是"山峰数组"，而 , , 和 不是。

K 小姐想知道，在她记录的所有子数组中，最长的"山峰数组"的长度是多少。

输入格式

第一行输入一个整数 ，表示数组的长度 。

第二行输入 个整数 ，表示数组的值 。

输出格式

输出一个整数，表示最长的"山峰数组"的长度。

样例输入

6
1 1 4 5 1 4

样例输出

4

样例	解释说明
样例1	最长的"山峰数组"是 ，长度为 4。这个子数组中 5 是最高点，左边的高度依次上升，右边的高度依次下降。

数据范围

• 数组长度 满足 。
• 数组元素 满足 。

题解

这道题目要求我们找出给定数组中，满足"山峰数组"定义的最长子数组长度。

首先，我们需要清楚理解"山峰数组"的定义：它必须有一个最高点，且这个最高点左边的元素严格递增，右边的元素严格递减。

解决这个问题的关键在于，我们可以预处理出每个位置的两个信息：

1. 该位置左侧的严格递增长度
2. 该位置右侧的严格递减长度

我们可以通过两次遍历数组来完成这个预处理：

• 从左到右遍历数组，计算每个位置的左侧严格递增长度
• 从右到左遍历数组，计算每个位置的右侧严格递减长度

然后，对于每个位置 i，如果它左侧有递增序列且右侧有递减序列，那么以 i 为最高点的"山峰数组"长度就是：左侧长度 + 右侧长度 + 1（当前位置本身）。

我们只需要找出所有可能的"山峰数组"中长度最大的那个。

时间复杂度分析：

• 两次遍历预处理数组：O(n)
• 一次遍历计算最大长度：O(n)
• 总时间复杂度：O(n)，其中 n 是数组的长度

这个复杂度对于题目给定的数据范围（n ≤ 10^5）是完全可以接受的。

参考代码

• Python

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

def solve():
    n = int(input())
    nums = list(map(int, input().split()))
    
    # 预处理左侧严格递增长度
    left = [0] * n
    for i in range(1, n):
        if nums[i] > nums[i-1]:
            left[i] = left[i-1] + 1
    
    # 预处理右侧严格递减长度
    right = [0] * n
    for i in range(n-2, -1, -1):
        if nums[i] > nums[i+1]:
            right[i] = right[i+1] + 1
    
    # 计算最大山峰长度
    ans = 0
    for i in range(n):
        if left[i] > 0 and right[i] > 0:
            ans = max(ans, left[i] + right[i] + 1)
    
    return ans

print(solve())

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 计算左侧递增序列长度
    vector<int> left(n);
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i-1]) {
            left[i] = left[i-1] + 1;
        }
    }
    
    // 计算右侧递减序列长度
    vector<int> right(n);
    for (int i = n-2; i >= 0; i--) {
        if (a[i] > a[i+1]) {
            right[i] = right[i+1] + 1;
        }
    }
    
    // 计算最长山峰数组
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (left[i] > 0 && right[i] > 0) {
            res = max(res, left[i] + right[i] + 1);
        }
    }
    
    cout << res << endl;
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        // 计算左侧递增序列
        int[] left = new int[n];
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) {
                left[i] = left[i-1] + 1;
            }
        }
        
        // 计算右侧递减序列
        int[] right = new int[n];
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] > nums[i+1]) {
                right[i] = right[i+1] + 1;
            }
        }
        
        // 寻找最长山峰数组
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            if (left[i] > 0 && right[i] > 0) {
                maxLen = Math.max(maxLen, left[i] + right[i] + 1);
            }
        }
        
        System.out.println(maxLen);
        sc.close();
    }
}

02. 小兰的美观排列

问题描述

小兰最近在整理她的书架，她希望将书架上的书分为两类，并且将它们排成一排。为了让书架看起来更美观，她希望相邻的书尽量属于同一类别。每当相邻的两本书属于不同的类别时，小兰就会觉得不美观。

书架上的一些书已经固定不能移动，而其他书可以自由移动。小兰想知道，如何移动这些可以移动的书籍，使得不美观程度最小。

输入格式

第一行输入一个整数 ，表示书的数量。

第二行输入 个整数 ，表示书的类别。其中 表示书是第一类， 表示书是第二类。

第三行输入 个整数 ，表示书是否可以移动。其中 表示第 本书可以移动， 表示第 本书不可以移动。

输出格式

输出一个正整数，表示不美观程度的最小值。

样例输入

5
1 2 1 2 1
0 1 1 0 1

样例输出

1

样例	解释说明
样例1	初始时第2、3、5本书可以移动。可以将第2本书改为类别1，第3本书改为类别2。经过调整后，书架变为[1,1,2,2,1]，只有第4本书和第5本书之间不美观，所以不美观程度为1。

数据范围

• 
• 
• 

题解

这道题目可以使用动态规划来解决。首先，我们需要明确什么是"不美观程度"——即相邻两本书类别不同的情况数量。

我们定义状态 dp[i][j][k] 表示：处理到第 i 本书时，还剩余 j 本第一类可移动的书，当前这本书的类别为 k（0表示第一类，1表示第二类）时的最小不美观程度。

状态转移思路如下：

1. 如果当前书不可移动（b[i] = 0），我们只能保持它的原始类别，计算与前一本书的不美观程度（如果存在）。
2. 如果当前书可以移动（b[i] = 1），我们有两种选择：
   • 放置第一类书
   • 放置第二类书（如果还有剩余的第一类可移动书）
3. 我们选择这两种情况中不美观程度较小的一种。

动态规划的边界条件是：当处理完所有书时（i = n），如果没有剩余的可移动书（j = 0），则返回0；否则返回一个很大的值（表示非法状态）。

这个问题的关键在于理解可移动书籍的分配：最初，我们统计可移动的第一类书的数量 t，然后在动态规划过程中，每当我们选择将一本可移动的书放置为第二类时，就减少一本可移动的第一类书。

时间复杂度分析：

• 状态数量：O(n²)，因为我们有 n 本书，每本书有至多 n 种剩余第一类可移动书的状态，以及2种当前书的类别。
• 每个状态的转移时间：O(1)
• 因此，总时间复杂度为 O(n²)，对于题目给定的 n ≤ 100，这个复杂度是可以接受的。

参考代码

• Python

import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().strip()

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    # 将类别转换为0和1
    for i in range(n):
        a[i] -= 1
    
    # 统计可移动的第二类书的数量
    count = 0
    for i in range(n):
        if b[i] == 1 and a[i] == 1:
            count += 1
    
    # dp数组初始化为None表示未计算
    dp = [[[None for _ in range(2)] for _ in range(count+1)] for _ in range(n+1)]
    
    def dfs(pos, rem, prev):
        # 处理完所有书
        if pos == n:
            return 0 if rem == 0 else 10**9  # 用大数代替inf
        
        if dp[pos][rem][prev] is not None:
            return dp[pos][rem][prev]
        
        # 计算惩罚：如果不是第一本书，且当前类别与前一本不同，惩罚1，否则0
        # 当前书类别暂时未知，先尝试不同放法
        res = 10**9
        
        if b[pos] == 1:
            # 放第一类书
            pen = 0 if pos == 0 else (1 if prev != 0 else 0)
            res = min(res, dfs(pos+1, rem, 0) + pen)
            
            # 放第二类书（前提是还有剩余rem）
            if rem >