858. 镜面反射
有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。
正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。
返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。
示例：
输入： p = 2, q = 1 输出： 2 解释： 这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。
提示：
1 <= p <= 10000 <= q <= p原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2022-12-09 16:13:30
class Solution(object):
def mirrorReflection(self, p, q):
# 只要确保分子分母不都是偶数就行了
while((q&1) == 0 and (p&1) == 0):
q >>= 1
p >>= 1
# p 为偶数
if((p&1) == 0):
return 2
# q 为偶数
if((q&1) == 0):
return 0
# p, q 都是奇数
return 1
python3 解法, 执行用时: 40 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-09 16:12:39
class Solution(object):
def mirrorReflection(self, p, q):
from math import gcd
g = gcd(p, q)
p = (p / g) % 2
q = (q / g) % 2
return 1 if p and q else 0 if p else 2
java 解法, 执行用时: 0 ms, 内存消耗: 38.3 MB, 提交时间: 2022-12-09 16:10:41
class Solution {
public int mirrorReflection(int p, int q) {
int g = gcd(p, q);
p /= g; p %= 2;
q /= g; q %= 2;
if (p == 1 && q == 1) return 1;
return p == 1 ? 0 : 2;
}
public int gcd(int a, int b) {
if (a == 0) return b;
return gcd(b % a, a);
}
}
java 解法, 执行用时: 4 ms, 内存消耗: 38.2 MB, 提交时间: 2022-12-09 16:10:29
class Solution {
double EPS = 1e-6;
public int mirrorReflection(int p, int q) {
double x = 0, y = 0;
double rx = p, ry = q;
// While it hasn't reached a receptor,...
while (!( close(x, p) && (close(y, 0) || close(y, p))
|| close(x, 0) && close (y, p) )) {
// Want smallest t so that some x + rx, y + ry is 0 or p
// x + rxt = 0, then t = -x/rx etc.
double t = 1e9;
if ((-x / rx) > EPS) t = Math.min(t, -x / rx);
if ((-y / ry) > EPS) t = Math.min(t, -y / ry);
if (((p-x) / rx) > EPS) t = Math.min(t, (p-x) / rx);
if (((p-y) / ry) > EPS) t = Math.min(t, (p-y) / ry);
x += rx * t;
y += ry * t;
if (close(x, p) || close(x, 0)) rx *= -1;
if (close(y, p) || close(y, 0)) ry *= -1;
}
if (close(x, p) && close(y, p)) return 1;
return close(x, p) ? 0 : 2;
}
public boolean close(double x, double y) {
return Math.abs(x - y) < EPS;
}
}
python3 解法, 执行用时: 372 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-09 16:10:17
'''
最初的光线可以看成是从 (x, y) = (0, 0) 发出，方向为 (rx, ry) = (p, q)。
这样我们就可以通过模拟的方法来找到光线会先碰到哪一面镜子，以及碰到镜子的哪一个位置。
随后，我们通过反射定律计算出新的光线方向。我们进行模拟，知道光线到达某一个接收器。
'''
class Solution(object):
def mirrorReflection(self, p, q):
from fractions import Fraction as F
x = y = 0
rx, ry = p, q
targets = [(p, 0), (p, p), (0, p)]
while (x, y) not in targets:
#Want smallest t so that some x + rx, y + ry is 0 or p
#x + rxt = 0, then t = -x/rx etc.
t = float('inf')
for v in [F(-x,rx), F(-y,ry), F(p-x,rx), F(p-y,ry)]:
if v > 0: t = min(t, v)
x += rx * t
y += ry * t
#update rx, ry
if x == p or x == 0: # bounced from east/west wall, so reflect on y axis
rx *= -1
if y == p or y == 0:
ry *= -1
return 1 if x==y==p else 0 if x==p else 2