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