題目
做項目的最大收益問題
-
鏈接 做項目的最大收益問題
-
題目描述
給定兩個整數W和K,W代表你擁有的初始資金,K代表你最多可以做K個項目。再給定兩個長度為N的正數數組costs[]和profits[],代表一共有N個項目,costs[i]和profits[i]分別表示第i號項目的啟動資金與做完后的利潤(注意是利潤,如果一個項目的啟動資金為10,利潤為4,代表該項目最終的收入為14)。你不能并行只能串行地做項目,并且手里擁有的資金大于或等于某個項目的啟動資金時,你才能做這個項目。該如何選擇做項目,能讓你最終的收益最大?返回最后能獲得的最大資金。
[要求] 時間復雜度為 O(klogn),空間復雜度為 O(n)。
和原題不一樣的是,這里返回值是long類型。
- 輸入與輸出
第一行三個整數N, W, K。表示總的項目數量,初始資金,最多可以做的項目數量 第二行有N個正整數,表示costs數組
第三行有N個正整數,表示profits數組。
輸入:
4 3 2
5 4 1 2
3 5 3 2
輸出:
11
解釋:
初始資金為3,最多做兩個項目,每個項目的啟動資金與利潤見costs和profits。最優選擇為:先做2號項目,做完之后資金增長到6。然后做1號項目,做完之后資金增長到11。其他的任何選擇都不會比這種選擇好,所以返回11。
最長無重復數組
- 鏈接 最長無重復數組
- 題目描述
給定一個數組arr,返回arr的最長無重復元素子數組的長度,無重復指的是所有數字都不相同。
子數組是連續的,比如[1,3,5,7,9]的子數組有[1,3],[3,5,7]等等,但是[1,3,7]不是子數組
- 輸入與輸出
輸入:
[2,3,4,5]
輸出:
4
解釋:
[2,3,4,5]是最長子數組
思路
做項目的最大收益問題
- 建立節點,記錄每個項目的 cost 和 profits;
- 生成比較器,小根堆保存每個節點,大根堆根據情況(K 的取值、當前資金)保存值;
- 判斷當前資金是否滿足條件;
- 返回結果。
最長無重復子串
暴力解法
- 雙層循環遍歷數組,如果有重復的,就打破循環,判斷長度。
滑動窗口
- 定義 Map,key = arr[i] ,value = arr[i] 的下標;
- 遍歷數組,如果當前出現過,那么更新左窗口的最大值;
- 每次循環更新長度;
- 返回結果。
代碼
做項目的最大收益問題
import java.util.Comparator;
import java.util.PriorityQueue;
public class Slution{
/**
* return the max money
* @param costs int整型一維數組 the costs
* @param profits int整型一維數組 the profits
* @param W int整型 the money you have first
* @param K int整型 max projects
* @return long長整型
*/
public static long maxMoney (int[] costs, int[] profits, int W, int K) {
// write code here
// 返回結果是 long 如果不定義 long res 的話結果可能會錯誤
long res = W;
// 將項目的花費與收益存在 nodes 數組中
Node[] nodes = new Node[profits.length];
for (int i = 0; i < profits.length; i++) {
nodes[i] = new Node(profits[i], costs[i]);
}
PriorityQueue<Node> minQueue = new PriorityQueue<>(new MinHeapCom());
PriorityQueue<Node> maxQueue = new PriorityQueue<>(new MaxHeapCom());
// 建立小根堆, 按照 cost(花費) 排序
for (int i = 0; i < profits.length; i++) {
minQueue.add(nodes[i]);
}
// K 代表最多可做項目數量, 因此有了這個循環
for (int i = 0; i < K; i++) {
// 當 minQueue 不為空 并且 花費小于 W(初始資金) 時, 大根堆添加節點
while (!minQueue.isEmpty() && minQueue.peek().cost <= res) {
maxQueue.add(minQueue.poll());
}
// 如果資金不夠做下一個項目, 那么返回收益 res
if (maxQueue.isEmpty()) {
return res;
}
// 如果夠, 那么 res += 當前項目的收益
res += maxQueue.poll().profit;
}
return res;
}
// 小根堆
static class MinHeapCom implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.cost - o2.cost;
}
}
// 大根堆
static class MaxHeapCom implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o2.profit - o1.profit;
}
}
// 定義節點
static class Node {
int profit;
int cost;
public Node(int profit, int cost) {
this.profit = profit;
this.cost = cost;
}
}
}
最長無重復子串
暴力
public int maxLength (int[] arr) {
// write code here
// 定義結果
int res = -1;
for (int i = 0; i < arr.length; i++) {
// 每次使用 set 保存
Set<Integer> set = new HashSet<>();
// 添加當前元素
set.add(arr[i]);
for (int j = i+1; j < arr.length; j++) {
// 如果添加失敗, 那么說明有重復的元素,打破循環
if (!set.add(arr[j])) {
break;
}
}
// 比較當前長度與原來記錄的長度
res = Math.max(res,set.size());
}
return res;
}
滑動窗口
public static int maxLength (int[] arr) {
// 如果 arr.length < 2 直接返回結果
if (arr.length < 2) {
return arr.length;
}
// 定義結果
int res = -1;
// 使用 map 保存信息
// key 代表當前元素, value 代表當前元素的下標
Map<Integer, Integer> map = new HashMap<>();
// 遍歷數組
for (int i = 0, begin = 0; i < arr.length; i++) {
// 如果 map 中含有當前元素, 說明重復了
if (map.containsKey(arr[i])) {
// 此時需要判斷左邊界與原來的左邊界的值, 如果
begin = Math.max(map.get(arr[i]+1), begin);
}
res = Math.max(i - begin+1, res);
map.put(arr[i],i);
}
return res;
}
浙公網安備 33010602011771號