Re: [閒聊] 每日LeetCode
1814. Count Nice Pairs in an Array
給你一串陣列
陣列裡面都是正整數
然後有一個顛倒數rev
例如123的顛倒數rev(123)是321
120的顛倒數rev(120)是21
有兩個數a,b
如果rev(a) + b = a + rev(b)
則a與b則可以配成一對
求陣列內的數可能配對的數量
Intuition:
這一題我原本想的思路是錯的
寫半天解決了大部分的case之後有少數case沒辦法找出來
Approach:
我們透過交換率可以知道
rev(a) + b = a + rev(b) => a - rev(a) = b - rev(b)
所以只要兩個數
他們和自己的顛倒數差相等就可以配一對
我們只要用map把所有顛倒數差相等的放一起
然後Cn取2就後累加就能得到答案
TS Code:
const mod = 1000000007
function getReverse (num: number): number {
const n = num
let reverse = 0
while (num > 0) {
reverse *= 10
reverse += num % 10
num = Math.floor(num / 10)
}
return reverse
}
function countNicePairs (nums: number[]): number {
const diffMap = new Map<number, number>()
for (let i = 0; i < nums.length; i++) {
const diff = getReverse(nums[i]) - nums[i]
diffMap.set(diff, (diffMap.get(diff) ?? 0) + 1)
}
let result = 0
for (const value of diffMap.values()) {
result = (result + value * (value - 1) / 2) % mod
}
return result
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700536865.A.FC8.html
推
11/21 11:28,
2年前
, 1F
11/21 11:28, 1F
※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/21/2023 11:30:00
推
11/21 11:35,
2年前
, 2F
11/21 11:35, 2F
→
11/21 11:39,
2年前
, 3F
11/21 11:39, 3F
討論串 (同標題文章)
完整討論串 (本文為第 531 之 719 篇)：