买它 vo 口定挂

第一题不是2 pointers 就行吗 为什么大家都说要用stack 呀 求解释

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

你另一轮的口定题目我能问一下吗？

1215wl 发表于 2024-2-29 14:23
第一题不是2 pointers 就行吗 为什么大家都说要用stack 呀 求解释

2 pointers和stack是都可以做的应该

第二题的输出是不是没写完？比如  右下角那个1 2 a 0

第二题不是consecutive subarray吗？找到一个w点，然后一直往右走，走到不能走就找一个新起点。同理，可以一直往下走，不能走就找新起点。这样的话其实就是整个matrix遍历两遍就行。最后结果取最长的就可以。
TC: O(M*N)
SC: O(M*N) 可以优化，没细想

另外第二题给我感觉很像扫雷
你从每行右边开始扫，不是block就加一，否则清零。这样就能知道每个点往右最多能走多少
同理可以从下往上扫，知道每个点往下最多能走多少
两个合一下就是答案，也可以用一个矩阵，正负号表示方向

补充内容 (2024-03-02 21:56 +08:00):
说错了，不是扫雷，是一个炸弹人的题

Cinny080808 发表于 2024-2-29 18:17
第二题不是consecutive subarray吗？找到一个w点，然后一直往右走，走到不能走就找一个新起点。同理，可以 ...

他要的应该是你这个答案
但我当时脑子抽了 钻到dfs memo里面去了

第二题只能一个方向走，两个方向是独立的，可以分别算。从右下开始，往左往上走，每个W计数（x,y)，如果右边是边界或者b, x=0,否则x是右边的x加1，同理update y
最后算出来色x,y 取最大值加1就是从该点出发最长路径

补充内容 (2024-03-01 07:43 +08:00):
其实就是前面层主说的DP吧

Cinny080808 发表于 2024-2-29 18:17
第二题不是consecutive subarray吗？找到一个w点，然后一直往右走，走到不能走就找一个新起点。同理，可以 ...

朋友 求个这题的题号