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