题目是让你判断一棵树是不是满足条件，是一颗平衡树？dngdnhxqs 发表于 2022-07-22 15:53
题目：一棵Balanced Tree, 满足以下条件，树的每一个节点都是一个素数，从根节点开始，每一层的每个节点的素数都是上一层的所有素数的两倍以上，而每一层的同层素数满足从左到右依次增大。设计一套最优算法判断对于任何一棵Balanced Tree, 以上条件是否满足，并写出算法的time complexity。 头文字D 发表于 2022-07-22 15:51
被人盗号了？ ChristinaW 发表于 2022-07-22 15:54
这是easy题吧？没让你手写红黑树算给你机会了 me2me2 发表于 2022-07-22 15:55
看了三遍没看懂题目，我默默回去读书了。 crazyeater 发表于 2022-07-22 15:57
D哥有戏。最近结了不少善缘，华人上马工姐妹不少，我看你找对路了！ Heiniu 发表于 2022-07-22 16:00
所以time complexity 是什么？我回来之后，还是百思不得其姐 头文字D 发表于 2022-07-22 15:56
o(logn) ChristinaW 发表于 2022-07-22 16:02
对我们这种文科生来说，转码太难了，你要加油，我也要加油 头文字D 发表于 2022-07-22 15:58
你不是中科大的吗？难道我弄错了？ xiaofengxian 发表于 2022-07-22 16:06
你和楼上的答案就不一样，我该信谁？ 头文字D 发表于 2022-07-22 16:03
我觉得o(n)太容易了，所以觉得应该是logn, 怎么做还没想出来～～ ChristinaW 发表于 2022-07-22 16:09
唉，难说，我上次和潮水哥提了一下，希望他内推，结果自从那次之后，潮水哥再也没找过我说话了 头文字D 发表于 2022-07-22 16:01
我只在学校学过红黑树，之后再也没见过。别吓人 孤傲招财猫 发表于 2022-07-22 16:12
应该 是 O(N), 用个 queue， 典型的 BFS with slight modification. 素数应该是 assume 不用判断了， 否则， 加起来 15 分钟有点难度。 FB 也不会这么要求。 gokgs 发表于 2022-07-22 16:31
这题感觉就是一个基本的数学题，不是很难的一道数学题，知道思路怎么做，虽然我不会写码。看来码工还是要有好的数学基础，很基础的数学知识 elee555 发表于 2022-07-22 16:15
素数不是assume的, 要判断是否是素数，否则你放素数的要求没意义啊，如果只考树的结构，放任何数还不是一样 头文字D 发表于 2022-07-22 16:33
当然是你搞错，LOL，就我这高中花了90%时间去打球和谈恋爱的，我要考到中科大，我神仙了 头文字D 发表于 2022-07-22 16:08
光判断素数 15 分钟也不一定够。 gokgs 发表于 2022-07-22 16:39
BFS? doge2moon 发表于 2022-07-22 16:38
回复 42楼miaka的帖子 确实，素数判定很简单，几行code if (n == 0 || n == 1) { is_prime = false; } for (i = 2; i <= n/2; ++i) { if (n % i == 0) { is_prime = false; break; } } gvcc 发表于 2022-07-22 16:54
应该用的是BFS，因为要按每层来判断，我觉得还要另外加一个array 储存上一层的节点，还是有更好的方法？ update: 不用另外的array, 如果h > 2g, 则 h 必然大于 g 左边的所有节点的2倍 头文字D 发表于 2022-07-22 16:59
应该用的是BFS，因为要按每层来判断，我觉得还要另外加一个array 储存上一层的节点，还是有更好的方法？ update: 不用另外的array, 如果h > 2g, 则 h 必然大于 g 左边的所有节点的2倍，因为每一层从左到右依次增大 头文字D 发表于 2022-07-22 16:59
BFS 用 queue 阿， 外加一个变量存 max so far and the first value in each level 就应该差不多了。 gokgs 发表于 2022-07-22 17:05
你起码要写个 上限是平方根的，哈哈。 数多了， 筛子法可能更好， 还有可能 cache 之类的， 稍微一讨论 15 分钟就没了。 所以我觉得这题考点应该是 BFS 的变种。 gokgs 发表于 2022-07-22 17:04
queue有什么好用的。就用simple array好了。面试能用STL吗？ miaka 发表于 2022-07-22 17:17
你还没面试过吧？ 连 queue 都不用， 典型的 red flag. gokgs 发表于 2022-07-22 20:24
没有啊，转码一直是我的理想，过去半年，我自学了Python 我要搬去加州，找你踢球 头文字D 发表于 2022-07-22 15:55
判断既是平衡树，也满足关于以上素数的所有条件
这是easy题吧？没让你手写红黑树算给你机会了
没有啊，转码一直是我的理想，过去半年，我自学了Python 我要搬去加州，找你踢球
所以time complexity 是什么？我回来之后，还是百思不得其姐
你没准备任何算法就去转码了？
对我们这种文科生来说，转码太难了，你要加油，我也要加油
唉，难说，我上次和潮水哥提了一下，希望他内推，结果自从那次之后，潮水哥再也没找过我说话了
o(logn)
你和楼上的答案就不一样，我该信谁？
time complexity是计算你写的算法的runtime，有些固定的算法的
你不是中科大的吗？难道我弄错了？
当然是你搞错，LOL，就我这高中花了90%时间去打球和谈恋爱的，我要考到中科大，我神仙了
我觉得o(n)太容易了，所以觉得应该是logn, 怎么做还没想出来～～
我只在学校学过红黑树，之后再也没见过。别吓人
这里面有几个tricks, 我回家后做了一下研究，我发现光判断素数这里就有几种不同的方法，而每种方法的时间复杂度也是不一样的，给你参考一下
https://blog.csdn.net/huang_miao_xin/article/details/51331710
哦，男人比较没义气 尤其你那楚留香的人设定位估计不受男人待见
开玩笑的，没找潮水哥内推过，但潮水哥这段时间比较忙，所以我和他老男人时间见面得比较少
素数应该是 assume 不用判断了， 否则， 加起来 15 分钟有点难度。 FB 也不会这么要求。
没听说过有人考红黑树。 哈哈。
素数不是assume的, 要判断是否是素数，否则你放素数的要求没意义啊，如果只考树的结构，放任何数还不是一样
我敢打赌考点肯定不是素数上。
看了你的回复不是码农科版。那你去上个data structure 在上个algorithm就可以了。 这个是判断true/fasle，所以worst case用recursion要全过一遍。再看看每次call yourself时候要比较几次。blanaced tree应该是sorted了吧？概念记不清了。但根据题目要求还要比较每层大小就不能assume是sorted的。 每个recursion input parent node保证他有children 1.先看是不是sorted满足left《parent〈 right. 2.然后比大小 判断是不是素数 and 是不是大于两倍 parent worst case是true的情况你自己数数要call几次recursion，每次1-2情况要比较次数是不是和N有关。判断素数是O（N）/ O（square(N))
所以只要数recursion的次数乘以O（N）就是和node number(N) 的关系。
BFS?
光判断素数 15 分钟也不一定够。
哈哈哈哈 我一看你就是玩儿咖 不过我学生时代也是 最后毕业好累的😆
left < parent < right 不对哦
left and right both must be > 2x parent
为什么？不就是几个condition加一个iteration？prime不就是找找除了1和它本身，有没有能被除得整数的。
我看题不仔细。那就是按你写的要求比较大小。一回事。 改成left< right and left > 2parent and right > 2 parent
你好歹也弄个比较大小啊。也不至于交白卷
看了俩遍没看懂，我只好去编码去了。
确实，素数判定很简单，几行code
if (n == 0 || n == 1) { is_prime = false; }
for (i = 2; i <= n/2; ++i) { if (n % i == 0) { is_prime = false; break; } }
如果你是cs 的faculty 那不算“转码”。如果是别的专业的，费那劲干嘛呀？
应该用的是BFS，因为要按每层来判断，我觉得还要另外加一个array 储存上一层的节点，还是有更好的方法？
update: 不用另外的array, 如果h > 2g, 则 h 必然大于 g 左边的所有节点的2倍，因为每一层从左到右依次增大
你起码要写个 上限是平方根的，哈哈。
数多了， 筛子法可能更好， 还有可能 cache 之类的， 稍微一讨论 15 分钟就没了。 所以我觉得这题考点应该是 BFS 的变种。
你这就不考虑memory/space complexity了？一个easy题你search啥。
BFS 用 queue 阿， 外加一个变量存 max so far and the first value in each level 就应该差不多了。
balanced binary tree吧。lz如果知道complete binary tree可以分层用数组表示，这题很容易做
老实说这种不难但是就是把几个基础概念混在一起吓人的题目，就是用来劝退你们这些转码人士的
不需要额外变量，每一层从左到右判断大小，然后拐弯到下一层的时候判断是否大于2倍
那个id明显不懂
题目要求判断每个元素是否满足要求，这怎么可能是log（n）
queue有什么好用的。就用simple array好了。面试能用STL吗？
熟练工肯定一提笔就是perfect解。LZ这样的15分钟能写多少写多少。挑基本简单的方法，写完bug free再考虑优化
你还没面试过吧？ 连 queue 都不用， 典型的 red flag.
我又不是码农我不需要面试啊。我又不穷也不需要转码。 我上学时候写作业是不许用STL的。什么都自己写。但可以用time计算algorithm时间写结论。给用STL那码农面试还是挺好的。
ChristinaW 是男银 ？？