N: 牌數 , M: 相異數字個數, E:邊數。 |
暴力判斷: O(2N・N) |
把正面反面視為01, 用 2N 種 01 bit 來決定拿正面或反面,同時紀錄有沒有拿過。 |
回溯法: O(2N) |
窮舉拿正面或反面。用 vis 維護有沒有拿過這張數字。 |
接下來的思路,基本上是將問題轉化成圖論的問題。
二分匹配: O(N • E) |
將卡牌正反面數字與卡牌編號建邊,從牌面數字大的到小的來二分匹配,如果當前卡牌編號沒有匹配過,就匹配,否則考慮被匹配的數字(一定比較大)有沒有其他牌同樣有這個被匹配的數字。
時間複雜度最壞應該是 1+2+3 + ...+ N ? |
剩下的兩個方法想法類似:
把卡牌的數字(a, b)可以當作一條邊,而我們希望集合和最大那就是從大的數字開始選。
當這些邊都建完後會發現一件事,當有連通的數字的數量有等於或超過的邊數時,我們可以全拿,但是如果少一條邊(一定是N-1條邊, 樹),我們會少拿一個,讓少拿的最小就好。
問題簡化成建邊 then 找環or樹。
BFS/DFS: O(N+M+E ) 。 |
用到的想法就是點數和邊數的關係,建邊(a, b)和(b, a)並爆搜所有連通塊,同時計數 or 判環即可。 |
並查集: O( Nㆍα(N) + M ) ,約為O(N)。 |
把每張數字初始不同集合,每次把數字(a, b) union, 如果已經在同個set 代表有環了, merge的過程需要維護卡牌數量和circle有無,最後從大數到小數檢查,有環就加,無環就扣數量,同個set的最後一張牌不要算。 |
109 的牌面數字 要用離散化處理 !!