Leetcode 858 Mirror Reflection

发表于 |

题目描述

这道题超有意思！

分析：

  1. 我们首先需要知道镜面反射的一些小技巧，如下图，也就是我们可以作延长线来判断反射之后的线将会落于何处。
    示例图1
  2. 题目既然保证一定会碰到012中的某一个点，那么我只要疯狂做延长线，总会交于某个角
  3. 再来举个例子，如下图，p = 4,q = 3，最后落于点2处,图中虚线和实线根据标号一一对应，且保证了两线方向一致
    示例图2
  4. 延长线每次交于边界点记作A,B,C,…,显然若A的横坐标为x，则B的横坐标为2x，C的横坐标为3x，依次类推，我们只需要找到某个点其横坐标恰好是p的倍数即可

思路：

  1. 显然若横坐标是x的偶数倍，说明相交点在下边界线，也就是0处！返回0即可
  2. 若横坐标是x的奇数倍，说明相交点在上边界线，或许是2，或许是1
  3. 那么显然，此时若横坐标是p的偶数倍，如示例1和示例2，最后会落于2处！
  4. else: 落于1处！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def mirrorReflection(self, p, q):
        """
        :type p: int
        :type q: int
        :rtype: int
        """
        # 先找到第一个横坐标为p的倍数的点
        k = 1
        while p*k % q != 0: k += 1
        # 若为x的偶数倍
        if k  % 2 == 0: return 0
        else:
        	# 分别判断p的奇数倍和偶数倍
            r = p*k / q
            if r % 2 == 1: return 1
            if r % 2 == 0: return 2


69 / 69 test cases passed.
diffculty: medium
Runtime: 30 ms