检查是否存在一个圆圈 [英] Check If there exists a Circle
问题描述
我在 Google 面试时被问到这个问题.我们得到一个由字母 F、L、R 组成的字符串.- 这是机器人遵循的指令
I was asked this during a Google Interview. We are given a string consisting of letters- F,L,R. - which is the instruction a robot follows
F-向前一步.
左转.
R-右转.
字符串长度最多可达 2500 个字符.
String length can be upto 2500 characters.
字符串无限次运行.我们需要判断是否存在一个半径为 r(r 可以是任何实数)的圆，这样机器人就不会离开这个圆.我被困在这一点上.我想过使用凸包，但是如何无限次检查它.将不胜感激.请帮忙.提前致谢
The string runs itself infinite times. We need to tell if there exists a circle with a radius, r( r can be any real number), such that the robot never leaves the circle. I was stuck at this point.I thought of using convex hull, but how to check it for infinite times.Explanation with code will be appreciated. Please help. Thanks in advance
推荐答案
- 每次运行(一次运行是执行给定字符串的所有命令一次)会改变两件事:机器人看向的方向和它的位置(也就是说，每次运行都会将它移动一个向量(这个向量的方向取决于在运行前的初始方向上)并旋转它).
可能的方向数为 4.因此，在运行模拟 4 次后，它看起来与最初的方向相同(每次摩擦旋转相同的角度).
- Each run(one run is executing all commands of the given string once) changes two things: the direction which the robot looks to and its position(that is, each run shifts it by some vector(the direction of this vector depends on the its initial direction before the run) and rotates it).
The number of possible directions is 4. Thus, after running the simulation 4 times it looks in the same direction as it did initially(each rub rotates it by the same angle).
这就是为什么连续 4 次运行只是将其移动某个向量而不进行任何旋转.
That's why 4 consecutive runs just shift it by some vector without any rotation.
因此，我们可以连续运行 4 次模拟，看看它是否在原点停止.如果是这样，我们可以找到包含其路径的最小圆.否则，不存在这样的圈子.
Thus, we can just run the simulation 4 times in a row and see if it stopped in the original point. If it did, we can find the minimum circle that contains its path. Otherwise, no such circle exists.
这篇关于检查是否存在一个圆圈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
