极致游戏21届校招游戏开发笔试编程题

六月丶

发布于 2022-12-26 17:58:05

8570

发布于 2022-12-26 17:58:05

文章被收录于专栏：六月-游戏开发六月-游戏开发

前言

昨天有幸参加了极致游戏的笔试，题目分为了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;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020 年 10 月，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树