主題
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那個值還真的不知道為啥
