ETH官方钱包

前往
大廳
主題

LeetCode - 2748. Number of Beautiful Pairs 解題心得

Not In My Back Yard | 2024-09-16 12:00:04 | 巴幣 0 | 人氣 20

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的整數陣列 nums。一對索引值 i 、 j,其中 0 ≦ i < j < nums.length,如果滿足 nums[i] 的第一個位數與 nums[j] 的最後一個位數互質,則該數對為「美麗的」。

回傳 nums 中美麗的數對之總數。

兩整數 x 和 y 互質,代表著沒有大於 1 的整數可以同時整除它們兩者。換句話說,x 和 y 互質,代表著 gcd(x, y) == 1,其中 gcd(x, y) 為 x 和 y 兩者的最大公因數。

限制:
2 ≦ nums.length ≦ 100
1 ≦ nums[i] ≦ 9999
nums[i] % 10 != 0



範例測資:
範例 1:
輸入: nums = [2,5,1,4]
輸出: 5
解釋: nums 中 5 個美麗數對:
當 i = 0 且 j = 1 時:nums[0] 的第一個位數為 2,而 nums[1] 的最後一位數為 5。我們可以確認 2 和 5 是互質的,因為 gcd(2,5) == 1。
當 i = 0 且 j = 2 時:nums[0] 的第一個位數為 2,而 nums[2] 的最後一位數為 1。而的確,gcd(2, 1) == 1。
當 i = 1 且 j = 2 時:nums[1] 的第一個位數為 5,而 nums[2] 的最後一位數為 1。而的確,gcd(5, 1) == 1。
當 i = 1 且 j = 3 時:nums[1] 的第一個位數為 5,而 nums[3] 的最後一位數為 4。而的確,gcd(5, 4) == 1。
當 i = 2 且 j = 3 時:nums[2] 的第一個位數為 1,而 nums[3] 的最後一位數為 4。而的確,gcd(1, 4) == 1。
因此我們回傳 5。

範例 2:
輸入: nums = [11,21,12]
輸出: 2
解釋: nums 中 2 個美麗數對:
當 i = 0 且 j = 1 時:nums[0] 的第一個位數為 1,而 nums[1] 的最後一位數為 1。而的確,gcd(1, 1) == 1。
當 i = 0 且 j = 2 時:nums[0] 的第一個位數為 1,而 nums[2] 的最後一位數為 2。而的確,gcd(1, 2) == 1。
因此我們回傳 2。


解題思維:
窮舉所有可能的數對(根據條件,最多不超過 100 * 99 ÷ 2 個)並按照題目敘述判斷有多少個符合條件即可。




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

創作回應

更多創作