跳转至

858. 镜面反射

题目描述

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。

正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。

返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。

 

示例 1：

输入：p = 2, q = 1
输出：2
解释：这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。

示例 2：

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

 

提示：

  • 1 <= q <= p <= 1000

解法

方法一：数学

思考

光线在正方形房间内反射，可展成网格上的直线，首次碰到的受体对应「横向奇数/偶数个房间、纵向奇数/偶数个房间」。

约去 \(p,q\) 的最大公因数后看二者奇偶：同奇则受体 \(1\)，横奇纵偶为 \(0\)，横偶纵奇为 \(2\)。

根据题意，光线在每次反射时，都会向上或向下移动 \(q\) 的距离，向右移动 \(p\) 的距离。而由于光线最后一定会遇到接收器，因此，我们需要找到一个最小的 \(k\)，使得 \(k \times q\) 是 \(p\) 的倍数。

同时，根据 \(k\) 的奇偶性，我们可以确定光线最终到达了西侧还是东侧。如果 \(k\) 是偶数，那么光线最终到达的是西侧，否则光线最终到达的是东侧。

另外，根据 \(k \times q\) 除以 \(p\) 的结果的奇偶性，我们可以确定光线最终到达的是北侧还是南侧。如果 \(k \times q\) 是 \(p\) 的偶数倍，那么光线最终到达的是南侧，否则光线最终到达的是北侧。

时间复杂度 \(O(\log p)\)，空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
8
class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        g = gcd(p, q)
        p = (p // g) % 2
        q = (q // g) % 2
        if p == 1 and q == 1:
            return 1
        return 0 if p == 1 else 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int mirrorReflection(int p, int q) {
        int g = gcd(p, q);
        p = (p / g) % 2;
        q = (q / g) % 2;
        if (p == 1 && q == 1) {
            return 1;
        }
        return p == 1 ? 0 : 2;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int mirrorReflection(int p, int q) {
        int g = __gcd(p, q);
        p = (p / g) % 2;
        q = (q / g) % 2;
        if (p == 1 && q == 1) {
            return 1;
        }
        return p == 1 ? 0 : 2;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func mirrorReflection(p int, q int) int {
    g := gcd(p, q)
    p = (p / g) % 2
    q = (q / g) % 2
    if p == 1 && q == 1 {
        return 1
    }
    if p == 1 {
        return 0
    }
    return 2
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function mirrorReflection(p: number, q: number): number {
    const g = gcd(p, q);
    p = Math.floor(p / g) % 2;
    q = Math.floor(q / g) % 2;
    if (p === 1 && q === 1) {
        return 1;
    }
    return p === 1 ? 0 : 2;
}

function gcd(a: number, b: number): number {
    return b === 0 ? a : gcd(b, a % b);
}

评论