@(LeetCode)
问题描述
在一个特殊的正方形房间内，四面墙上都有镜子。除了西南角，在其余的每个角落都有一个接收器，编号分别为 0，1，2。
墙的宽度为 p，一条射线从西南角射出，落在东边墙上，与接收器 0 的距离为 q 。
返回射线第一个遇到的接收器编号，且保证射线最终会遇到一个接收器。
栗子：
image.png
输入：p = 2, q = 1
输出：2
解释：射线最先遇到第二个接收器。
注意：
1 <= p <= 10000 <= q <= p
解题思路
我的解法
我的初始想法是通过计算射线在四面墙上来回反射的路线，确定其在落在墙上的距离。如果最终的距离为 q，则表示遇到了接收器。
这其实是一种挺麻烦的方法，但是一陷进去就无法自拔，思维固化了。满脑子都是在想怎么计算反射路线，老实讲，还是花了挺多时间的。
下面来介绍一下思路，从简单到复杂的情况说起。
假设将墙面标号如下，从南面墙开始编号为 0，逆时针方向墙面编号 +1。如图所示：
image.png
最简单的情况
假设射线沿逆时针方向反射，且会逐个经过每一面墙，也就是墙面顺序为 1-2-3-0-1-...。如下图所示：
image.png
当射线初始落在 1 号墙距离底部 q 处，如何计算下一次反射到 2 墙上的距离 x 呢？如下图所示：
image.png
由于反射角度是不变的，即比率r = p / q 是固定的。因此我们可以根据比率 r 来计算下一次反射的距离。假设 l 为反射角的一条边，其初始值为 l = p - q。
- 第一次反射到
2号墙，x = r * l，此时更新距离l = p - x。如下图所示。
image.png
- 第二次反射到
3号墙，x = l / r，此时更新距离l = p - x。
image.png
- 第三次反射到
0号墙，x = r * l，此时更新距离l = p - x。可按照上图自己画一下。 - 第四次反射到
1号墙，x = l / r，此时更新距离l = p - x。可按照上图自己画一下。 - ...，直至
x == p。
当射线在反射到某面墙上时， 计算出的 x 满足 x == p，则表示遇到了接收器。而接收器编号就是反射到当前墙的编号。
从上面的叙述中，我们可以发现 x 的计算方式在不同墙面上其实是不一样的。总结如下：
在
0/2号墙，x = r * l
在1/3号墙，x = l / r
更复杂的情况
有可能会出现反射落点不是在相邻的下一面墙，而是其对面墙的情况。如下图所示：
image.png
在这种情况下，计算出来的 x 会大于墙的长度 p，因此 l 的计算方式也发送了变化，即 l = x - p。如下图所示，绿色线段为 x，表示待求距离。
image.png
这时如果再次发生反射，则会往回反射，方向变为顺时针。在这种情况下，l 需更新为已求出的 x， l = x，即上图中绿色线段，而非 l = p - x，以继续计算下一个反射的距离 x。如下图所示：
image.png
当方向为顺时针时，在正常情况下，下一次反射的墙面编号为当前墙面编号 - 1。但也有可能出现下一次反射是对面墙的情况。如下图所示：
image.png
如果再次反射到对面墙，计算出的 x 仍然大于 p，那么下一次反射方向又会变化，变为逆时针。
因此，反射方向跟 x 值有关，概括如下：
- 当
x > p时，则会反转方向； - 当
x < p时，保持原方向不变。
同样的判断方式，当 x == p 时，表示遇到了接收器。但是接收器的编号需要区分反射方向，如下图所示：
- 如果是逆时针，则为当前墙面编号。
image.png
- 如果是顺时针，则为当前墙面编号
- 1。
image.png
以上就是按照实际反射路线来计算的思路。
具体代码
- 循环的条件为
x != p，即没有遇到接收器。 - 默认在每次循环中，下次反射的落点墙面都为下一个相邻的墙面，根据逆/顺时针方向计算。如果出现反射到对面墙的情况，则需再次计算一次，更新为下一个墙面。
- 注意浮点数是否相同的比较，不能直接用
==。发现这个问题还花了些时间，明明逻辑都是对的😆。
代码如下：
var mirrorReflection = function (p, q) {
if (p >= q) {
if (p === q) {
return 1
}
if (p === 2 * q) {
return 2
}
// 已知距离
let l = (p - q)
// 比率
let ratio = p / q
// 待求距离
let x = 0
// 当前墙面编号
let cur = 1
// 是否需要计算下一个墙面编号
let flag = true
// 1 - 逆时针，0 - 顺时针
let direction = 1
// 因为计算有小数点，比较浮点数大小
while (!isEqual(x, p)) {
// 计算下一个墙面编号
if (flag) {
// 逆时针
if (direction === 1) {
cur = (cur + 1) % 4
} else {
cur = (cur + 3) % 4
}
}
if (cur % 2 === 1) {
x = l / ratio
} else {
x = l * ratio
}
// 计算有小数点，比较浮点数大小
if (isEqual(x, p)) {
// 逆时针，当前墙面编号
if (direction === 1) {
cur = cur % 4
} else {
// 顺时针，当前墙面-1
cur = (cur + 3) % 4
}
break
} else {
if (x > p) {
l = x - p
// 因为此时反射到对面的墙，所以还需要再根据方向 +1 / -1
if (direction === 1) {
cur = (cur + 1) % 4
} else {
cur = (cur + 3) % 4
}
// 下次循环不需要计算墙面编号，因为已经计算过了
flag = false
// 如果超出，方向相反
direction = (direction + 1) % 2
} else if (x < p) {
// 在反射到对面墙时，l = x
if (!flag) {
l = x
} else {
l = p - x
}
flag = true
}
}
}
return cur
}
return 0
};
// 比较 x,y 浮点数是否相等
var isEqual = function (x, y) {
return Math.abs(x - y) < 1e-6
}
更简单的解法
上面的解法太复杂，一定不是这种类型题目的最优解。在讨论区翻了翻答案，解法不要太简洁。但由于没有理解其思想，很难明白，最后看了这篇文章才弄懂。
其主要思想是利用镜面原理：成像相反。将反射路径简化为直线路径来求解，思路清奇。
我们能直观的想到：一条射线在某个点经过镜面的落点， 与其直接穿过镜面（即为一条直线）的落点成像是相反的。
下面举几个栗子加深理解。
栗 1：
假设 p = 2, q = 1，则反射和直线的路线如下图所示。相当于向右扩展了一个房间，且成像相反，因此直线到达的右上角对应 2 号接收器。
image.png
栗 2：
假设 p = 3, q = 1，则反射和直线的路线如下图所示。相当于向右扩展了 2 个房间，成像相同，因此右上角接收器的编号为 1。
image.png
栗 3：
假设 p = 3, q = 2，则反射和直线的路线如下图所示。相当于向右扩展了 2 个房间，此时横向成像相同，向上扩展了 1 个房间，此时成像相反。因此，右上角接收器的编号为 0。
image.png
从上面的栗子可以看出，当在同一方向上经过不同个数的镜面时，成像是不一样的。
- 当有
1个镜面时，即有2个房间，是反向的； - 当有
2个镜面时，即有3个房间，则变为同向； - 当有
3个镜面时，即有4个房间，则变为反向； - ...，以此类推。
以上推论一句话总结如下：
当经过奇数个镜面时，即偶数个房间，最终结果为反向；
当经过偶数个镜面时，即奇数个房间，最终结果为同向。
我们想像一下，假设房间个数是可以无限叠加的，可以将反射路径简化为不断延伸的直线，再确定直线到达的右上角最终对应的成像编号。
而该直线需要满足如下条件：
- 一定落在房间右上角顶点， 即其
x、y值均为房间长度的倍数，且满足比率x / y = p / q。 - 满足
1的情况下，直线的距离最短。因为需要找到第一个遇到的接收器。
因此需要找到直线上的一个延伸点，满足上述条件。
而直线到达的接收器跟其经过几个镜面有关系。因此问题可进一步转化为：当射线以一条直线到达房间的右上角，横向和竖向需要叠加到多少个房间。
假设横向需要 m 个房间，纵向需要 n 个房间，根据条件 1，可推断出如下关系：
x = m * p
y = n * p
(m * p) / (n * p) = p / q => m / n = p / q
// 简化为：
m = p
n = q
由于需要满足条件 2，那么 m、n 越小越好。
鉴于 p、q 可能有公约数，所以需要将 p、q 除以其最大公约数来保证它们最小。
在知道 m、n 后，需同时考虑横向和竖向的镜面成像。根据上述镜面成像变化结论，则可推断出对应的接收器编号。
根据上面的栗子或者自行画图推导，可以得出如下结论：
- 当
m为奇数，n为偶数时，横向经过的镜面数为偶数，成像相同，纵向经过的镜面数为奇数，成像相反，则最终右上角成像为0。 - 当
m为奇数时，n为奇数时，横向成像相同，纵向成像相同，则最终右上角成像为1。 - 当
m为偶数，n为奇数时，横向成像相同，纵向成像相反，则最终右上角成像为2。 - 当
m为偶数，n为偶数时，这种情况不可能存在。因为其有公约数2，那么只能是上面的三种情况。
以上结论用代码表示为：
var mirrorReflection = function (p, q) {
// 最大公约数
const g = gcd(p, q)
// 使 m，n 最小
let m = p / g
let n = q / g
if (m % 2 === 1 && n % 2 === 1) {
return 1
}
if (m % 2 === 1) {
return 0
}
return 2
}
网友评论