镜面反射
难度:
标签:
题目描述
有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。
正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。
返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。
示例 1：
输入：p = 2, q = 1 输出：2 解释：这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。
示例 2：
输入：p = 3, q = 1 输入：1
提示：
1 <= q <= p <= 1000
代码结果
运行时间: 21 ms, 内存: 16.2 MB
/*
* 思路：
* 1. 使用流式计算来简化最小公倍数（LCM）的计算。
* 2. 利用java.util.stream.IntStream来求解。
*/
import java.util.stream.IntStream;
public class Solution {
public int mirrorReflection(int p, int q) {
int lcm = IntStream.iterate(1, i -> i + 1)
.map(i -> p * i)
.filter(x -> x % q == 0)
.findFirst()
.getAsInt();
int k = lcm / q;
if ((lcm / p) % 2 == 0) {
return 0;
} else if (k % 2 == 1) {
return 1;
} else {
return 2;
}
}
}解释
方法:
题解使用了模拟的思路。我们可以假设没有北面的墙壁，无限延长东西两面镜子的长度，光线会通过东西两面镜子的反射一直往北走，每次增加的纵向距离为 q。当光线走过的纵向距离为 p 的整数倍时，光线到达某个接收器。题解中使用了 left 和 upward 两个布尔变量分别表示光线当前是向左运动还是向右运动，以及是向上运动还是向下运动。通过模拟光线的运动过程，当光线到达北面或南面的墙壁时，根据光线的运动方向和位置来判断遇到了哪个接收器。
时间复杂度:
O(p)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在模拟过程中，光线的方向变化只与其当前的位置有关，而不考虑其之前的路径或是反射次数？
▷🦆
在题解中，当光线的纵坐标y超出北面墙壁时，为什么将y对p取余，并改变光线的向上运动状态？这样的处理是否与物理反射原理相符？
▷🦆
题解中提到当y等于p时，根据光线的运动方向判断遇到的接收器。如果光线刚好在角落处反射，是否会存在不确定性，即同时可能遇到两个接收器？
▷🦆
题解假设了一个无限延长的东西墙，这种假设在实际的数学或物理模型中是如何合理化的？
▷