最新狗家店面

Nathan220

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

昨天做的店面，题目很简单，45分钟就一道题，中间提示了不少，感觉答得不是很好，求onsite。

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

整体感觉提示有点多，然后听不是很清楚。估计跪了。

noclyt

MercyAPDY 发表于 2019-2-24 10:07
求教正确解法

拿一个变量 cnt 累计 ( 出现的次数。碰到 ) 就cnt--。一旦 cnt < 0 或者最后 cnt != 0 都是错误的。

MirandaChou

LZ有回复了吗？是LC 散凌伊吧 Hard呢

MercyAPDY

其实就是dfs回溯就可以了吧

noclyt

MercyAPDY 发表于 2019-2-24 07:55
其实就是dfs回溯就可以了吧

楼主说了要O(1)。 DFS 你怎么做到 O(1)

noclyt

想咨询一下细节：
1. 对于其他字符是不是跳过就行了，还有别的处理要求吗？
2. 对于 ')(' 是不是发现第一个 ) 直接输出 unbalance 就行了？

Nathan220

noclyt 发表于 2019-2-24 08:21
想咨询一下细节：
1. 对于其他字符是不是跳过就行了，还有别的处理要求吗？
2. 对于 ')(' 是不是发现第 ...

嗯，是的

MercyAPDY

noclyt 发表于 2019/02/24 08:17:09

楼主说了要O(1)。 DFS 你怎么做到 O(1)

求教正确解法

杨超越

直接o(n)时间扫一遍然后left count计数？这样就空间为O(1)了

tobebeyond

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

iq136man

直接扫描一遍就行了吧，设置一个counter，遇到‘（’counter++, ')' counter--, 如果counter<0 就返回 unbalance。