📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: 孤笑客
跳转到指定楼层
上一主题 下一主题
收起左侧

请教4道题目的最优做法(G家真题)

🔗
ryancooper 2015-10-30 01:01:52 | 只看该作者
全局:
对于第4题,要是全部输入的都是正整数的话,应该有个线性的算法
回复

使用道具 举报

🔗
z928czzc 2015-10-30 01:05:24 | 只看该作者
全局:
本帖最后由 z928czzc 于 2015-10-30 01:06 编辑
readman 发表于 2015-10-30 01:01
第二题我咋觉得即使boolean count[26] 看一下有几个出现过, 然后扫一下string, 有就放上去...


无法保证order。

对于例子bcacb。算法结果是bac。然而你会产生abc或者bca。
回复

使用道具 举报

🔗
readman 2015-10-30 01:08:16 | 只看该作者
全局:
z928czzc 发表于 2015-10-30 01:05
无法保证order。

对于例子bcab。算法结果是bca。然而你会产生abc。

- - 我没说清楚. 第二次扫数组的时候, 是看当前char是否应该保留. 保留了需要update count[].
回复

使用道具 举报

🔗
z928czzc 2015-10-30 01:11:21 | 只看该作者
全局:
readman 发表于 2015-10-30 01:08
- - 我没说清楚. 第二次扫数组的时候, 是看当前char是否应该保留. 保留了需要update count[].

对于例子bcacb。算法结果是bac。其中b是保留第一个b,而c是保留第二个c。你无法区分保留与否。
回复

使用道具 举报

🔗
z928czzc 2015-10-30 01:12:37 | 只看该作者
全局:
readman 发表于 2015-10-30 01:08
- - 我没说清楚. 第二次扫数组的时候, 是看当前char是否应该保留. 保留了需要update count[].

例子错了。。。等等。。。
回复

使用道具 举报

🔗
z928czzc 2015-10-30 01:14:19 | 只看该作者
全局:
readman 发表于 2015-10-30 01:08
- - 我没说清楚. 第二次扫数组的时候, 是看当前char是否应该保留. 保留了需要update count[].

你无法区分保留的顺序。

对于cabac。结果是abc。但是a是保留第一个,c是保留第二个。
回复

使用道具 举报

🔗
gorilazz 2015-10-30 01:41:28 | 只看该作者
全局:
z928czzc 发表于 2015-10-30 00:59
第一题只是排序的某种变形。Partial heap sort就能解决。

第二题比较interesting,想了几分钟,答案如下 ...

第二题用这个思路怎么样?
从后往前扫描string,同时保存当前出现的最小valid string。比如bcabc,从后往前扫描出来的顺序就是下面这样的:c->bc->abc->abc->abc。如果是abcab,顺序就是b->ab->cab->bca->abc

回复

使用道具 举报

🔗
gorilazz 2015-10-30 01:43:33 | 只看该作者
全局:
gorilazz 发表于 2015-10-30 01:41
第二题用这个思路怎么样?
从后往前扫描string,同时保存当前出现的最小valid string。比如bcabc,从后 ...

class Solution:

    def minValid(self, s):
        appeared = {}
        top = None
        for i in range(len(s)-1, -1, -1):
            if not s[i] in appeared:
                appeared[s[i]] = i
                top = s[i]
            else:
                if ord(s[i])<ord(top):
                    appeared[s[i]] = i
                    top = s[i]
        buf = []
        for c in appeared:
            buf.append((appeared[c], c))
        buf.sort()
        result = "".join([item[1] for item in buf])
        return result
        
sol = Solution()
result = sol.minValid("bcabc")
print(result)
回复

使用道具 举报

🔗
z928czzc 2015-10-30 02:15:25 | 只看该作者
全局:
本帖最后由 z928czzc 于 2015-10-30 02:16 编辑
gorilazz 发表于 2015-10-30 01:41
第二题用这个思路怎么样?
从后往前扫描string,同时保存当前出现的最小valid string。比如bcabc,从后 ...


无法保存和更新当前出现的最小valid string (or need exponential time)?在当前index的最小valid string可能和前后index的最小valid string没有任何关系。

举个反例还挺麻烦的。。。应该是 acbdefafedcb
你如何从afedcb切换到acbdef的???

回复

使用道具 举报

🔗
CrowSquad 2015-10-30 02:19:14 | 只看该作者
全局:
第一题用线段树啊!多好的东西啊!树状数组也行,实现起来还更方便。。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表