登录
  • #美国面经
  • #码农类general
  • #面试经验
  • #google

Google onsite 3/25

xiaoniqiuqiu
7799
37
Google onsite 面经今天刚面的,热乎乎的面经回馈地里的兄弟姐妹~第一轮 一个说话不太听得懂的外国小哥(非美国人)贪食蛇 就是手机里面的那个贪食蛇,不能出手机屏幕,头部不能吃到身体的任何部分,出了尾巴, 因为头部移过去的时候尾巴会移走,所以不会吃到输入:List of moves: [U, U, D, L, D, R….] U: up, D: down, L: left, R : right 移动的方向,有限长度的listList of food: [(x1, y1), (x2, y2), (x3, y3)….] 食物的位置,有限长度的listint: width 宽度 (屏幕宽度)int: height 高度 (屏幕高度)开始的时候,蛇在(0,0)的位置

本帖隐藏的内容需要积分高于 188 才可浏览,点击前往一亩三分地论坛阅读

朋友讨论,还是用queue+hashset比较好。每一步,如果出了边界,或者蛇下一步的头碰到了身体里除了尾巴的别的部分,游戏就结束了。

补充内容 (2016-3-26 16:12):

如果下一步是valid的,有两种情况:1)蛇头到了食物的位置,则linkedlist和set里加上新的蛇投头的位置,蛇尾巴的位置不变。2)蛇没吃到食物,则除了加上新的舌头,尾巴也会往前移一步,即之前的尾巴的位置就不是蛇

补充内容 (2016-3-26 16:13):

的身体的一部分了,要从linkedlist里面和set里面删除掉。

补充内容 (2016-3-26 16:18):

为什么要用linkedlist+set的原因是,检查下一步的蛇头的位置是不是已经身体的一部分的时候,set可以O(1)做到,但是set不知道尾巴是哪一个;然后要删除尾巴的时候,可以从linklist拿到尾巴,从list和set删掉尾巴
37条回复
热度排序

发表回复