面試刷題:鍾針之間的角度 | 第79期

很多的問題看起來很難,並不是因為需要很複雜的技巧和經驗,而是因為情況比較多。

如果能夠靜下心來把情況分清楚,就像中學數學中常做的對參數分情況討論一樣。情況也不是隨便劃分的,常常有一些數學關係天然地劃分了各種情況。Leetcode Q1344的鐘針夾角問題就可以說明這一點,因此,事實上,這是一道中學生,甚至小學生就能做出來的題目。不過,從編程的角度看,除了分情況,我們還需要適度的合併一些情況,因為這樣才能讓代碼更加簡潔高效。

1 題目 Q1344 鍾針夾角

給定兩個數字,hour 和 minutes。返回時針和分針之間形成的較小角度(以60進制單位)。

約束條件:

<code>(a) 1 <= hour <= 12
(b) 0 <= minutes <= 59
(c) 實際值的 10^-5 以內的答案將被認為是正確的。/<code>

關於這個問題,我們可以使用下圖來進行更加清晰地說明:

面試刷題:鍾針之間的角度 | 第79期

鍾針夾角問題說明圖

有幾個常識需要說明一下:

鍾針轉一圈是360度

分鐘轉一圈是60分鐘,時針轉一圈是12小時

一分鐘的時間分針轉動6度,時針轉動30/60=0.5度

一小時時針轉動30度

一些具體的例子可能更能說明一些具體的問題,下面就展示3個例子的圖示:

面試刷題:鍾針之間的角度 | 第79期

三個示例的示意圖

2 求解思路

對於給定時間 h 小時 m分鐘,根據問題中的常識,假設0點對應的角度為0度,則我們可以計算出時針和分針的角度:

Dh = 30m/60 + 30h

Dm = 6m

那麼就會有兩種很明顯的情況存在,即 Dm > Dh 和 Dm < Dh 。具體演示如圖:

面試刷題:鍾針之間的角度 | 第79期

分針角度大於和小於時針角度的情況

這兩種情況下,計算夾角時的公式如圖所示,但是可以使用絕對值運算簡化成一個公式:

D = |Dh - Dm|

從以上公式可以看出,夾角 D 的數值範圍是 [0, 360),這與題目中的較小角要求不符,因此,關於這個角度是不是較小角,即 D < 180 和 D > 180 能劃分成兩種個情況。第一種夾角的情況上面已經討論,接下來就看看第二種夾角的情況示意圖。

面試刷題:鍾針之間的角度 | 第79期

計算出的夾角大於180度情況示意圖

從以上示意圖和夾角小於180的情況可以知道,在夾角大於180的情況下,角度為

D = 360 - |Dh - Dm|

到此,這個問題的求解思路就理清楚了。

3 C++解決方案

根據以上思路實現一個解決方案當然是非常容易的,不過,如果對於這四種情況逐個去實現就未免太笨拙。以下給出一種合併的實現方案。

面試刷題:鍾針之間的角度 | 第79期

這個實現中需要注意整數與浮點數的計算規則,在計算時針角度時,使用 來做浮點數運算,避免整數運算造成的精度損失。時間複雜度是 O(1)。

----------------------

題外:

頻道資源,可以私信關鍵字獲取。

Python編程問題諮詢,請發送關鍵字【諮詢】

獲取leetcode源代碼,請發送關鍵字【leetcode】

獲取書籍,請發送關鍵字【書籍】


分享到:


相關文章: