Medium

题目描述

有一个特殊的正方形房间，四面墙都是镜子。除了西南角，其他三个角都有接收器，编号分别为 0、1、2。

正方形房间的墙长为 p，激光从西南角发射，首先在距离第 0 号接收器 q 的距离处击中东墙。

给定两个整数 p 和 q，返回激光首先击中的接收器编号。

测试用例保证激光最终会击中某个接收器。

示例 1：

输入：p = 2, q = 1
输出：2
解释：激光第一次反射回左墙时击中接收器 2。

示例 2：

输入：p = 3, q = 1
输出：1

约束条件：

  • 1 <= q <= p <= 1000

解题思路

这道题可以通过数学几何的方法来解决。关键在于理解激光在镜面中的反射规律。

我们可以将问题转化为：激光在一个"展开"的房间中直线运动，直到击中某个接收器。通过镜面反射的性质，我们可以想象将房间在水平和垂直方向上无限复制，激光就在这个扩展的网格中直线运动。

核心思路：

  1. 激光从 (0,0) 出发，方向向量为 (p,q)
  2. 激光会在某个点 (mp, nq) 处击中接收器，其中 m 和 n 是正整数
  3. 为了使激光首次击中接收器，我们需要找到最小的 m 和 n，使得激光路径的终点在某个接收器位置

通过数学分析，可以得出：

  • 设 lcm = lcm(p,q) 为 p 和 q 的最小公倍数
  • m = lcm / p，n = lcm / q
  • 根据 m 和 n 的奇偶性来判断击中哪个接收器：
    • 如果 m 为偶数，n 为奇数：击中接收器 2
    • 如果 m 为奇数，n 为偶数：击中接收器 0
    • 如果 m 为奇数，n 为奇数：击中接收器 1

最优解法使用辗转相除法计算最大公约数，然后求最小公倍数。

代码实现

class Solution {
public:
    int mirrorReflection(int p, int q) {
        int gcd = __gcd(p, q);
        int m = p / gcd;
        int n = q / gcd;
        
        if (m % 2 == 0) return 2;
        if (n % 2 == 0) return 0;
        return 1;
    }
};

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        import math
        gcd = math.gcd(p, q)
        m = p // gcd
        n = q // gcd
        
        if m % 2 == 0:
            return 2
        if n % 2 == 0:
            return 0
        return 1

public class Solution {
    public int MirrorReflection(int p, int q) {
        int gcd = GCD(p, q);
        int m = p / gcd;
        int n = q / gcd;
        
        if (m % 2 == 0) return 2;
        if (n % 2 == 0) return 0;
        return 1;
    }
    
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

/**
 * @param {number} p
 * @param {number} q
 * @return {number}
 */
var mirrorReflection = function(p, q) {
    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
    
    const g = gcd(p, q);
    const pReduced = p / g;
    const qReduced = q / g;
    
    if (pReduced % 2 === 0) {
        return 2;
    } else if (qReduced % 2 === 0) {
        return 0;
    } else {
        return 1;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(log(min(p,q)))计算最大公约数的时间复杂度
空间复杂度O(1)只使用了常数级别的额外空间