💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍥 本次的难度相对美团字节来说不大，总共有两套卷，其中前两题是一样的，顺序不一定相同，不同的卷最后一题有不同

1️⃣ 经典山峰题，前后缀预处理

2️⃣ 有些卷子这题是第一题，容易给人误导认为贪心可以做，但其实贪心很难拿满，dp比较容易点，而且这题数据范围可以拓展到

3️⃣ 比较经典的DP，类似于0/1背包的思维，难度不大

⛰ 01.山峰探险

问题描述

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

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

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

输入格式

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

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

输出格式

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

样例输入

6
1 1 4 5 1 4

样例输出

4

数据范围

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

题解

预处理

“山峰数组”要求在某个位置存在一个最高点，且该位置左右两边的高度依次严格递减。

思路：我们可以通过两次遍历数组来记录每个位置的上升和下降序列的长度。

• 从左到右遍历数组，记录每个位置的上升序列长度。

• 从右到左遍历数组，记录每个位置的下降序列长度。

• 检查每个位置是否可以作为山峰的顶点，并计算可能的山峰数组长度。

• Python

def longest_peak(arr):
    n = len(arr)
    if n < 3:
        return 0
    
    l = [0] * n
    r = [0] * n
    

    for i in range(1, n):
        if arr[i] > arr[i - 1]:
            l[i] = l[i - 1] + 1

    for i in range(n - 2, -1, -1):
        if arr[i] > arr[i + 1]:
            r[i] = r[i + 1] + 1
    
    max_length = 0
    for i in range(1, n - 1):
        if l[i] > 0 and r[i] > 0:
            max_length = max(max_length, l[i] + r[i] + 1)
    
    return max_length

n = int(input())
arr = list(map(int, input().split()))
print(longest_peak(arr))

• Java

import java.util.Scanner;

public class LongestPeak {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        
        System.out.println(findLongestPeak(arr));
    }
    
    private static int findLongestPeak(int[] arr) {
        int n = arr.length;
        if (n < 3) return 0;
        
        int[] l = new int[n];
        int[] r = new int[n];
        
      
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                l[i] = l[i - 1] + 1;
            }
        }
        

        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                r[i] = r[i + 1] + 1;
            }
        }
        
        int maxLength = 0;
        for (int i = 1; i < n - 1; i++) {
            if (l[i] > 0 && r[i] > 0) {
                maxLength = Math.max(maxLength, l[i] + r[i] + 1);
            }
        }
        
        return maxLength;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestPeak(const vector<int>& arr) {
    int n = arr.size();
    if (n < 3) return 0;
    
    vector<int> l(n, 0), r(n, 0);
    

    for (int i = 1; i < n; ++i) {
        if (arr[i] > arr[i - 1]) {
            l[i] = l[i - 1] + 1;
        }
    }
    

    for (int i = n - 2; i >= 0; --i) {
        if (arr[i] > arr[i + 1]) {
            r[i] = r[i + 1] + 1;
        }
    }
    
    int maxLength = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (l[i] > 0 && r[i] > 0) {
            maxLength = max(maxLength, l[i] + r[i] + 1);
        }
    }
    
    return maxLength;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    cout << longestPeak(arr) << endl;
    return 0;
}

🎲 02.K小姐的美观排列

问题描述

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

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

输入格式

第一行输入一个整数 ，表示书的数量。
第二行输入 个整数 ，表示书的类别。其中 表示书是第一类， 表示书是第二类。
第三行输入 个整数 ，表示书是否可以移动。其中 表示第 本书可以移动， 表示第 本书不可以移动。

输出格式

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

样例输入

5
1 2 1 2 1
0 1 1 0 1

样例输出

1

数据范围

题解

这道题目可以使用动态规划来解决。我们定义状态 dp[i][l][r][k] 表示处理到第 i 本书时，还剩 l 本第一类可移动的书，r 本第二类可移动的书，当前这本书的类别为 （0表示第一类，1表示第二类）时的最小不美观程度。状态转移的思路如下：

1. 如果当前书不可移动，我们只能保持它的原始类别，计算与前一本书的不美观程度（如果存在的话）。
2. 如果当前书可以移动，我们有两种选择：放置第一类书（如果还有剩余的第一类可移动书）放置第二类书（如果还有剩余的第二类可移动书）
3. 我们选择这两种情况中不美观程度较小的一种。
4. 边界条件：当处理完所有书时，返回 0

时间复杂度：，其中 n 是书的数量。 空间复杂度：。

这题其实有技巧能够优化成

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

其他转移和第一种类似。

我们考虑最终结果

边界条件：当处理完所有书时，返回 ，否则返回不合法。

时间复杂度：，其中 n 是书的数量。 空间复杂度：。

参考代码

• Python

# 定义最大书籍数量
N = 101

# 初始化 dp 数组，存储每个状态的最小“不美观”程度
dp = [[[-1 for _ in range(2)] for _ in range(N)] for _ in range(N)]

def dfs(u, l, k):
    # 如果已经处理完所有书籍
    if u == n:
        return 0 if l == 0 else 2 * n + 1

    # 如果当前状态已经计算过，直接返回结果
    if dp[u][l][k] != -1:
        return dp[u][l][k]

    v = 1 if u > 0 else 0  # 检查前一本书是否存在
    res = 2 * n + 1  # 初始化最小“不美观”程度为一个很大的值

    # 如果当前书可以移动
    if b[u]:
        # 尝试将当前书放置为第一类
        res = dfs(u + 1, l, 0) +