黑车噢诶

刚刚完成了黑车在线答疑 --

1. 给一个array of number，把第i个和第n-i个元素组队，i=0,1,2,...  把组队的结果依次打印出来。要求： 1. pair左边的元素应该不大于右边， 即如果arr[i] > arr[n-i], 对调两个元素后再打印； 2. 如果n为奇数，则最中间的元素无法配对，把这个元素放在最后也打印出来。
e.g. 给定  [2,5,7,

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

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

运气比较好，题目都挺简单的，第三题用的暴力搜索，本来想着超时了再优化，没想到提交以后就过了。四道题用了不到半小时，每道题都是300/300，但是最后总分849，可能是还不够快？

经常来地里逛逛，这次做了在线答疑回报地里！请大家帮我加点米啦，希望大家offer全中！

Felix1218 发表于 2022-3-17 01:15
给楼主加米了 祝一切顺利
请问第一题有要求一定要用原来的array 做in place的交换吗？还是可以用新的array ...

第一题没有要求in place，我用的是新的array。

第三题我是暴力搜索，就是看到一个1的格子就用while loop往四个方向搜索，比如左上角就是一直row--，col--，右上角就是row--，col++，etc。直到1: 碰壁；或者 2:位置上的数字不对（该是0的地方不是0，该是2的地方不是2）就停止。期间一直maintain最大长度。
这个解法的时间复杂度的上限应该是 O(m*n*(m+n)), m, n是矩阵的长和宽， 如果m=n,则是 O(n^3)。但是代码运行过程应该是 O(m*n) 左右，因为极端情况下：若所有点都是1，则每个点的搜索半径都是1，时间O(m*n)； 若只有一排/列点为1，则只需要搜索m/n个点，搜索半径为m+n，时间复杂度也是 O(m*n)。

做的时候还想了一些优化，比如一个点到上下左右边界的距离很好求，可以在搜索之前就算出来，如果长度不大于现有的max value，就可以跳过搜索这个方向了。可能还有其他的优化方法，请大家指教～

给楼主加米了 祝一切顺利
请问第一题有要求一定要用原来的array 做in place的交换吗？还是可以用新的array？
请问第三题您是用BFS吗？我在想是不是同时往四个对角线放在queue里面，如果这样做感觉检测已经访问过的格子并不容易，请问楼主是怎么处理/记录这个已经访问过的格子呢？谢谢🙏