題目

  • 題目連結
  • 目標函式 : countBeautifulPairs(nums)
    • Input : nums: List[int]
    • Output : int

解題概念

  • 題意 : 給予一 0-indexed 陣列 nums，若存在 a pair of indices i, j (0 <= i < j < nums.length)，其中 nums[i] 的 first digit 與 nums[j] 的 last digit 互質，則稱 i, j 為 Beautiful pairs。
  • 題目希望找出 nums 中 Beautiful pairs 的總數

我的寫法

  • 想法 :
    1. 使用雙層 for 迴圈去閱覽所有的 pairs of i, j
    2. 找出 nums[i] 的 first digit 與 nums[j] 的 last digit
    3. 寫一個 gcd() function 去判斷兩個數字是否互質
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    def gcd(self, a, b):
        if b > a:
            a, b = b, a
        while b != 0:
            r = a % b
            a = b
            b = r
        return a
        
    # find first digit of i
    def getFirstDigit(self, i):
        r = 0
        while i!= 0:
            r = i % 10
            i = i // 10
        return r

    # Main Function
    def countBeautifulPairs(self, nums):
        cnt = 0 
        # Step 1 : double loop 
        for i in range(0, len(nums)-1):
            for j in range(i+1, len(nums)):
                # Step 2 : find first digit of nums[i]
                f = self.getFirstDigit(nums[i])
                # Step 3 : find last digit of nums[j] 
                l = nums[j] % 10
                # Step 4 : use gcd()
                if self.gcd(f, l) == 1:
                    cnt += 1
        return cnt
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n^2)}$

解答 or 其他優秀寫法

  • 想法 :
    1. 先將 所有 first/last digit 全部抓出來，並用成 frst 與 last 兩個陣列
    2. 然後利用兩層 for 迴圈去計算 frst[i] 與 last[i] 是否互質
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def countBeautifulPairs(self, nums):

        ans = 0
        # 使用 lambda 去快速計算 frst 與 last 兩個陣列
        ## 將 nums[i] 轉成 str 挑出第一個字元，再轉回 int
        frst = list(map(lambda x: int(str(x)[0]), nums))
        ## 直接將 nums[i] % 10
        last = list(map(lambda x: x %10, nums))

        # 使用雙重迴圈 & enumerate
        for i,n1 in enumerate(frst):
            for n2 in last[i+1:]: 
                ans += (gcd(n1, n2) == 1)

        return ans
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n^2)}$