Python yield 和 leetcode space optimization

2020-04-18 18:15:58 +08:00
 MainHanzo

最近刚好做到了 leetcode 844 这道题,说的是两个字符串,里面如果出现# 则代表用户回退上个输入字符,最后判断下两个输出字符是否相同。 我想到的最直接的解法是 On 时间 On 空间, 对每个 char 进行判断,然后遇到#就把最后一个删掉,最后比较。 看了下 solution 里的最优解是 O1 space 的,利用了 yield 这个关键词,在遍历字符串的时候每次只返回一个 char,然后进行判断,判断完就把这个 char 删掉。的确很巧妙,但是我提交了下发现使用空间和我的 On 没什么区别。

我很好奇为什么会有这个现象,在 python3 里,yield 的优势已经不存在了吗?还是 leetcode 的空间计算有什么特性? 在写 leetcode 题时,该怎么正确降低 space 使用呢?

1872 次点击
所在节点    Python
5 条回复
ipwx
2020-04-18 18:28:12 +08:00
所以答案连接?我看了一眼评论区,不少 O1 space 不用 yield 的呀,谁知道你 yield 怎么写的。
----

减少 space 占用请用 C++。
ipwx
2020-04-18 18:50:55 +08:00
MainHanzo
2020-04-19 20:52:55 +08:00
@ipwx 不好意思 没看到咋传图。
可是 Leetcode 里 space 的比较不应该是按语言分开的么。python 的 space performance 不可能直接和 c 语言做比价吧。
MainHanzo
2020-04-19 20:54:57 +08:00
@ipwx https://leetcode.com/problems/backspace-string-compare/solution/ 是直接 solution 里的 python 解法, 用了 yiedl
ipwx
2020-04-19 21:10:56 +08:00
itertools.izip_longest 是 python 2 的函数,python 3 叫做 itertools.zip_longest 。所以你说的这个版本的答案肯定是 python 2 。(这就尴尬了

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/663794

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX