前往
大廳
主題

LeetCode - 816. Ambiguous Coordinates 解題心得

Not In My Back Yard | 2021-06-05 00:00:05 | 巴幣 0 | 人氣 204

題目連結:


題目意譯:
我們有一些二維座標,像是 "(1, 3)" 或是 "(2, 0.5)"。然後,我們將所有的逗號、小數點以及空白移除,最終得到了字串 s。回傳所有可能的座標之字串表示法之列表。

我們的原始表示法絕對不會有多餘的 0 ,所以我們不會開始於數字像是 "00" 、 "0.0" 、 "0.00" 、 "1.0" 、 "001" 、 "00.01" 或是其他可以用更少的位數表示的數字。

最終答案可以任意順序回傳。注意到,所有最終答案中的最標都會有恰好一個空白(出現於逗號之後)。

注:
4 ≦ s.length ≦ 12.
s[0] = "(" 、 s[s.length - 1] = ")" 且其他 s 中元素為數字。



範例測資:
範例 1:
輸入: s = "(123)"
輸出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

範例 2:
輸入: s = "(00011)"
輸出: ["(0.001, 1)", "(0, 0.011)"]
解釋: 0.0 、 00 、 0001 或是 00.01 都不被允許。

範例 3:
輸入: s = "(0123)"
輸出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

範例 4:
輸入: s = "(100)"
輸出: [(10, 0)]
解釋: 1.0 不被允許。


解題思維:
以 s = "(00011)" 為例,只考慮 "00011" (也就是忽略左右的小括號),我們可以直接地切出以下數對:
0, 0011
00, 011
000, 11
0001, 1

接著對於每個數對 X, Y 我們窮舉 X 、 Y 各自的小數點擺放之可能。例如數對 00, 011 有以下可能:
00, 011
00, 01.1
00, 0.11
0.0, 011
0.0, 01.1
0.0, 0.11
然後對每個可能性去檢查左右兩邊的數字有無符合以下規則:
如果該數字沒有數字出現小數點「.」,則檢查其值是否為 0 。如果是,且如果長度超過 1 個字元(即代表有多餘的 0)則代表該數字不合法;如果值不是 0 ,且如果開頭為 0 ,則該數字也不合法。

如果該數字有小數點出現,則以小數點為界再分為左右兩邊。對於左邊的數字套用上面沒有出現小數點之數字判斷規則。而右邊的數字則檢查是否以 0 結尾,如果是則不合法。

所以可以看到
00, 011
00, 01.1
00, 0.11
0.0, 011
0.0, 01.1
0.0, 0.11
這些數組都不合法。

考慮進其他數對,即 0, 0011000, 110001, 1 ,我們最終只會獲得
(0.001, 1)(0, 0.011)
這兩個合法的數組。

而其他的字串 s 之情形,也是按照以上想法即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作