首页 > 美团笔试8.22“阔豪”序列计算,小美的数学题
头像
谁能给我个offer啊
编辑于 2021-08-22 16:58
+ 关注

美团笔试8.22“阔豪”序列计算,小美的数学题

 

对大佬 牛客0X0001号 ac的代码进行讲解:

https://www.nowcoder.com/discuss/715645?source_id=profile_create_nctrack&channel=-1

例如s = '(()))()'

n = len(s)

0:‘(’进入变-1,  stk:[-1]

1: ‘(’进入变-1,stk:[-1, -1]

2:  “)”进入,检查stk最后一位,如果最后一位为-1说明此‘)’需要跟-1代表的“(”匹配  stk:[-1, 2]

3: "("进入 ,stk: [-1, 2, -1]

4 : ")"进入,stk:[-1, 2, 2]

注意这一步:



此步骤为 检测stk后面是否有连续的两个正数,如果有,这两个正数应该“相碰”(相乘), 因为两个正数挨着,说明这两个完整的括号部分挨着,因此必为相乘操作;
stk.size()-2 , stk.size()-1,就是后两位的idx, 相乘之后存在stk.size()-2的位置,因为最后一位需要被pop掉。

此时stk [-1, 4]

5: ")"进入, 由于最后一位不是‘-1’,说明这个右括号“)”肯定有前面未匹配的左括号“(”在等待。

规律:前面未匹配的左括号比为倒数第二位。因为后面可以匹配的正整数已经相互碰撞成了一个新的整数,所以stk最右侧最多只能连续存在一个正整数。如果不信可以自己试试。

因此执行此步骤:

stk[stk.size() - 2] = (1 + stk[stk.size() - 1]) % mod;
stk.pop_back();



此时stk:[5]

6:“(”进入,stk:[5, -1]
7:")"进入,stk:[5, 2]  碰撞相乘 得到[10]

最后输出结果





全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐