六月丶

极致游戏21届校招游戏开发笔试编程题
前言昨天有幸参加了极致游戏的笔试,题目分为了30道选择题(60分)和2道编程题(40分),都只有一次进入作答的机会...
扫描右侧二维码阅读全文
29
2020/10

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

前言

昨天有幸参加了极致游戏的笔试,题目分为了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)。
输入格式
输入包含一行,一串平衡括号字符串
输出格式
输出包含一行,一个整数,根据规则计算出的该平衡括号字符串的值。

解题思路

对于这种匹配括号的题用栈或递归来做就很适合。

代码

#include<iostream>
#include<string>

using namespace std;

int func(string str,int &idx){
    if(str[idx]=='\0')return 0;
    else if(str[idx]=='('){
        if(str[idx+1]==')'){
            idx+=2;
            return 1 + func(str,idx);
        }
        else return 2*func(str,++idx);
    }
    else if(str[idx]==')')return 0;
}
int main(){
    int idx = 0;
    string str;
    cin >> str;
    cout << func(str,idx);
    
    return 0;
}

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;
}
本文作者:六月丶

本文链接:/index.php/archives/682/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2020 年 10 月 29 日 09 : 59 AM
如果觉得我的文章对你有用,请随意赞赏

发表评论