※ 引述《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
至少我硬幹出來了