🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 秋招笔试题

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

本次的题目比较典，但如果是第一次做该类型的题还是有点困难的

1️⃣ 是一道比较简单的栈模拟

2️⃣ 看到LCA被吓了一跳，心想笔试还要考这个？仔细一看是完全二叉树，那没事了

3️⃣ LC原题，比较典的树形DP。

4️⃣ 判断4个数是否能凑出 24 点，代码还是比较长的。

⚡️ 01.消除重复字符

问题描述

LYA 是一位热爱编程的高中生。最近，她在参加一个编程比赛时遇到了一个有趣的字符串处理问题。问题要求她编写一个程序，能够消除字符串中连续出现的相同字符，直到没有连续相同的字符为止。如果最终字符串变为空，则输出"null"。LYA 觉得这个问题很有挑战性，你能帮她解决吗？

输入格式

输入为一行，包含一个字符串 ，字符串长度不超过 。

输出格式

输出一行，为处理后的字符串。如果结果为空字符串，则输出"null"（不包含引号）。

样例输入

accb

样例输出

ab

数据范围

对于 100% 的数据，，字符串中只包含小写字母。

题解

这道题目可以使用栈的思想来解决。我们可以遍历字符串，并维护一个结果栈。

对于每个字符，我们有以下处理方式：

1. 如果栈为空，直接将当前字符入栈。
2. 如果栈不为空，比较当前字符与栈顶字符：
   • 如果不相同，将当前字符入栈。
   • 如果相同，将栈顶元素弹出，并继续向后遍历，直到遇到不同的字符或到达字符串末尾。

这样，我们就可以在一次遍历中完成所有的消除操作。最后，如果栈为空，输出"null"；否则，将栈中的字符连接成字符串输出。

时间复杂度：，其中 是字符串的长度。 空间复杂度：，用于存储结果栈。

参考代码

• Python

# 读取输入字符串
s = input()

# 初始化结果列表
res = []

# 遍历字符串
i = 0
while i < len(s):
    # 当结果列表为空或当前字符与栈顶不同时，将字符加入结果
    if not res or s[i] != res[-1]:
        res.append(s[i])
        i += 1
    else:
        # 当遇到相同字符时，移除栈顶元素并跳过相同的字符
        res.pop()
        while i < len(s) and s[i] == res[-1]:
            i += 1

# 输出结果
print('null' if not res else ''.join(res))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        
        // 使用 StringBuilder 作为栈
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            // 如果结果为空或当前字符与栈顶不同，则添加字符
            if (result.length() == 0 || c != result.charAt(result.length() - 1)) {
                result.append(c);
            } else {
                // 移除栈顶字符并跳过相同的字符
                result.deleteCharAt(result.length() - 1);
                while (i + 1 < s.length() && s.charAt(i + 1) == c) {
                    i++;
                }
            }
        }
        
        // 输出结果
        System.out.println(result.length() == 0 ? "null" : result.toString());
    }
}

• Cpp

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

int main() {
    string s;
    cin >> s;
    
    string result;
    
    for (int i = 0; i < s.length(); i++) {
        // 如果结果为空或当前字符与栈顶不同，则添加字符
        if (result.empty() || s[i] != result.back()) {
            result.push_back(s[i]);
        } else {
            // 移除栈顶字符并跳过相同的字符
            result.pop_back();
            while (i + 1 < s.length() && s[i + 1] == s[i]) {
                i++;
            }
        }
    }
    
    // 输出结果
    cout << (result.empty() ? "null" : result) << endl;
    
    return 0;
}

🍉 02.寻找最近共同导师

问题描述

在一个名为"星际学院"的虚拟世界中，每个学员可以拥有多个学生，但每个学生只能有一个导师。LYA 是这个学院的管理员，她发现学院的组织结构恰好形成了一个完全二叉树。现在，她需要开发一个程序来帮助学员们找到他们的最近共同导师。

在这个虚拟世界中，学员们使用独特的昵称相互识别。LYA 需要你的帮助来实现这个功能：给定所有学员的昵称（按层次遍历顺序）和若干指定学员，找出这些学员的最近共同导师。

输入格式

第一行包含一个正整数 ，表示学员的总数。

第二行包含 个由空格分隔的字符串，表示按层次遍历顺序给出的所有学员的昵称。

第三行包含一个正整数 （），表示需要查找最近共同导师的学员数量。

第四行包含 个由空格分隔的字符串，表示这 个学员的昵称。

输出格式

输出一行，包含一个字符串，表示这些学员的最近共同导师的昵称。

样例输入

15
Alpha Beta Gamma Delta Epsilon Zeta Eta Theta Iota Kappa Lambda Mu Nu Xi Omicron
2
Theta Beta

样例输出

Beta

数据范围

对于 100% 的数据，保证：

• （）
• 
• 所有昵称由大小写英文字母组成，且互不相同
• 指定的学员昵称一定在所有学员昵称中

题解

这道题目本质上是在完全二叉树中寻找最近公共祖先（LCA）的问题。由于输入是按层次遍历顺序给出的，我们可以利用完全二叉树的性质来解决这个问题。

解题思路如下：

1. 首先，我们需要找到每个指定学员在树中的索引位置。
2. 对于每个学员，我们可以通过不断除以 2 来找到其所有祖先的索引。
3. 比较所有学员的祖先路径，找到最深的公共祖先即为答案。

具体实现时，我们可以：

1. 使用一个函数来获取学员从根节点到自身的路径。
2. 对所有指定学员的路径进行比较，找到最后一个相同的节点。

时间复杂度：，其中 是指定学员的数量， 是总学员数。 空间复杂度：，用于存储学员的路径。

参考代码

• Python

def find_lca(tree, players):
    # 获取学员从根到自身的路径
    def get_path(player):
        path = []
        index = tree.index(player)
        while index > 0:
            path.append(index)
            index = (index - 1) // 2
        path.append(0)
        return path[::-1]
    
    # 获取所有指定学员的路径
    paths = [get_path(player) for player in players]
    lca_index = 0
    # 比较所有路径，找到最后一个相同的节点
    for level in zip(*paths):
        if len(set(level)) == 1:
            lca_index = level[0]
        else:
            break
    return tree[lca_index]

# 输入处理
n = int(input())
tree = input().split()
x = int(input())
players = input().split()

# 找到最近公共导师并输出
result = find_lca(tree, players)
print(result)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();  // 消耗换行符
        
        String[] tree = scanner.nextLine().split(" ");
        int x = scanner.nextInt();
        scanner.nextLine();  // 消耗换行符
        
        String[] players = scanner.nextLine().split(" ");
        
        String result = findLCA(tree, players);
        System.out.println(result);
    }
    
    // 寻找最近公共导师
    private static String findLCA(String[] tree, String[] players) {
        List<List<Integer>> paths = new ArrayList<>();
        for (String player : players) {
            paths.add(getPath(tree, player));
        }
        
        int lcaIndex = 0;
        for (int i = 0; i < paths.get(0).size(); i++) {
            int current = paths.get(0).get(i);
            boolean allSame = true;
            for (List<Integer> path : paths) {
                if (i >= path.size() || path.get(i) != current) {
                    allSame = false;
                    break;
                }
            }
            if (allSame) {
                lcaIndex = current;
            } else {
                break;
            }
        }
        return tree[lcaIndex];
    }
    
    // 获取学员从根到自身的路径
    private static List<Integer> getPath(String[] tree, String player) {
        List<Integer> path = new ArrayList<>();
        int index = Arrays.asList(tree).indexOf(player);
        while (index > 0) {
            path.add(index);
            index = (index - 1) / 2;
        }
        path.add(0);
        Collections.reverse(path);
        return path;
    }
}

• Cpp

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

// 获取学员从根到自身的路径
vector<int> getPath(const vector<string>& tree, const string& player) {
    vector<int> path;
    int index = find(tree.begin(), tree.end(), player) - tree.begin();
    while (index > 0) {
        path.push_back(index);
        index = (index - 1) / 2;
    }
    path.push_back(0);
    reverse(path.begin(), path.end());
    return path;
}

// 寻找最近公共导师
string findLCA(const vector<string>& tree, const vector<string>& players) {
    vector<vector<int>> paths;
    for (const auto& player : players) {
        paths.push_back(getPath(tree, player));
    }
    
    int lcaIndex = 0;
    for (size_t i = 0; i < paths[0].size(); ++i) {
        int current = paths[0][i];
        bool allSame = true;
        for (const auto& path : paths) {
            if (i >= path.size() || path[i] != current) {
                allSame = false;
                break;
            }
        }
        if (allSame) {
            lcaIndex = current;
        } else {
            break;
        }
    }
    return tree[lcaIndex];
}

int main() {
    int n, x;
    cin >> n;
    vector<string> tree(n);
    for (int i = 0; i < n; ++i) {
        cin >> tree[i];
    }
    cin >> x;
    vector<string> players(x);
    for (int i = 0; i < x; ++i) {
        cin >> players[i];
    }
    
    string result = findLCA(tree, players);
    cout << result << endl;
    return 0;
}

🍓 03.智慧树木修剪计划

问题描述

LYA 是一位热爱园艺的生态学家。她最近在研究一种特殊的树木，这种树木的生长模式形成了一个完美的二叉树结构。每个树节点都有一个特定的生态价值。然而，为了维持生态平衡，LYA 需要谨慎地修剪这棵树。

她发现，如果一个节点被修剪，其相邻的节点（父节点和子节点）就不能被修剪，以确保树的结构稳定性。此外，为了保持树的整体健康，最多只能修剪 个相邻的节点。

LYA 希望在这些限制条件下，最大化被修剪节点的总生态价值。你能帮助她设计一个最优的修剪方案吗？

输入格式

第一行包含两个整数 和 ，其中 表示树中节点的数量， 表示最多可以修剪的相邻节点数。

第二行包含 个整数，表示每个节点的生态价值。如果某个位置的值为 ，则表示该节点不存在。

输出格式

输出一个整数，表示在给定限制条件下，能够获得的最大生态价值总和。

样例输入

2 4
1 2 3 4

样例输出

9

数据范围

对于 100% 的数据，保证：

• 
• 
• 每个节点的生态价值

题解

这道题目可以使用动态规划来解决。关键是要理解状态的定义和转移方程。

定义 表示以节点 为根的子树，修剪了 个相邻节点（包括节点 自身）时能获得的最大生态价值。

状态转移方程如下：

1. 如果不修剪当前节点： ，其中

2. 如果修剪当前节点： ，其中 ，

最终的答案就是根节点的所有状态的最大值：，其中 。

时间复杂度：，其中 是节点数， 是最多可修剪的相邻节点数。 空间复杂度：。

参考代码

• Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxValue(self, root: TreeNode, k: int) -