一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
查看: 984|回复: 8
收起左侧

骨骼蠡口分类整理之Stack栈

[复制链接] |只看干货 |面试经验, 美国面经, google, 码农类general
我的人缘0

升级   70%


分享帖子到朋友圈
yangzhit | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (270)
 
 
0% (1)    👎

2022(10-12月) 码农类General 硕士 全职@Google - Other - 其他  | Other | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
主贴 骨骼蠡口分类整理 https://www.1point3acres.com/bbs/thread-649468-1-1.html
分贴(一)骨骼蠡口分类整理追加单调队列 https://www.1point3acres.com/bbs/thread-651314-1-1.html

6个月内
Easy 1021, 844, 155, 20,
Medium 946, 739(单调队列), 901(单调队列)
1209. Remove All Adjacent Duplicates in String II
735. Asteroid Collision
636. Exclusive Time of Functions
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
1, 1019, 103(Microsoft), 1249, 71(Facebook), 150(linkedin)
Hard 772,  591(Microsoft)

由于最近没有跳槽计划,所以只做6个月新题。带标题的是没有Python版的,Hard可能也不会做。大家有简便的解法欢迎跟帖加注释。

评分

参与人数 4大米 +6 收起 理由
何曾渡光 + 2 很有用的信息!
wyu51 + 1 给你点个赞!
shunshunlili + 1 给你点个赞!
lingyuenu + 2 给你点个赞!

查看全部评分


上一篇:capitalone ba virtual interview
下一篇:脸家SWE实习过经
我的人缘0

升级   70%

 楼主| yangzhit 2020-10-31 16:52:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (270)
 
 
0% (1)    👎
1021. Remove Outermost Parentheses
参考这个贴,没有用栈,大家有什么栈的解法可以列一下。
https://blog.csdn.net/fuxuemingzhu/article/details/89067501
逻辑是左括号个数和右括号个数一致就去边,剩下的为里层。
class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        rest=""
        pre=0
        count=0
        l = len(S)
        i=0
        while i < l:
            if S == '(': #计算左括号
                count=count+1
            else: #扣除右括号
                count=count-1
            if count==0: #计数为0说明最外层
                rest = rest + S[pre+1:i]
                pre = i + 1
            i=i+1
        return rest
回复

使用道具 举报

我的人缘0

升级   70%

 楼主| yangzhit 2020-10-31 16:56:56 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (270)
 
 
0% (1)    👎
844. Backspace String Compare
判断带退格键#的字符串是否一致
class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        rs = []
        for s in S:
            if s=="#" and len(rs)>0: #碰到退格键,出栈
                rs.pop()
            elif s == "#": #空字符串跳过
                continue
            else:
                rs.append(s)
        rt = []
        for t in T:
            if t=="#" and len(rt)>0:
                rt.pop()
            elif t == "#":
                continue
            else:
                rt.append(t)
        if rs == rt:
            return True
        else:
            return False
回复

使用道具 举报

我的人缘0

升级   70%

 楼主| yangzhit 2020-10-31 17:07:38 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (270)
 
 
0% (1)    👎
155. Min Stack
最小栈, 多用一个栈存最小数。每次入栈,抛弃比栈顶大的数,因为不是最小。
class MinStack:

    def __init__(self):
        self.stack=[]
        self.minstack=[] #存最小数

    def push(self, x: int) -> None:
        self.stack.append(x)
        if len(self.minstack)==0 or self.minstack[-1]>=x: #如果小于等于栈顶,则入栈。
            self.minstack.append(x)

    def pop(self) -> None:
        current = self.stack.pop()
        if len(self.minstack)>0 and self.minstack[-1]==current: #如果栈顶刚好是最小数
            self.minstack.pop()
        return current

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minstack[-1]
回复

使用道具 举报

我的人缘0

升级   70%

 楼主| yangzhit 2020-10-31 17:12:15 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (270)
 
 
0% (1)    👎
20. Valid Parentheses
三种括号配对成字符串。
class Solution:
    def isValid(self, s: str) -> bool:
        pairs={}
        pairs[")"]="("
        pairs["}"]="{"
        pairs["]"]="["
        stack=[]
        for c in s:
            if c in pairs:
                if len(stack)==0 or stack[-1] != pairs[c]: #右括号入空栈或者右括号不配栈顶
                    return False
                stack.pop()
            else:
                stack.append(c)
        if len(stack)>0: #栈不为空
            return False
        return True
回复

使用道具 举报

我的人缘0

升级   70%

 楼主| yangzhit 2020-10-31 17:18:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (270)
 
 
0% (1)    👎
946. Validate Stack Sequences
入栈串跟出栈串匹配,可能要交叉
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        i=0
        j=0
        l = len(pushed)
        while i<l:
            stack.append(pushed[i]) #入栈
            i = i + 1
            while len(stack)>0 and j<l: #匹配出栈和栈顶
                if stack[-1] == popped[j]:
                    j = j+1
                    stack.pop()
                else:
                    break
        if j<l:
            return False
        else:
            return True
回复

使用道具 举报

我的人缘0

升级   5%

xiana406 2020-10-31 18:51:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (147)
 
 
1% (2)    👎
请问楼主还有其他的总结吗?
回复

使用道具 举报

我的人缘0

升级   70%

 楼主| yangzhit 2020-10-31 19:29:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (270)
 
 
0% (1)    👎
xiana406 发表于 2020-10-31 18:51
请问楼主还有其他的总结吗?

题号可以先看主贴,后面的详细整理,只能做一类贴一类。原来有个Google Doc,应该是不能放上去被删了。
回复

使用道具 举报

我的人缘0

升级   70%

 楼主| yangzhit 2020-11-1 13:56:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (270)
 
 
0% (1)    👎
1209. Remove All Adjacent Duplicates in String II
删除所有重复K次的字符子串
跑LC会Time Limit Exceeded, 有好的算法请共享
class Solution:
    def removeDuplicates(self, s, k):
        stack=[]
        for c in s:
            stack.append(c)
            if self.isdup(stack, k):
               stack=stack[:len(stack)-k]
        count=0
        r=""
        while count<len(stack):
            r=r+stack[count]
            count=count+1
        return r

    def isdup(self, stack, k):
        if len(stack)<k:
            return False
        i=1
        while i<k and stack[-i]==stack[-i-1]:
            i=i+1
        if i<k:
            return False
        return True
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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