🐶虚拟上门

一轮BQ
四轮算法
1、 联通岛屿 + 杨辉三角
2、连续k项

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

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

么办 ，如果是国际象棋皇后怎么办

太难了

第三题是不是morris遍历啊？
不是说带人名的算法不会考吗？
谷歌不讲武德

第二题类似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)。

麻烦各位大佬看看，verify一下：

1. void freeTree( TreeNode*& root ) {
   
2.     while ( root != NULL ) {
   
3.         TreeNode* cur = root;
   
4.         TreeNode* parent = NULL;
   
5.         while ( cur->left != NULL ) {
   
6.             parent = cur;
   
7.             cur = cur->left;
   
8.             if ( cur->left == NULL ) {
   
9.                 if ( cur->right != NULL ) {
   
10.                     cur = cur->right;
    
11.                 }
    
12.             }
    
13.         }
    
14.         if ( parent == NULL ) {
    
15.             TreeNode* tmp = root;
    
16.             root = root->right;
    
17.             delete tmp;
    
18.             continue;
    
19.         }
    
20.         if ( parent->left != NULL ) {
    
21.             parent->left = NULL;
    
22.         } else {
    
23.             parent->right = NULL;
    
24.         }
    
25.         delete cur;
    
26.     }
    
27. }
    
28. int main() {
    
29.     TreeNode* root = new TreeNode( -1 );
    
30.     TreeNode* a = new TreeNode( 0 );
    
31.     TreeNode* b = new TreeNode( 1 );
    
32.     TreeNode* c = new TreeNode( 2 );
    
33.     TreeNode* d = new TreeNode( 3 );
    
34.     TreeNode* e = new TreeNode( 4 );
    
35.     TreeNode* f = new TreeNode( 5 );
    
36.     root->left = a;
    
37.     root->right = b;
    
38.     a->left = c;
    
39.     a->right = d;
    
40.     b->left = e;
    
41.     b->right = f;
    
42.     freeTree( root );
    
43.     assert ( root == NULL );
    
44. }

复制代码

祝楼主好运～请问杨辉三角那道题是什么样的？谢谢楼主！

第三题是不是root=Null然后交给gc就好了（逃

咳咳，请问一下这个是不是想问morris postorder啊，也太难了吧😭

第四题给的数据规模很小，是不是就是dfs暴力就可以了？

嗨，楼主，最后一题有步数限制嘛？如果没步数限制的话岂不是可以有无数种可能了吗？把所有非障碍点走一遍
10000
00***
00002

上图中，1是起点，星号是障碍物，2是终点，这种情况下，如果还得把所有非障碍点都走过一遍的话，第一行的第二列，第三列，第四列都得走两遍，
那上图还是一个VALID的INPUT吗？ 如果是的话，就代表一个点可以走无数遍，如果一个点可以走无数遍，那答案不久无穷大了吗？

vanquishz 发表于 2021-4-21 07:13
已加米。楼主不开空间释放一棵树是什么意思可以讲讲吗？

就是C++里面要free 一颗二叉树，不让用递归

teletubbylalala 发表于 2021-4-21 09:42
祝楼主好运～请问杨辉三角那道题是什么样的？谢谢楼主！

就是生成一个杨辉三角，很简单的一层一层生成

aug828 发表于 2021-4-21 12:40
第三题是不是morris遍历啊？
不是说带人名的算法不会考吗？
谷歌不讲武德

这题不会， morris没有掌握