ETH官方钱包

前往
大廳
主題

[LeetCode]1814. Count Nice Pairs In an Array O(n^2) ~ O(n)

テリ君(桃夫模式) | 2023-11-21 20:37:08 | 巴幣 2 | 人氣 135

Medium difficulty.
原本搞了兩個函式,而且超沒效率是O(n^2)
跑出來是run time error怎麼想都不意外
class Solution:
    def countNicePairs(self, nums) -> int:
        def doTheRev(num):
            def rev(n, rn):
                if n > 0:
                    return rev((int)(n / 10), rn * 10 + (n % 10))
                else:
                    return rn

            return rev(num, 0)
        cnt = 0

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if doTheRev(nums[i]) + nums[j] == doTheRev(nums[j]) + nums[i]:
                        cnt += 1
        
        
        return cnt
後來先把rev數字直接叫出來(雖然會浪費掉一些空間,但效率高很多)
之後跑一次把diff算出來
在count_dict跑一次去把可以組合的量整合出來
回傳cnt
class Solution:
    def countNicePairs(self, nums) -> int:
        def reverse_number(num):
            return int(str(num)[::-1]) #make num from int to str and make it reverse then make it int back

        reversed_nums = [reverse_number(num) for num in nums] # firstly create a list of revsersed nums
        count_dict = {}

        for i in range(len(nums)):
            diff = reversed_nums[i] - nums[i] # get diff of each num
            count_dict[diff] = count_dict.get(diff, 0) + 1 # if diff is None, then = 0 or return the val
        cnt = 0
        for count in count_dict.values():
            cnt += count * (count - 1) // 2  # Calculate combinations

        return cnt % (10**9 + 7) #10^9+7, 10^9+9, 998244353 are all prime numbers, which can prevent integer overflow.
這樣比較快
註解有寫比較清楚
忘掉了還是可以回來看
不過沒查return為何要mod那個值還真的不知道為啥

創作回應

貓狗喵
其實你只要 loop 過 nums 一次,每次算出 diff 就把結果加上當前 diff 對應數量,再把對應數量+1。這樣就省掉 reversed_nums,最後也可以少 loop 一次 count_dict
2023-11-21 21:08:40
テリ君(桃夫模式)
等等來試試看
2023-11-21 22:21:11
貓狗喵
然後 10^9 + 7 是一個非常大的質數,又小於 2^31 - 1。大部分程式語言的整數是有範圍上限的,最基本的就是 4 byte 的 int,也就是 -2^31 ~ 2^31 - 1 這個範圍
2023-11-21 21:10:36
テリ君(桃夫模式)
度……搜了才在stack overflow看到,腦袋要長出來了
2023-11-21 22:21:37

更多創作