Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《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])

思路:
看解答 姆咪

這思路也是暴力解 晚點看一下有沒有其他方法




Python Code:
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        asc = dsc = 0
        for i, v in enumerate(rating):
            llc = lgc = rlc = rgc = 0
            for l in rating[:i]:
                if l > v:
                    lgc += 1
                elif l < v:
                    llc += 1

            for r in rating[i+1:]:
                if r > v:
                    rgc += 1
                elif r < v:
                    rlc += 1
            asc += llc * rgc
            dsc += lgc * rlc

        return asc + dsc



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.0.156 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722217613.A.0DD.html
推 JIWP: 剩我只會寫n^3