虾皮笔试 虾皮笔试题 0320
笔试时间: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) {
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。