前言

昨天有幸参加了极致游戏的笔试,题目分为了30道选择题(60分)和2道编程题(40分),都只有一次进入作答的机会。两道编程题趁还有映像赶紧记录一下。

1、平衡括号

题目描述

输入是一串全部由左括号和右括号组成且保证括号配对的字符串。例如:"()(()()(()()))"
现有一些计算规则如下:
() 值为1
AB 值为A+B
(AB) 值为2(A+B)
根据上述规则,样例"()(()()(()()))"的结果为:
=1+2
(1+1+2(1+1))
=1+2
(2+4)
=13
请编写程序,要求时间复杂度不大于O(n)。
输入格式
输入包含一行,一串平衡括号字符串
输出格式
输出包含一行,一个整数,根据规则计算出的该平衡括号字符串的值。

解题思路

这道题其实和表达式求值的问题类似,把单()当作是值为1的因子,(...)相当于2*子表达式值,(...)(...)相当于因子相加,用栈或递归来做就很适合。
而且在洛谷上有原题:括号的分数

代码

/*
  和只有+-()的表达式求值等价

 */
class Solution {
    stringstream ss;
public: 
        //返回表达式的分数
    int getb(){
        int num = gety();
        bool more = true;
        while(more){
            char c = ss.peek();
            if(c == '('){
                num += gety();
            }
            else more = false;
        }

        return num;
    }
    //返回因子的分数
    int gety(){
        int num = 0;
        ss.get();
        if(ss.peek() == ')'){
            ss.get();
            num = 1;
        }
        else{
            num = 2 * getb();
            ss.get();
        }
        return num;
    }
    int scoreOfParentheses(string s) {
        ss << s;
        return getb();
    }
};

2、题目忘了

题目描述

现给出一串字符串,例如"-1(3(2)(5))(4(6))",要求用该字符串生成一棵二叉树,并用中序遍历输出该二叉树。
创建节点顺序为先创建左子树再创建右子树,字符串中,整数代表该节点的值,用括号括起来的代表是一棵子树,样例中生成的二叉树为:
在这里插入图片描述
中序遍历结果为2 3 5 -1 6 4。
样例输入
-1(3(2)(5))(4(6))
样例输出
2 3 5 -1 6 4

解题思路

做该题分为两个步骤,先将字符串反序列化为一棵二叉树,然后用中序遍历输出该二叉树,其中中序遍历好说,而反序列化可像上题一样用递归来做。

代码

#include<iostream>
#include<string>

using namespace std;
//-1(3(2)(5))(4(6))
struct TreeNode{
    int val;
    TreeNode *left,*right;
    TreeNode(){
        val = 0;
        left = NULL;right = NULL;    
    }
};

int getVal(string str,int &idx){
    bool isZ = true;        //是正整数 
    int val = 0;
    char ch;
    while(ch = str[idx++]){
        if(ch=='-')isZ = false;
        else if(ch>='0'&&ch<='9')val = val*10+ch-'0';
        else {
            idx--;
            break;
        }
    }
    return isZ?val:-val;
}
TreeNode *func(string str,int &idx){
    if(str[idx]=='\0'||str[idx]==')')return NULL;
    TreeNode *p = new TreeNode();
    p->val = getVal(str,idx);
    if(str[idx]=='('){
        p->left = func(str,++idx);  //++为跳过该子树左括号
        if(str[idx]=='('){
            p->right = func(str,++idx);
        }
    }
    idx++;      //跳过该子树右括号
    return p;
}

void midPrint(TreeNode *head){
    if(head==NULL)return;
    midPrint(head->left);
    cout << head->val << " ";
    midPrint(head->right);
}
int main(){
    string str;
    cin >> str;
    int i = 0;
    TreeNode *head = func(str,i);
    midPrint(head);

    return 0;
}
最后修改:2022 年 10 月 08 日
如果觉得我的文章对你有用,请随意赞赏