BB 感觉挂经

__jind · 2019-10-17 02:24:08

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

x

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

BestOreo · 2019-10-19 22:57:54

请问第一题为什么要用stack，双指针O(1)不是更好?

__jind · 2019-10-20 00:02:49

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

__jind · 2019-10-20 05:15:30

哥大懒猫发表于 2019-10-19 22:57
请问第一题为什么要用stack，双指针O(1)不是更好?

class Solution():
def two_pointers(self, s):
# we always use p0, and if we find a repeating element we use p1
p0 = 0
p1 = None
while p0 < len(s):
p1 = p0 if p1 == None else p1 # p1 is not None, when we find our previous repeating elements
while p1 + 1 < len(s) and s[p1+1] == s[p0]:
p1 += 1
if p1 - p0 + 1 >= 3:
s = s[:p0] + s[p1+1:]
# we want to check previous element
p1 = p0
while p0 - 1 >= 0 and s[p0-1] == s[p0]:
p0 -= 1
p0 -= 1 # because later we have p0 += 1
else:
p0 = p1 # we are not eliminating things,
# but if we have two repeating elements we don't need to check the second element
p1 = None
p0 += 1
return s
def stack(self, s):
stack = []
p = 0
while p < len(s):
lis = [s[p]]
while stack != [] and s[p] == stack[-1]:
lis.append(stack.pop())
while p + 1 < len(s) and s[p+1] == s[p]:
p += 1
lis.append(s[p])
if len(lis) >= 3:
pass
else:
for j in lis:
stack.append(j)
p += 1
return "".join(stack)
a = Solution()
print(a.two_pointers('baacccabb'))
print(a.two_pointers(''))
print(a.two_pointers('abb'))
print("stack")
print(a.stack('baacccabb'))
print(a.stack(''))
print(a.stack('abb'))

复制代码

第一个写的不好，turns out 两个差不多

BestOreo · 2019-10-20 05:21:26

复制代码

__jind · 2019-10-20 05:41:33

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

kirska · 2019-10-20 06:13:07

是应该用stack，蠡口幺二凌久

quhe333 · 2019-10-29 17:09:45

kirska 发表于 2019-10-20 06:13
是应该用stack，蠡口幺二凌久

实名摸一下，tql

取个响亮的名号

请教下楼主，第二题follow-up不用循环语句该怎么做呢？还会加米的，感谢！

__jind

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