狗家新鲜vo

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

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

1 二分 类似刷题网吃香蕉那题.
3 two pointer
4 感觉见过不少次了 个人感觉是建立dp[i][j][Direction] 来做
1) dp[i][j][DOWN] = max(dp[i + 1][j][DOWN/LEFT/RIGHT] if matrix[i + 1][j] not blocked)
2) scan from left to right, right to left to update dp[i][j][RIGHT/LEFT]
3) check the first row to find the maximal path.


补充内容 (2021-05-12 23:46 +8:00):
不知道为啥dp[i][j][Direction]的第一维被吞了....

补充内容 (2021-05-12 23:47 +8:00):
dp 有 三维   i, j, direction

感谢楼主分享。最后一个题怎么样不会一直循环左右左右呢？

cxw111 发表于 2021-5-12 00:19
1 二分 类似刷题网吃香蕉那题.
3 two pointer
4 感觉见过不少次了 个人感觉是建立dp[j][Direction] 来 ...

第四题不能直接bfs吗？
不好意思，看错了，是最远。。。。

第三题 是啥意思啊， subsequence 怎么有最短的？是说substring吗?

请问下楼主第三题是啥意思？是要找包含a-z的substring中最小的吗？
第一题可以再解释一下吗？

ydog5 发表于 2021-5-31 21:53
请问下楼主第三题是啥意思？是要找包含a-z的substring中最小的吗？
第一题可以再解释一下吗？

yes

ZZ_2315 发表于 2021-5-31 21:20
第三题 是啥意思啊， subsequence 怎么有最短的？是说substring吗?

yes

结合的别的帖子来看第三题，可能理解错误，不喜勿喷。
输入2D arr比如
0 0 1 0
1 1 1 1
0 0 1 0
1 1 1 1
找到最长的一条由1 组成的length，只能向下，向左and向右，不能重复。求最远的走到最下面一层的路径。这个例子输出7
1 1 1
      1
1 1 1


首先从第一层开始扫描，因为只能向下，所以肯定是层数越多越占优势了。对于每一层从左到右再从右到左，分别与上一层的状态做dp，

从左到右：cur[i] = max(cur[i-1], last[i]) + 1 if grid is not 0 else 0
从右到左: cur[i] = max(cur[i+1], last[i]) + 1 if grid is not 0 else 0
然后对于两次扫描取最大值作为这一层的状态

需要一个数组表示上一层的状态，同时用两个数组表示下一层的状态。
例如：
扫描第一层之后，0还是0，1还是1，所以结果是 [0 0 1 0]
扫描第二层，从左到右是[1 2 3 4] 从右到左是[4 3 2 1],所以结果是[4 3 3 4]
扫描第三层，从左到右是[0, 0, 4 0] 从右到左是[0 0 3 0】 所以结果是0 0 4 0  
扫描第四层，从左到右是[1 ,2 ,5, 6] 从右到左是[7, 6, 5, 1]，所以结果是[7, 6, 5 ,6] 取最大值为7

第一题一看就是koko eat banana那道题。哈哈

补充内容 (2021-09-26 00:36 +8:00):
然后第三题应该就是蠡口遥遥舞的变种。目标string是"abcdef..z", 只不过要找的是长度，而不是个数