怎么用电脑windows做网站,广州免费发布信息网,网络营销策划模板,西安企业网站设计哪家专业第一场#xff1a;2018年12月30日#xff08;周日#xff09;#xff0c;北京时间早上五点。 写在最前面#xff1a;好不容易五点爬了起来围观mock#xff0c;结果早上周赛睡过去了#xff0c;唉。orz。 面试官#xff1a;wisdompeak#xff0c;同学#xff1a;littl… 第一场2018年12月30日周日北京时间早上五点。 写在最前面好不容易五点爬了起来围观mock结果早上周赛睡过去了唉。orz。 面试官wisdompeak同学littleRainRain 第一题有个花圃矩阵 gridsize 是n * m花圃上面的一个点坐标是(x, y)上面可能有花可能没有花没有花的话矩阵上的值为0。如果一个Q(x,y)上有花的话grid[x][y] W W代表这朵花的香气随着距离这朵花越来越远花的香气会逐渐减弱减弱的关系和两个点的曼哈顿距离成正比比如在点 P(x1, y1)能闻到在点Q的花的香味是 f W / (abs(x- x1) abs(y-y1))。输入一个P点的坐标(px, py)求在这个P点能闻到花的香味最重的点坐标。 题解直接二维矩阵遍历就行。只有一点需要注意的就是曼哈顿距离为0的时候0不能做除数怎么处理要问面试官不要自己yy。 follow-up能不能让算法更快一点其实我觉得这个问法不是特别的优秀第一次听到了比较容易懵逼如果我是面试者的话下面不知道该怎么接。直接问具体条件有什么变化还是新增了什么条件么 我第一次听到follow-up有点懵逼我还以为难道bfs能解...但是迅速的否认了自己的想法想象一下如果有个点距离给出的P点非常非常远但是它的W非常非常大这个点也有可能是candidate。 后来面试官解释了一下假设这个花圃上面就几朵花呢然后调用query方法N次如何加速这个算法言下之意是这个矩阵是一个稀疏矩阵 ok那我们开始预处理下矩阵把有花的坐标点给存下来存成一个数组假设叫flowerCoor然后每次query的时候就从flowerCoor里面取花的坐标然后计算。 第二题leetcode 837 New 21 Game https://leetcode.com/problems/new-21-game/description/ 面试官化简了一下这个题他的问题是桌面上有10张扑克牌代表[1, 10]这个区间的数字玩家一开始有个基础分数 score 游戏开始score 代表现在点数如果 score 17 那么庄家随机翻一张牌累加score如果 score 在[17, 21] 这个区间中就代表庄家win如果 score 21 就代表玩家win。求玩家 win 的概率。 前面怎么讨论的我有点记不清了但是妹子说了一句“这个题有点递归的意思”然后就开始递归做。递归可以做。不知道如果递归写全对的话下面follow-up会不会扩大规模考 dp。不过想不到 dp不知道是 hired 还是 weak hired 了 lc递归会超时我加了记忆化递归也超时了 :( lc给的是 dp 解法。 mock的时候群里小伙伴有人说这题和 688 很像https://leetcode.com/problems/knight-probability-in-chessboard/description/ 第三题leetcode 636 Exclusive Time of Functions https://leetcode.com/problems/exclusive-time-of-functions/description/ 第三题有点类似资源抢占调度的一道题。 task 1: start, 0 task 2: start, 2 task 2: end, 3 task 1: end, 4 task 2: start, 6 task 2: end, 7 start, end just mean get schecduled, like process to CPU, only one cpu, so if task2 started, task 1 paused。 要求返回每个task占用cpu的时间。返回map也好数组也好都行。 用stack解我还没仔细想。我估计应该是用一个变量或者pair存某个任务被中断的时间 第四题leetcode 528. Random Pick with Weight https://leetcode.com/problems/random-pick-with-weight/description/ 群主给的就是有 N 个人种每个人种的占比实现一个算法这个算法每次都会返回一个人种在调用KK是一个很大的数次的情况下所有的返回值的比例满足人种的占比。 given possibility like chinese 22% american: 5% indian: 21% ... 各个概率之和保证为1随机选一个,要求符合概率,如按22.333% sample chinese.. 妹子一开始想的有点类似于基数了就是比如说chinese占了22%American占了 5%那我搞一个 100 个人的数组前 22 个元素 代表 chinese 23 28 个元素代表 american。然后 1 100 内随机一个随机数求得。然后面试官反问如果占比不是整数呢比如 22.345676798878888%这种那是不是要开一个巨大的数组存这些数。于是这个思路走进死胡同了。群里有小伙伴说如果有个 0 1 的随机数发生器就好了。我们可以这么思考就是我们把概率数组求前缀和然后随机一个 0 1 的数在前缀和数组中二分这个数字就可以了。 题解前缀和 二分。 转载于:https://www.cnblogs.com/zhangwanying/p/10199941.html
相关文章：
