858. Mirror Reflection


题目

——镜面反射

There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 01, and 2.

The square room has walls of length p and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor.

Given the two integers p and q, return the number of the receptor that the ray meets first.

The test cases are guaranteed so that the ray will meet a receptor eventually.

Example 1:

Input: p = 2, q = 1
Output: 2
Explanation: The ray meets receptor 2 the first time it gets reflected back to the left wall.

Example 2:

Input: p = 3, q = 1
Output: 1

Constraints:

  • 1 <= q <= p <= 1000

思路

题目大意是说镜面正方形房间,光线从左下角出发,求最终会射入哪个角。

又是一道被踩爆的题,主要是因为这题太物理了。

思路如下,一图胜千言。

补充下要点

1.反射相当于房间镜像&光线直接延长。

2.m = p / gcd(p, q), n = m * q // p

代码

class Solution(object):
    def mirrorReflection(self, p, q):

        def gcd(a, b):
            if a < b:
                return gcd(b, a)
            if b == 0:
                return a
            return gcd(b, a % b)

        m = p // gcd(p, q)
        n = m * q // p

        if n % 2 == 0:
            return 0
        else:
            return 1 if m % 2 == 1 else 2
        
        

AC,收工!



——此处是内容的分割线——

除非注明,否则均为广陌原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.utopiafar.com/2022/08/04/leetcdoe-858-mirror-reflection/

码字不易,如果觉得内容有帮助,欢迎留言or点赞!


发表回复

您的电子邮箱地址不会被公开。