# 算法细节系列（21）：贪心有理？

《算法导论》也有关于贪心算法的相关章节，但我还不敢看，无非怕被书中的论述思维给限制住了。所以先刷点题，对贪心有了基本了解后，回过头来再看它的论证。

## Leetcode 502: IPO

```    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
int total = W;
for (int i = 0; i < k; i++){
int maxProfit = 0;
//find the max Profit
int index = -1;
for (int j = 0; j < Capital.length; j++){
if (Capital[j] <= total){
if (maxProfit < Profits[j]){
maxProfit = Profits[j];
index = j;
}
}
}
Capital[index] = Integer.MAX_VALUE;
total += maxProfit;
}
}```

TLE了，如果有n个项目，那么上述代码时间复杂度为O(n2)O(n^2)。嘿，其实在它贪心的背后，它是一道数据结构题，用到了优先队列。

```for (int j = 0; j < Capital.length; j++){
if (Capital[j] <= total){
if (maxProfit < Profits[j]){
maxProfit = Profits[j];
index = j;
}
}
}```

```private class Pair{
int profit;
int capital;

Pair(int profit, int capital){
this.profit = profit;
this.capital = capital;
}
}

public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
int n = Profits.length;
Pair[] pairs = new Pair[n];

for (int i = 0; i < n; i++){
pairs[i] = new Pair(Profits[i],Capital[i]);
}

PriorityQueue<Pair> q1 = new PriorityQueue<>((o1,o2) -> (o1.capital - o2.capital));
PriorityQueue<Pair> q2 = new PriorityQueue<>((o1,o2) -> (o2.profit - o1.profit));

for (int i = 0; i < n; i++){
q1.offer(pairs[i]);
}

int total = W;
for (int i = 0; i < k; i++){
while (!q1.isEmpty() && q1.peek().capital <= total){
q2.offer(q1.poll());
}
total += q2.poll().profit;
}
}```

## Leetcode 055: Jump Game

```public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
return canJump(nums,0,dp);
}

private boolean canJump(int[] nums, int pos,boolean[] dp){
if (dp[pos]) return false;
if (pos >= nums.length - 1) return true;
else{
int step = nums[pos];
for (int i = 1; i <= step; i++){
if (canJump(nums,pos + i,dp)){
return true;
}
}
}
dp[pos] = true;
return false;
}```

```    public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
dp[0] = true;
for (int i = 0; i < nums.length; i++) {
if (!dp[i]) continue;
int step = nums[i];
for (int j = 1; j <= step; j++) {
if (i + j >= nums.length)
continue;
dp[i + j] = dp[i] || dp[i + j];
}
}
return dp[nums.length - 1];
}```

```nums = [25000,25000,24000,1]

```public boolean canJump(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++){
if (i > max) return false;
max = Math.max(max, nums[i] + i);
if (max >= nums.length-1) return true;
}
return true;
}```

## Leetcode 330: Patching Array

```nums = [1,2,5] n = 7

111 表示 1+2+5=8
110 表示 1+2 = 3

000,001,010,011,100,101,110,111

0,1,2,3,5,6,7,8

nums = [1,2,4,5] n = 7

0,1,2,3,4,5,6,7  (由1,2,4得)

0,1,2,3,4,5,6,7
5,6,7,8,9,10,11,12

0,1,2,3,4,5,6,7,8,9,10,11,12

0,1,...,12
| 13,14,...,25

0,1,2,...,6,...,12
| 7,8,9,10,...,19

```    public int minPatches(int[] nums, int n) {
long miss = 1;
int added = 0, i = 0;
while (miss <= n){
if (i < nums.length && nums[i] <= miss){
miss += nums[i++];
}
else{
miss += miss;
}
}
}```

0 条评论

• ### LWC 54：698. Partition to K Equal Sum Subsets

LWC 54：698. Partition to K Equal Sum Subsets 传送门：698. Partition to K Equal Sum S...

• ### 算法细节系列（35）：不一样的排序

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 动态规划设计

输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

• ### 程序员面试金典 - 面试题 16.17. 连续数列（DP/分治）

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/contiguous-sequence-lcci 著...

• ### 【LeetCode算法】两数之和

LeetCode第一题：两数之和题目描述题目分析题目解答思路一：双重for循环（1）代码（2）提交结果思路二：hashmap键值对一次遍历（1）代码（2）提交结...

• ### 漫画：动态规划系列 第二讲

在上一篇文章中，我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中，我们将继续通过1道简单题型，进一步学习动态规划的思想。

• ### LeetCode 300. Longest Increasing Subsequence (DP)

有O(n^2)效率，还有O(n*logn)效率的。 O(n^2)的效率很好理解的啦，就是大家最常见的那种DP

• ### LeetCode45|数组中重复的数据

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

• ### 详解三道一维的动态规划算法题

在一条直线上，有n个房屋，每个房屋中有数量不等的财宝，有一个盗 贼希望从房屋中盗取财宝，由于房屋中有报警器，如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问...