shopee 2021秋招部分笔试题汇总

最新推荐文章于 2024-10-20 18:29:49 发布

程勇uestc

最新推荐文章于 2024-10-20 18:29:49 发布

阅读量1.9k

点赞数

分类专栏： Leetcode 文章标签：笔试虾皮 shopee

本文链接：https://blog.csdn.net/qq_40438165/article/details/118423229

版权

Leetcode 专栏收录该内容

11 篇文章

订阅专栏

本文介绍了LeetCode中的六个字符串处理和算法题目，涉及罗马数字转换、命名转换、算术运算、二叉搜索树叶节点查找、有效括号字符串检查及链表翻转。通过实例演示了如何运用栈、哈希映射等数据结构解决这些问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1、Leetcode13 罗马数字转整数

class Solution {
public:
    int romanToInt(string s) {
        int n = s.size();
        unordered_map<string, int> mp;
        mp["I"] = 1, mp["V"] = 5, mp["X"] = 10, mp["L"] = 50,
        mp["C"] = 100, mp["D"] = 500, mp["M"] = 1000;
        mp["IV"] = 4, mp["IX"] = 9;
        mp["XL"] = 40, mp["XC"] = 90;
        mp["CD"] = 400, mp["CM"] = 900;
        int res = 0;
        for(int i = 0; i < n;){
            if(i + 1 < n && mp.count(s.substr(i, 2))) res += mp[s.substr(i, 2)], i += 2;
            else res += mp[s.substr(i, 1)], i ++ ;
        }
        return res;
    }
};

2、字符串命名转换

孔乙己说“回”字有四种写法，编程语言中常见的命名风格有如下四种：

全部首字母大写
第一个单词首字母小写，其余单词首字母大写
单词全部小写，由下划线连接
单词全部小写，由减号连接

请设计并实现一个caseTransform函数，使得一个字符串str可以被方便地转成四种形式，并且将四种形式通过空格拼接成一个字符串返回为方便起见，这里假设输入字符串全部符合以上四种形式的英文字母组合。

输入样例：

PascalCaseTest

输出样例：

PascalCaseTest  pascalCaseTest  pascal_case_test pascal-case-test

#include <iostream>
#include <map>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
using namespace std;


int main()
{
    string s; cin >> s;
    vector<string> words;
    if(s[0] >= 'A' && s[0] <= 'Z') s[0] += 'a' - 'A';
    s += '-';
    string word;
    for(char c: s){
        if(c == '-' || c == '_' || (c >= 'A' && c <= 'Z')){
            words.push_back(word);
            word.clear();
            if(c >= 'A' && c <= 'Z'){
                c += 'a' - 'A';
                word += c;
            }
        }else word += c;
    }
    string res;
    for(string word: words){
        word[0] += 'A' - 'a';
        res += word;
    }
    cout << res << " ";
    res = words[0];
    for(int i = 1; i < words.size(); i ++ ){
        string t = words[i];
        t[0] += 'A' - 'a';
        res += t;
    }
    cout << res << " ";
    res = words[0];
    for(int i = 1; i < words.size(); i ++ ) {
        res += '_' + words[i];
    }
    cout << res << " ";
    res = words[0];
    for(int i = 1; i < words.size(); i ++ ) {
        res += '-' + words[i];
    }
    cout << res << endl;
    return 0;
}

3、字符串算术运算

给定一个字符串式子，返回它的计算结果。算术规则为: k*[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。e.g. s = “3*[a2*[c]]”, 返回 “accaccacc”。
输入样例：

3*[a2*[c]]

输出样例：

accaccacc

题解：经典问题，栈模拟即可

class Solution {
public:
    string computeString(string s) {
        stack<string> st;
        for(char c: s){
            string t;
            t += c;
            if(c != ']') st.push(t);
            else{
                vector<string> arr;
                while(st.top() != "[") arr.push_back(st.top()), st.pop();
                reverse(arr.begin(), arr.end());
                t = "";
                for(string &a: arr) t += a;
                string num;
                if(st.top() == "[") st.pop();
                if(st.top() == "*") st.pop();
                while(!st.empty() && st.top()[0] >= '0' && st.top()[0] <= '9') num += st.top(), st.pop();
                reverse(num.begin(), num.end());
                int n = stoi(num);
                string temp;
                while(n -- ) temp += t;
                st.push(temp);
            }
        }
        vector<string> res;
        while(!st.empty()){
            res.push_back(st.top());
            st.pop();
        }
        reverse(res.begin(), res.end());
        string anw;
        for(string r: res) anw += r;
        return anw;
    }
};

4、查找二叉搜索树的叶子节点

给一个二叉查找树（Binary Search Tree）的前序遍历结果数组，打印出所有的叶子节点。
输入描述:

输入为二叉查找树的前序遍历结果数组，元素之间用空格分隔：
9 8 7 10

输出描述:

所有的叶子节点元素，用空格分隔
解释：因为二叉搜索树的表示为:
       9
   8    10
7
输出的叶子节点为: 7 10

输入例子1:

9 8 7 10

输出例子1:

7 10

题解：二叉搜索树的中序遍历得到的序列是递增的，因此我们可以得到该二叉树的前序遍历和中序遍历，并据此重建二叉树。根据重建的二叉树进行遍历即可得到叶子节点。

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left, *right;
    TreeNode(int val){
        this->val = val;
        this->left = this->right = NULL;
    }
};

TreeNode *dfs(vector<int> &pre, vector<int> &in, int preL, int preR, int inL, int inR) {
    if(preL > preR) return NULL;
    TreeNode *root = new TreeNode(pre[preL]);
    int mid = 0;
    while(in[mid] != pre[preL]) mid ++ ;
    root->left = dfs(pre, in, preL + 1, preL + mid - inL, inL, mid - 1);
    root->right = dfs(pre, in, preL + mid - inL + 1, preR, mid + 1, inR);
    return root;
}

void preOrder(TreeNode *root) {
    if(root == NULL) return;
    if(root->left == NULL && root->right == NULL)
        cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

int main() {
    vector<int> pre, in;
    int t;
    while(cin >> t) {
        pre.push_back(t);
        in.push_back(t);
    }
    sort(in.begin(), in.end());
    int n = pre.size();
    TreeNode *root = dfs(pre, in, 0, n - 1, 0, n - 1);
    preOrder(root);
    return 0;
}

5、有效的括号字符串

给定一个只包含三种字符的字符串：（，）和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

输入例子1:

"()"

输出例子1:

true

输入例子2:

"(*)"

输出例子2:

true

输入例子3:

"(*))"

输出例子3:

true

题解：正向扫描字符串，*当(处理，实时统计(和)数目，需要保证左括号数目时时刻刻不少于右括号数目；再反向扫描字符串，*当)处理，需要保证右括号数目时时刻刻不少于左括号数目。

bool checkValidString(string s) {
    int l = 0, r = 0;
    for(char c: s){
        if(c == '(' || c == '*') l ++ ;
        else r ++ ;
        if(l < r) return false;
    }
    reverse(s.begin(), s.end());
    l = 0, r = 0;
    for(char c: s){
        if(c == ')' || c == '*') r ++ ;
        else l ++ ;
        if(r < l) return false;
    }
    return true;
}

6、以组为单位翻转单向链表

给一个单向链表以及整数N，使得每N个元素为一组进行翻转。要求时间复杂度O(n), 空间复杂度O(1)。
输入例子1:

{1,2,3,4,5,6,7,8},3

输出例子1:

{3,2,1,6,5,4,8,7}

ListNode* reverseLinkedList(ListNode* head, int n) {
    int len = 0;
    for(auto p = head; p; p = p->next) len ++ ;
    ListNode *pre = NULL, *cur = head;
    for(int i = 0; i < min(n, len); i ++ ){
        auto t = cur->next;
        cur->next = pre;
        pre = cur;
        cur = t;
    }
    if(n > len) return pre;
    head->next = reverseLinkedList(cur, n);
    return pre;
}