🐶虚拟上门

jil261 发表于 2021-4-22 01:12
我写的dfs 然后followup那里的话复杂度爆炸了

是不是可以四维状压dp？dp[x][y][step][state]，起始状态dp[x0][y0][0][state1]，终止状态dp[x1][y1][k][state2]。(x0, y0) = 起点，(x1, y1) = 终点，k = 除了起点、终点和障碍外的格子总数目+1，state都是20位二进制，state1 = 把起点位置设为1，state2 = 除了障碍物以外的所有位置都是1。循环最外层按步数从0到k遍历，内层就不用说了。时间复杂度O(20 * 20 * 方向数 * (1 << 20))

最后一题可以用DP么，或者说dfs + cache.

dp[i][j] means from start to {i, j}, how many ways to reach {i,j},  还需要记录访问了多少空点.

dp[i][j]  = if ([i-1][j] not visited) + dp[i-1][j]  same to {i + 1, j} {i, j-1} {i, j + 1}.  另外感觉起点和终点有一定的限制, 如果两点是全局 4 * 5 随机的话, 会非常复杂。 这个时候貌似就需要用双向dfs+ cache了。 也就是从起点, 和终点各自开始dfs, 有相交点时, 两个的遍历必须访问了所有空点, 然后走法是相乘。 当然，做这些都是个人猜的，不一定work.
               

请问楼主是new grad吗

第二题类似presum吧。但是乘法有个坑就是0。感觉可以计算presum的时候把0当1处理，而且要记下所有0的index。最后查询的时候看看[lo, hi]这段区间有没有零有的话直接return 0。这样的话预处理应该是O(N)，每个query是O(logN）。

吐槽一下，谷歌的题都这么难的吗。。。。。。

补充内容 (2021-04-22 13:34 +08:00):
想到一个优化，，，可以不记录所有index的数目，而是记录“到index i为止总共出现了多少个0”，这样的话预处理是O(N)，每个query是O(1)。

第二题prefix product， 看到一个很好的BIT 讲解 https://iq.opengenus.org/fenwick-tree-range-product/

最后那个用 dp bitmask？ 毕竟网格很少

jil261 发表于 2021-4-22 01:14
就是每个点走过且只走一遍，步数是定死的

如果每个点走过且走以遍，步数是定死的话，步数要求就是所有可以走的点的个数呗。那么就算可以走四个方向，应该也可以动规。
不用记录之前走过哪些点，只用记录现在的位置，和走过的步数。
等步数到了上限的时候，发觉自己还没在终点，就返回0，在终点的话就返回1.因为如果步数又到了上限，人也在终点，那不就是代表所有可以走的点都走过了，而且只走了一遍嘛？
以上思路是DFS+MEMO。
所以是DP[ROW][COL][STEPS]

最后一题需要状态压缩，每个状态包含当前坐标x，y以及所有已经走过的点，因为4x5，可以用一个整数表示x，y 以及20个点，如果嫌状态压缩麻烦，可以只压缩所有已经走过的点，可以用一个三维数组保存状态[X][Y][status]
释放树那个题，不需要用morris，只需找到左孩子的最右孙子null节点，把当前节点的右子树放到最右子孙那即可

1. find borders of islands, do BFS, 杨辉三角, dp

请问一下楼主是在职跳槽还是new grad，看了几个new grad面经好像没有这么难呀