feat: add solutions to lc problem: No.0502

yanglbme · yanglbme · commit 8d4fb9893724 · 2022-09-14T15:08:54.000+08:00
No.0502.IPO
diff --git a/solution/0400-0499/0496.Next Greater Element I/README.md b/solution/0400-0499/0496.Next Greater Element I/README.md
@@ -67,9 +67,9 @@ for i in range(n):
     stk.append(i)
 ```
 
-对于本题，先对将 $nums2$ 中的每一个元素，求出其下一个更大的元素。随后对于将这些答案放入哈希表 $m$ 中，再遍历数组 $nums1$，并直接找出答案。对于 $nums2$，可以使用单调栈来解决这个问题。
+对于本题，先对将 `nums2` 中的每一个元素，求出其下一个更大的元素。随后对于将这些答案放入哈希表 $m$ 中，再遍历数组 `nums1`，并直接找出答案。对于 `nums2`，可以使用单调栈来解决这个问题。
 
-时间复杂度 $O(M+N)$，其中 $M$ 表示 $nums1$ 的长度，$N$ 表示 $nums2$ 的长度。
+时间复杂度 $O(M+N)$，其中 $M$ 和 $N$ 分别为数组 `nums1` 和 `nums2` 的长度。
 
 <!-- tabs:start -->
 
diff --git a/solution/0400-0499/0498.Diagonal Traverse/README.md b/solution/0400-0499/0498.Diagonal Traverse/README.md
@@ -42,11 +42,11 @@
 
 **方法一：定点遍历**
 
-对于每一轮 $k$，我们固定从右上方开始往左下方遍历，得到 $t$。如果 $k$ 为偶数，再将 $t$ 逆序。然后将 $t$ 添加到结果数组 $ans$ 中。
+对于每一轮 $k$，我们固定从右上方开始往左下方遍历，得到 $t$。如果 $k$ 为偶数，再将 $t$ 逆序。然后将 $t$ 添加到结果数组 `ans` 中。
 
 问题的关键在于确定轮数以及每一轮的起始坐标点 $(i,j)$。
 
-时间复杂度 $O(m*n)$，其中 $m$ 表示 $mat$ 的行数，$n$ 表示 $mat$ 的列数。
+时间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。
 
 <!-- tabs:start -->
 
diff --git a/solution/0400-0499/0499.The Maze III/README.md b/solution/0400-0499/0499.The Maze III/README.md
@@ -70,7 +70,7 @@
 
 <!-- 这里可写通用的实现逻辑 -->
 
-BFS。
+**方法一：BFS**
 
 <!-- tabs:start -->
 
diff --git a/solution/0500-0599/0502.IPO/README.md b/solution/0500-0599/0502.IPO/README.md
@@ -56,22 +56,132 @@
 
 <!-- 这里可写通用的实现逻辑 -->
 
+**方法一：贪心 + 优先队列（双堆）**
+
+将每个项目放入优先队列 $q_1$ 中，按照启动资本从小到大排序。如果堆顶元素启动资本不超过当前已有的资金，则循环弹出，放入另一个优先队列 $q_2$ 中，按照纯利润从大到小排序。取出当前利润最大的项目，将其纯利润加入到当前资金中，重复上述操作 $k$ 次。
+
+时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。其中 $n$ 为项目数。
+
 <!-- tabs:start -->
 
 ### **Python3**
 
 <!-- 这里可写当前语言的特殊实现逻辑 -->
 
 ```python
-
+class Solution:
+    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
+        h1 = [(c, p) for c, p in zip(capital, profits)]
+        heapify(h1)
+        h2 = []
+        while k:
+            while h1 and h1[0][0] <= w:
+                heappush(h2, -heappop(h1)[1])
+            if not h2:
+                break
+            w -= heappop(h2)
+            k -= 1
+        return w
 ```
 
 ### **Java**
 
 <!-- 这里可写当前语言的特殊实现逻辑 -->
 
 ```java
+class Solution {
+    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
+        int n = capital.length;
+        PriorityQueue<int[]> q1 = new PriorityQueue<>((a, b) -> a[0] - b[0]);
+        for (int i = 0; i < n; ++i) {
+            q1.offer(new int[] {capital[i], profits[i]});
+        }
+        PriorityQueue<Integer> q2 = new PriorityQueue<>((a, b) -> b - a);
+        while (k-- > 0) {
+            while (!q1.isEmpty() && q1.peek()[0] <= w) {
+                q2.offer(q1.poll()[1]);
+            }
+            if (q2.isEmpty()) {
+                break;
+            }
+            w += q2.poll();
+        }
+        return w;
+    }
+}
+```
+
+### **C++**
+
+```cpp
+using pii = pair<int, int>;
+
+class Solution {
+public:
+    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
+        priority_queue<pii, vector<pii>, greater<pii>> q1;
+        int n = profits.size();
+        for (int i = 0; i < n; ++i) {
+            q1.push({capital[i], profits[i]});
+        }
+        priority_queue<int> q2;
+        while (k--) {
+            while (!q1.empty() && q1.top().first <= w) {
+                q2.push(q1.top().second);
+                q1.pop();
+            }
+            if (q2.empty()) {
+                break;
+            }
+            w += q2.top();
+            q2.pop();
+        }
+        return w;
+    }
+};
+```
 
+### **Go**
+
+```go
+func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
+	q1 := hp2{}
+	for i, c := range capital {
+		heap.Push(&q1, pair{c, profits[i]})
+	}
+	q2 := hp{}
+	for k > 0 {
+		for len(q1) > 0 && q1[0].c <= w {
+			heap.Push(&q2, heap.Pop(&q1).(pair).p)
+		}
+		if q2.Len() == 0 {
+			break
+		}
+		w += heap.Pop(&q2).(int)
+		k--
+	}
+	return w
+}
+
+type hp struct{ sort.IntSlice }
+
+func (h hp) Less(i, j int) bool  { return h.IntSlice[i] > h.IntSlice[j] }
+func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
+func (h *hp) Pop() interface{} {
+	a := h.IntSlice
+	v := a[len(a)-1]
+	h.IntSlice = a[:len(a)-1]
+	return v
+}
+
+type pair struct{ c, p int }
+type hp2 []pair
+
+func (h hp2) Len() int            { return len(h) }
+func (h hp2) Less(i, j int) bool  { return h[i].c < h[j].c }
+func (h hp2) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
+func (h *hp2) Push(v interface{}) { *h = append(*h, v.(pair)) }
+func (h *hp2) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
 ```
 
 ### **...**
diff --git a/solution/0500-0599/0502.IPO/README_EN.md b/solution/0500-0599/0502.IPO/README_EN.md
@@ -54,13 +54,117 @@ Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
 ### **Python3**
 
 ```python
-
+class Solution:
+    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
+        h1 = [(c, p) for c, p in zip(capital, profits)]
+        heapify(h1)
+        h2 = []
+        while k:
+            while h1 and h1[0][0] <= w:
+                heappush(h2, -heappop(h1)[1])
+            if not h2:
+                break
+            w -= heappop(h2)
+            k -= 1
+        return w
 ```
 
 ### **Java**
 
 ```java
+class Solution {
+    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
+        int n = capital.length;
+        PriorityQueue<int[]> q1 = new PriorityQueue<>((a, b) -> a[0] - b[0]);
+        for (int i = 0; i < n; ++i) {
+            q1.offer(new int[] {capital[i], profits[i]});
+        }
+        PriorityQueue<Integer> q2 = new PriorityQueue<>((a, b) -> b - a);
+        while (k-- > 0) {
+            while (!q1.isEmpty() && q1.peek()[0] <= w) {
+                q2.offer(q1.poll()[1]);
+            }
+            if (q2.isEmpty()) {
+                break;
+            }
+            w += q2.poll();
+        }
+        return w;
+    }
+}
+```
+
+### **C++**
+
+```cpp
+using pii = pair<int, int>;
+
+class Solution {
+public:
+    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
+        priority_queue<pii, vector<pii>, greater<pii>> q1;
+        int n = profits.size();
+        for (int i = 0; i < n; ++i) {
+            q1.push({capital[i], profits[i]});
+        }
+        priority_queue<int> q2;
+        while (k--) {
+            while (!q1.empty() && q1.top().first <= w) {
+                q2.push(q1.top().second);
+                q1.pop();
+            }
+            if (q2.empty()) {
+                break;
+            }
+            w += q2.top();
+            q2.pop();
+        }
+        return w;
+    }
+};
+```
 
+### **Go**
+
+```go
+func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
+	q1 := hp2{}
+	for i, c := range capital {
+		heap.Push(&q1, pair{c, profits[i]})
+	}
+	q2 := hp{}
+	for k > 0 {
+		for len(q1) > 0 && q1[0].c <= w {
+			heap.Push(&q2, heap.Pop(&q1).(pair).p)
+		}
+		if q2.Len() == 0 {
+			break
+		}
+		w += heap.Pop(&q2).(int)
+		k--
+	}
+	return w
+}
+
+type hp struct{ sort.IntSlice }
+
+func (h hp) Less(i, j int) bool  { return h.IntSlice[i] > h.IntSlice[j] }
+func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
+func (h *hp) Pop() interface{} {
+	a := h.IntSlice
+	v := a[len(a)-1]
+	h.IntSlice = a[:len(a)-1]
+	return v
+}
+
+type pair struct{ c, p int }
+type hp2 []pair
+
+func (h hp2) Len() int            { return len(h) }
+func (h hp2) Less(i, j int) bool  { return h[i].c < h[j].c }
+func (h hp2) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
+func (h *hp2) Push(v interface{}) { *h = append(*h, v.(pair)) }
+func (h *hp2) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
 ```
 
 ### **...**
diff --git a/solution/0500-0599/0502.IPO/Solution.cpp b/solution/0500-0599/0502.IPO/Solution.cpp
@@ -0,0 +1,25 @@
+using pii = pair<int, int>;
+
+class Solution {
+public:
+    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
+        priority_queue<pii, vector<pii>, greater<pii>> q1;
+        int n = profits.size();
+        for (int i = 0; i < n; ++i) {
+            q1.push({capital[i], profits[i]});
+        }
+        priority_queue<int> q2;
+        while (k--) {
+            while (!q1.empty() && q1.top().first <= w) {
+                q2.push(q1.top().second);
+                q1.pop();
+            }
+            if (q2.empty()) {
+                break;
+            }
+            w += q2.top();
+            q2.pop();
+        }
+        return w;
+    }
+};
diff --git a/solution/0500-0599/0502.IPO/Solution.go b/solution/0500-0599/0502.IPO/Solution.go
@@ -0,0 +1,38 @@
+func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
+	q1 := hp2{}
+	for i, c := range capital {
+		heap.Push(&q1, pair{c, profits[i]})
+	}
+	q2 := hp{}
+	for k > 0 {
+		for len(q1) > 0 && q1[0].c <= w {
+			heap.Push(&q2, heap.Pop(&q1).(pair).p)
+		}
+		if q2.Len() == 0 {
+			break
+		}
+		w += heap.Pop(&q2).(int)
+		k--
+	}
+	return w
+}
+
+type hp struct{ sort.IntSlice }
+
+func (h hp) Less(i, j int) bool  { return h.IntSlice[i] > h.IntSlice[j] }
+func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
+func (h *hp) Pop() interface{} {
+	a := h.IntSlice
+	v := a[len(a)-1]
+	h.IntSlice = a[:len(a)-1]
+	return v
+}
+
+type pair struct{ c, p int }
+type hp2 []pair
+
+func (h hp2) Len() int            { return len(h) }
+func (h hp2) Less(i, j int) bool  { return h[i].c < h[j].c }
+func (h hp2) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
+func (h *hp2) Push(v interface{}) { *h = append(*h, v.(pair)) }
+func (h *hp2) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
diff --git a/solution/0500-0599/0502.IPO/Solution.java b/solution/0500-0599/0502.IPO/Solution.java
diff --git a/solution/0500-0599/0502.IPO/Solution.py b/solution/0500-0599/0502.IPO/Solution.py
