Re: [閒聊] 每日LeetCode

作者: AyuniD (アユニ.D)   2023-10-03 23:47:21
我的想法比較不一樣,偏數學一點:
由題目可以得知出現次數在兩次以下的不構成 Pair,
而兩次以上的情形,我們可以用排列組合中的組合去計算。
當某數出現 N 次時,其可能組成的 Pair 數為 C(N, 2)。
你可能會問說:可是這題有順序之分啊?怎麼不是用排列呢?
沒有錯,確實要考慮順序,
但其實在這題裡,當你在從 N 個出現位子中取 2 位出來時,也順便幫他們排列好了,意即:
取出 i 與 j,其中 i 與 j 分別代表出現的位子
那他們的排列要嘛是 i, j,要嘛是 j, i
而我們只需要其中一種,所以其實就是組合
Code:
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
c = Counter(nums)
result = 0
for times in c.values():
if times >= 2:
result += math.comb(times, 2)
return result
Note:
其實可以利用 math.comb 的特性 (math.comb(k, n) = 0 for n > k) 去省略掉判斷 times 是不是大於 2
然後其實可以塞成一行 XD
return sum(math.comb(times, 2) for times in collections.Counter(nums).values())
※ 引述《yam276 (史萊哲林的優等生)》之銘言:
: ※ 引述《Rushia (みけねこ的鼻屎)》之銘言:
: : 1512. Number of Good Pairs
: : 給你一個整數陣列 nums,如果 nums[i] == nums[j] 且 i < j 則 (i, j) 是一個
: : Pair,求出 nums 共有幾個 Pair。
: : 思路:
: : 1.用一個 map 記錄之前出現過的數字數量,因為 nums[i] 介於 0 到 100 所以用
: : int[101]。
: : 2.每一輪可以產生的 Pair 為累計先前出現過的數量,把每一輪的結果加總即可。
: 思路:
: 跟這個差不多
: 主要是每次出現新數字就會多N個組合所以邏輯是result+=count;
: count+=1;
: 以及學到快速使用HashMap:
: *nums_map.entry(num).or_insert(0) += 1;
: .entry(num) : 尋找key(num)-value是存在
: .or_insert(0) : key(num)-value存在
: 就會給你value的可變引用並進行後面操作(+=1)
: key(num)-value不存在
: 則會用初始值(0)建立一對key(num)-value
: 並給你value的可變引用
: 再用這個可變引用做後面操作(+=1)
: Code:
: use std::collections::HashMap;
: impl Solution {
: pub fn num_identical_pairs(nums: Vec<i32>) -> i32 {
: let mut nums_map = HashMap::new();
: let mut result = 0;
: for num in &nums {
: match nums_map.get(num) {
: Some(count) => {
: result += count;
: }
: None => {}
: }
: *nums_map.entry(num).or_insert(0) += 1;
: }
: result
: }
: }
作者: yam276 ('_')   2023-10-03 23:52:00
我的想法是從頭往尾跑 只要碰到可以成隊的 前面有幾個就加幾次 這樣順著跑還不用考慮排列啥的
作者: wu10200512 (廷廷)   2023-10-04 00:50:00
你是誰

Links booklink

Contact Us: admin [ a t ] ucptt.com