Re: [閒聊] 每日leetcode

[DJYOMIYAHINA (通通打死)]

這題好像 水蠻深的 做法很多
自己是先用了個O(N^2) 先能過吧
直覺是想應該可以O(NlogN)啦
畢竟unique rating
隨便一個binary search方法應該都可以 但懶想
先去上班晚上再來看看其他人的寫法

我這應該就算brute force吧
大概就是
先init各rating後有多少rating是比他大的 全記下來
然後就forloop加加加加加
最後反過來再做一次 對ㄚ==


def numTeams(self, rating: List[int]) -> int:
    n = len(rating)
    def helper(rating):
        ushiros = defaultdict(list)
        for i in range(n):
            cnt_cur = 0
            for j in range(i, n):
                if rating[j] > rating[i]:
                    ushiros[rating[i]].append(rating[j])

        ans = 0
        for num in rating:
            for num2 in ushiros[num]:
                ans += len(ushiros[num2])

        return ans

    return helper(rating) + helper(rating[::-1])

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722213989.A.8FA.html
→ pchooooome: 怎麼一早就在卷
→ JIWP: 怎麼一早就在卷
→ JIWP: 用monotonic stack試看看
推 sustainer123: 怎麼一早就在卷
→ sustainer123: 我看標籤有dp
→ sustainer123: 這題我本來想說backtracking
推 smart0eddie: 我抄解答不知道抄幾天了