笔试时间：2024年03月20日

历史笔试传送门：2023秋招笔试合集

第一题

题目：有效的重复字符

给定一个经过编码的字符串，按照特定规则返回它解码后的字符串。编码规则为: k{string}，表示大括号内部的 string 经过解码后重复 k 次，k 保证为正整数, string经过解码后为由a-z之间的字符组成的字符串，即大括号可能会有嵌套的情况。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的括号总是符合格式要求的。原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2{4}的输入，但是会出现像2{a3{b4{c}d}e}的情况。

样例输入一

"2{ac}"

样例输出一

"acac"

样例输入二

"2{ab3{ac}}"

样例输出二

"abacacacabacacac"

参考题解

简单的栈模拟。遇到数字则不断累加，遇到左括号则入栈，则清空之前积累的数字以及之前记录的字符串，遇到右括号则出栈，复制相应数量的字符串，遇到字符则添加至当前的字符串中。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <stack>
#include <string>

class Solution {
public:
    std::string decodeString(const std::string& s) {
        std::stack<std::pair<std::string, int>> sk;
        int num = 0;
        std::string curString = "";
        
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '{') {
                sk.push({curString, num});
                curString = "";
                num = 0;
            } else if (c == '}') {
                auto [lastString, cnt] = sk.top();
                sk.pop();
                std::string repeatedString;
                for (int i = 0; i < cnt; i++) {
                    repeatedString += curString;
                }
                curString = lastString + repeatedString;
            } else {
                curString += c;
            }
        }
        return curString;
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Stack;

public class Solution {
    public String decodeString(String s) {
        Stack<String> strStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();
        int num = 0;
        StringBuilder curString = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + Character.getNumericValue(c);
            } else if (c == '{') {
                strStack.push(curString.toString());
                numStack.push(num);
                curString = new StringBuilder();
                num = 0;
            } else if (c == '}') {
                String lastString = strStack.pop();
                int cnt = numStack.pop();
                StringBuilder repeatedString = new StringBuilder();
                for (int i = 0; i < cnt; i++) {
                    repeatedString.append(curString.toString());
                }
                curString = new StringBuilder(lastString).append(repeatedString);
            } else {
                curString.append(c);
            }
        }
        return curString.toString();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

class Solution:
    def decodeString(self, s) :
        # write code here
        sk = []
        num = 0
        cur_string = ""
        for c in s:
            if c.isdigit():
                num = num*10 + int(c)
            elif c == "{":
                sk.append((cur_string, num))
                cur_string = ""
                num = 0
            elif c == "}":
                ls_string, cnt = sk.pop()
                cur_string = ls_string + cur_string*cnt
            else:
                cur_string += c
        return cur_string

第二题

题目：字符/数字卡片拼电话号码

幼儿园老师与小朋友做游戏，老师准备一个电话号码，幼儿从一叠识字卡片(每张卡片上有0~9,A~Z,a~z中的一个字母)中抽出任意(大于零)张卡片，顺序展示，然后进行如下操作：选择任意连续的若干张卡片，并将这些卡片按从小到大顺序排列。任意多次操作后，若所有卡片组成的字符串与老师展示的电话号码完全相同，则该幼儿游戏成功，输出1，否则失败，输出0，若有字母，返回-1，给出电话号码，及N个幼儿选择的卡片序列，预测此轮游戏的结果。

提示：

1、卡片总数足够多，且每个字母的卡片数足够多；

2、电话号码只包含数字，长度最少为3，最大为11；

样例输入

"119",["191","911","19","129","1A9"]

样例输出

[1,1,0,0,-1]

说明

191，选取第二、第三个字符91进行排序，得到19，整个字符串变为119，返回1 911，选取第一、第二个字符91排序，得到19，字符串变为191，继续选取第二、第三个字符91排序，得到19，整个字符串变成119，返回1 19，长度不匹配，不能匹配成功，返回0 129，包含字符2，不能匹配成功，返回0 1A9，包含字母，返回-1。

参考题解

核心思路是 检查字符串的相对位置。例如 "54213" 能否转换成 "13254" ，我们可以从最高位开始往前考虑，最后一位是4，那么我们如何将 54213得到呢？由于 5[4213]中，4往后的所有数字均小于4，所以可以不改变相对位置的前提下直接将4换到最后，于是可以得到"52134"，如此我们继续考虑 "5213"能否转换成"1325"即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<int> sortSubStringToBuildPhoneNum(const std::string& phoneNum, const std::vector<std::string>& cardListArray) {
        int n = cardListArray.size();
        std::vector<int> res(n, 0);
        
        for (int i = 0; i < n; ++i) {
            std::string card = cardListArray[i];
            std::unordered_map<char, int> phoneCount, cardCount;
            
            for (char c : phoneNum) {
                phoneCount[c]++;
            }
            
            for (char c : card) {