iT邦幫忙

2

【小馬的LeetCode練功坊】858. Mirror Reflection (Medium)

參考題目: leetcode- 858. Mirror Reflection
題目: 有一個四面都是鏡子的正方形房間,
邊長為p,一開始從左下角發射光線,
x位移=p,y位移=q,
碰到牆時遵循入射角=反射角的原則,
試問最後光線會從幾號出口離開?
(右下角: 0、右上角: 1、左上角: 2)

圖示:
https://ithelp.ithome.com.tw/upload/images/20200505/20117114umBV3eC5m9.png

測資範圍:

  1. 1 <= p <= 1000
  2. 0 <= q <= p

解法一: 直接模擬光線的動向

一開始設定位置pos=[0,0]
光線走的方向direction = [p,q]
持續計算光線走到哪裡,
但缺點就是光線反射的過程中,
會出現很多小數點,
必須額外寫函數定義容許的誤差範圍

def close(x,y):
    return abs(x-y)<=10**(-5)

def closePos(pos1, pos2):
    return abs(pos1[0]-pos2[0])+abs(pos1[1]-pos2[1])<=10**(-5)

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        direction, pos = [p,q], [0,0]
        exits = [[p, 0], [p, p], [0,p]]
        # while迴圈,若現在位置還沒靠近出口,就繼續模擬光線走向
        while all(not closePos(pos, ex) for ex in exits):
            dir_x = p-pos[0] if direction[0]>0 else pos[0]
            dir_y = p-pos[1] if direction[1]>0 else pos[1]
            rate = min(dir_x/p, dir_y/q) # 看x,y哪個方向先撞牆
            pos[0] += direction[0] * rate
            pos[1] += direction[1] * rate
            # 撞牆就反向
            if close(pos[0],0) or close(pos[0],p):
                direction[0] *= -1
            if close(pos[1],0) or close(pos[1],p):
                direction[1] *= -1
                
        # 判斷離哪個出口近
        for i in range(3):
            if closePos(pos, exits[i]):
                return i

解法二: 優化模擬- 直接往上走到鏡中世界

這個想法蠻奇特的,
大概需要一些創造力,
如果照正常的模擬光線行走路徑,
那麼很快就是出現小數點而難免有誤差
https://ithelp.ithome.com.tw/upload/images/20200505/20117114EK98vEtAki.png

這個想法是我們只讓光線左、右反彈,
如果碰到上面的話直接繼續往上走,
想像直接把光線送進鏡中世界
如圖…

https://ithelp.ithome.com.tw/upload/images/20200505/201171140PRv8MfbRK.png

並且,鏡子往上的世界上可以一直延伸的,
第2,4,6,8個世界為鏡中世界
第1,3,5,7個世界因碰到下面的牆壁而回歸正常世界
https://ithelp.ithome.com.tw/upload/images/20200505/20117114LSPBUQK2IP.png

程式碼模擬變的相當簡單,pos固定每次加q
光線方向也只需要左右變動即可

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        direction, pos = "left", q #下一步往左走、位置=q
        while pos%p!=0:
            pos += q
            direction = "right" if direction=="left" else "left"
        if (pos//p)%2==1: #正常世界
            return 2 if direction=="right" else 1
        return 0 #鏡中世界

解法三: 省去模擬,直接判斷

解法三可謂非常的巧妙,
第一步將p, q除以它們的最大公因數,
原因是這樣只是把房間和光線等比例縮小,
光線離開的出口是相同的

再來,厲害的事情來了,
既然p, q互質了,於解法二的討論中,
可以很清楚看到光線會左右反射p次,
進入第q個世界,
因此,不必模擬即可判答案:

from math import gcd
class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        g = gcd(p, q)
        p, q = p//g, q//g
        if q%2==1: #正常世界
            return 2 if p%2==0 else 1
        return 0 #鏡中世界

尚未有邦友留言

立即登入留言