狗家面试挂经 求安慰米

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

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

时间复杂度常数级，每次棋盘横纵坐标各砍一半。
2^16 就进16次while循环。
已经测试跑通。

浅漾 发表于 2018-7-12 05:29
然后呢 你是找到了x轴的值 在往上那个y是多少呢？x,y最后加起来输出的数又是谁呢？ 二分直接找坐标不是很 ...

suixinsuoyu说的是对的，这题就是模拟quad tree的查找。楼主可以参考一下蠡口explore里的quad tree章节
https://leetcode.com/explore/learn/card/quad-tree/

suixinsuoyu 发表于 2018-7-12 06:09
**** 本内容被作者隐藏 ****

时间复杂度常数级，每次棋盘横纵坐标各砍一半。

你是对的 确实可以二分 厉害。。

suixinsuoyu 发表于 2018-7-12 06:09
**** 本内容被作者隐藏 ****

时间复杂度常数级，每次棋盘横纵坐标各砍一半。

恩 我看到他po的代码了 确实是对的 感谢你们

第一题就二分就行。大概思路是这样的：给定的x,y看是比当前矩阵边长的一半大还是小，可以知道这个是在0123中间的哪块。然后递归进行，传递下新的边长跟变换以后的坐标，以及base_sum就行。

拿题主的例子:比如说我们现在要找（2，1）（左上角为0，0，找到8）那就是1< 4/2 && 2>= 4/2. 所以可以判断2，1在2（右上角），他等价于右上角方格内的（0，1）。

对比右上角左下角2*2可知左下角矩阵加上一个数就是右上角，这个数就是base_sum=((边长/2)^2) * (0,1,2,3 base on loc) + base_sum.

然后就可以递归了，传进新的坐标，新的边长，base_sum.直到边长==2时停止，枚举出最后一次是0123中的哪一个，返回和base_sum的和就是答案。

因为限定了2^16所以是常数复杂的，如果不限定则是log边长

2，3，4 楼主都讲的很清楚了就不提了

5是 lc857

tinylic 发表于 2018-7-12 07:23
suixinsuoyu说的是对的，这题就是模拟quad tree的查找。楼主可以参考一下蠡口explore里的quad tree章节
...

怎么看不到这个链接？

浅漾 发表于 2018-7-12 05:44
额 string已经是中序遍历了 主要是找根 要把符号放在数字上面。。。转换成后缀是什么意思嘞？

所以这题是从后往前找+/- 作为根, 然后分割多项式成左右子树对吧. 如果前面有1X2X3X4X5X6X7X9+8楼主是怎么处理的

第一题感觉有点像变形的Hilbert Curve？

第二题数组里存的符号的意思是？如果+在-前面就是+是根的意思么

第四题有点像利口叁啾啾

LZ很厉害啊~ 祝LZ顺利~

浅漾 发表于 2018-7-12 05:44
额 string已经是中序遍历了 主要是找根 要把符号放在数字上面。。。转换成后缀是什么意思嘞？

那怎么确定跟是哪个符号呢  还有怎么确定乘除优先于加减啊

tinylic 发表于 2018-7-12 07:23
suixinsuoyu说的是对的，这题就是模拟quad tree的查找。楼主可以参考一下蠡口explore里的quad tree章节
...

大神你真厉害哈～