新鲜狗家面筋攒人品!! 求祝福!!!

jasonyang04 发表于 2018-2-26 13:27
谢谢楼主。我还是有两个问题，麻烦你能解答下。1. 围棋那题，我看了下LC130，是从边缘进行遍历，但是围棋 ...

想法的都是一样的 就是 bfs的时候 稍稍改一下规则, 如果遇到相同的棋子就压栈, 如果遇到空白的就返回没有死亡, 如果遇到对方的棋子就跳过

第二题是应该就是 longest increasing subsequence.
从头到尾遍历, 每次判断遍历到的数和 stack 顶部的数的大小,
如果当前的数大于栈顶元素, 就压栈, 否则就出栈, 直到 stack 为空或者栈顶元素小于当前元素
然后只要在运行过程中记录 stack 中元素个数的最大值就行

BigShaun 发表于 2018-2-26 13:53
同问第二题和LIS不一样吗？ 难道是要subarray不是subsequence？？

第二题应该就是 LIS, subsequence.
面试官给我的原题是  x < y < z and num.indexOf(x) < num.indexOf(y) < num.indexOf(z)

CankerHereAgain 发表于 2018-2-26 14:14
想法的都是一样的 就是 bfs的时候 稍稍改一下规则, 如果遇到相同的棋子就压栈, 如果遇到空白的就返回没有 ...

楼主你这个LIS不太对啊，比如输入数据是
2, 3, 1, 4
你一开始把 2, 3 压进去了
到 1 的时候把 2, 3 都弹出来了
最后把 4 压进去
你这样stack里面最多的时候元素为 2
但实际上 2, 3, 4 是一个长度为3的 LIS

CankerHereAgain 发表于 2018-2-26 10:12
https://www.youtube.com/watch?v=yCQN096CwWM
这个视频解释的很详细!

谢谢！！！ 视频讲的很好！

狗家bar这么高，感觉去了也是当分母。。。

jack213 发表于 2018-2-26 15:28
楼主你这个LIS不太对啊，比如输入数据是
2, 3, 1, 4
你一开始把 2, 3 压进去了

和我想的一样，出栈操作是可能改变当前的subsequence的起始位置的，如果扫array的时候看到了比栈底元素更小的元素会导致所有元素出栈，会错过可能的解。

就是说，单调栈解决不了之后看到的数据比栈里最小的数据更小，并且后来数据存在比当前栈里数据更大的情况。

ps 楼主发的视频确实讲的非常好。