Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 剩我不會寫hard了
: 狗屎爛leetcode
: 502. IPO
: 給兩個矩陣profits、capital
: w為目前的資本額
: 當w>=capital[i]時
: 可以將profits[i]加入資本額中
: 上述的操作可以做k次
: 請回傳最大的資本額w
: 思路:
: 建立一個n*2的矩陣rec
: rec[i][0]=profits[i]
: rec[i][1]=capital[i]
: 將rec依照capital的大小排序
: 接著用迴圈進行k次操作
: 將符合w>=rec[i][1]的元素放進maxheap中
: 並把profit最大的元素拿出來，並且w+=profit
: 當maxheap裡沒有任何元素時跳出
: 這樣就可以得到答案了
: golang code :
: type h []int
: func (this h) Len() int           { return len(this) }
: func (this h) Less(i, j int) bool { return this[i] > this[j] }
: func (this h) Swap(i, j int)      { this[i], this[j] = this[j], this[i] }
: func (this *h) Pop() interface{} {
:         n := len(*this)
:         res := (*this)[n-1]
:         (*this) = (*this)[:n-1]
:         return res
: }
: func (this *h) Push(x interface{}) {
:         (*this) = append(*this, x.(int))
: }
: func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
:         var maxheap h
:         n, idx := len(profits), 0
:         rec := make([][2]int, n)
:         for i := 0; i < n; i++ {
:                 rec[i][0] = profits[i]
:                 rec[i][1] = capital[i]
:         }
:         slices.SortFunc(rec, func(i, j [2]int) int {
:                 return i[1] - j[1]
:         })
:         for i := 0; i < k; i++ {
:                 for idx < n && rec[idx][1] <= w {
:                         heap.Push(&maxheap, rec[idx][0])
:                         idx++
:                 }
:         if maxheap.Len()<1{
:             break
:         }
:                 w += heap.Pop(&maxheap).(int)
:         }
:         return w
: }


本來思路:
max_heap 每次重新把東西丟進去 結果炸了

Python Code:
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int],
capital: List[int]) -> int:
        if k > len(profits):
            k = len(profits)
        max_heap,flag = [],-1
        while k > 0:

            for i in range(len(capital)):
                if w >= capital[i]:
                    if (profits[i]*flag,i) not in max_heap:
                        heapq.heappush(max_heap,(profits[i]*flag,i))


            if max_heap:
                x = heapq.heappop(max_heap)
                w += x[0] * flag
                profits.pop(x[1])
                capital.pop(x[1])
            k -= 1


        return w


更新思路:
一樣max_heap 但只遍歷一次

Python Code:
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int],
capital: List[int]) -> int:
        n = len(profits)
        project = sorted([(capital[i], profits[i]) for i in range(n)])
        max_heap = []
        cur = 0
        flag = -1

        for i in range(k):
            while cur < n and project[cur][0] <= w:
                heapq.heappush(max_heap,project[cur][1]*flag)
                cur += 1

            if max_heap:
                w += heapq.heappop(max_heap) * flag

        return w


沒那麼狗屎的hard

至少我硬幹出來了


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.180.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718465576.A.F17.html
推 JIWP: 大師
→ Rushia: 早上要刷 晚上也要刷 別卷了
→ sustainer123: 我們不是約好要一輩子一起刷題嗎