greedy_algorithm

关于贪心算法呐

常见套路

背包问题

Leetcode题目

45. 跳跃游戏 II

为什么这个标号会在前面

我们每次选可以跳的最远的的格子,然后继续选在可以到的区域里面的格子,我们只需要找每一段区间里面的最大值即可

由于我是zz,写了一个单调队列

单调队列版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int jump(int[] nums) {
int n=nums.length;
int ans=0;
int []jmp=nums;
for(int i=0;i<n;i++){
jmp[i]+=i;
if(jmp[i]>=(n-1)) jmp[i]=n-1;
}
if(n==1) return 0;
int l=0;
int r=0;
int []q=new int[n];
int pos=1;
int x=0;int y=jmp[x];
while(true){
ans++;
while(l<=r&&q[l]<x) l++;
while(pos<=y){
while(l<=r&& jmp[q[r]]<=jmp[pos]) r--;
q[++r]=pos;
pos++;
}
x=q[l];
if(x==n-1) return ans;
y=jmp[x];
x++;
}
}
}

正常写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int jump(int[] nums) {
int ans=0;
int end=0;
int maxpos=0;
for(int i=0;i<nums.length-1;i++){
maxpos=Math.max(i+nums[i],maxpos);
if(i==end){
end=maxpos;
ans++;
}
if(end==nums.length-1) return ans;
}
return ans;
}
}

我们可以注意到,我们每次都是选可以走到最远的节点,如果选择了其他节点,那么之后的选择不会变多(或者说我们这样选择是上升的最快的,如果选了其他的节点,那么我们下一次所能到的节点不会更远),所以这样做是最优的

55. 跳跃游戏

134. 加油站

考虑到只要加的比用的多,就一定有解,为什么呢

如果正好相等,问题就变成了是否存在一个点,能够绕一圈,我们假定不存在

我们假定我们选择1节点,那么到某一个点(a)的时候如果不够油,那么我们发现我们无法从1-a之间的任何一个节点出发而绕一圈,只能从之后的再出发,不难发现的是,我们最后一次出发的节点就是答案,为什么呢,在到达n节点之后,我们会继续从1出发,这样会至少能达到a节点,而且这样做的费用一定是够的,因为费用最后平衡,所有后面那部分一定会包含前面的,如果前面一共有m段,我们可以发现的是最后那一段一定会包含前面的段,因为总和为0,而前面的都是负数,所以后面那部分必然包含前面的花费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int all=0;
int cur=0;
int ans=0;
int n=gas.length;
for(int i=0;i<n;i++){
all+=(gas[i]-cost[i]);
cur+=(gas[i]-cost[i]);
if(cur<0) {
ans=i+1;
cur=0;
}
}
return all<0 ? -1 : ans;
}
}

135. 分发糖果

好像和直接模拟差不多,我们现在只管下降的。

情况比较少,如果说我们当前元素比之前的元素要小的话,就用它替代,同时长度加1.如果是大于的的话,那么前面一个元素必定是1,我们可以直接计算,注意最后一个元素的值要单独计算,然后更细最后一个元素的值,实际上就是它的前一个的值+1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int candy(int[] ratings) {
int ans=0;
int n=ratings.length;
int cnt=0;
int stk;
if(n==0) return 0;
stk=ratings[0];
cnt++;
int pre=1;
for(int i=1;i<n;i++){
int cur=ratings[i];
if(cur>=stk){
ans += (cnt)*(cnt-1)/2;
ans+=Math.max(cnt,pre);
if(cnt==1) pre=pre+1;
else pre=2;
if(cur==stk) pre=1;
cnt=0;
}
stk=cur;
cnt++;
}
if(cnt>=1){
ans+= (cnt-1)*(cnt)/2;
ans+=Math.max(pre,cnt);
}
return ans;
}
}

253. 会议室 II

考虑离散化然后差分求每个时间点会有多少人同时开会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public int minMeetingRooms(int[][] intervals) {
int n=intervals.length;
if(n==0) return 0;
int []l=new int[n];
int []r=new int[n];
int []arr=new int[n*2];
Map<Integer,Integer> M=new HashMap();
for(int i=0;i<n;i++){
l[i]=intervals[i][0];
r[i]=intervals[i][1];
arr[i]=l[i];
arr[i+n]=r[i];
}
int ans=0;
Arrays.sort(arr);
int cnt=1;
M.put(arr[0],cnt);
for(int i=1;i<n*2;i++){
if(arr[i]==arr[i-1]) continue;
M.put(arr[i],++cnt);
}
int []lis=new int[cnt+1];
System.out.println(cnt);
for(int i=0;i<n;i++){
int L=M.get(l[i]);
int R=M.get(r[i]);
lis[L]+=1;
lis[R]-=1;
}
for(int i=1;i<=cnt;i++){
lis[i]+=lis[i-1];
ans=Math.max(lis[i],ans);
}
return ans;

}
}

376. 摆动序列

考虑连续的三个数$x_1,x_2,x_3$,如果$x_1\leq x_2\leq x_3$,那么这样对答案是没有贡献的,如果是不同的数,

如果第一次就是上升的,之后还是上升的,那么我们可以直接把序列变成第一个加上最后一个,这样的话不会错过之后所有的下降,下降同理可以按之前的算。

这样我们维护一个之前的正负即可,相同继续,否则就更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int wiggleMaxLength(int[] nums) {
int n=nums.length;
if(n<2) return n;
int diff;
int prediff=nums[1]-nums[0];
int ans= prediff==0 ? 1 : 2;
for(int i=2;i<n;i++){
diff= nums[i] - nums[i-1];

if(diff< 0 && prediff=> 0 ){
prediff = diff;
ans++;
}else if(diff > 0 && prediff <=0){
prediff =diff;
ans++;
}
}
return ans;
}
}

如果第一次是0的话,应该继续往后找,直到出现了不是0的,我们这样处理可以省略这一步。

402. 移掉K位数字

我们发现12是优先删除2,而21是优先删除1,也就是如果后面一个数比前面一个数要小的话,那么我们就应该尽量把它之前而且比它小的删掉,而且它的位置是尽量考后的,我们使用单调栈即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public String removeKdigits(String num, int k) {
int n=num.length();
char []stk=new char[n+1];
int cnt=0;
for(char c : num.toCharArray()){
while(k>0&&(cnt!=0&&stk[cnt]>c)) {cnt--;k--;}
stk[++cnt]=c;
}
while(k>0){
cnt--;
k--;
}
String ans= cnt==0 ? "0":"";
boolean flg=true;
for(int i=1;i<=cnt;i++){
if(stk[i]=='0'&&flg) continue;
flg=false;
ans += stk[i];
}
return ans==""?"0":ans;
}
}

406. 根据身高重建队列

我们按身高从小到大就可以了,首先身高最高的就可以直接放到位置了,因为它的k就是它的位置,然后我们选剩下的身高最低的就可以了,这样继续,我们就可以确定所有人的位置了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public int[][] reconstructQueue(int[][] people) {
int n=people.length;
int [][]ans=new int[n][2];
for(int i=0;i<n;i++) ans[i][1]=-1;
for(int j=0;j<n;j++){
int sel=-1;
int selh=0;
int selk=0;
for(int i=0;i<n;i++){
int h=people[i][0];
int k=people[i][1];
if(k==-1) continue;
if(sel==-1){
selh=h;selk=k;sel=i;
}else{
if(selh==h){
if(k<selk){
sel=i;
selh=h;
selk=k;
}
}else if(selh>h){
sel=i;
selh=h;
selk=k;
}
}
}
int len=0;
int k=selk;
int h=selh;
people[sel][1]=-1;
for(int i=0;i<n;i++){
if(len==k){
while(ans[i][1]!=-1) i++ ;
ans[i][0]=h;
ans[i][1]=k;
break;
}
if(ans[i][1]==-1||ans[i][0]==h) len++;
}
}
return ans;
}
}

实际上我们第一部分可以用堆来维护,之后我们找位置是否有更快的找法

455. 分发饼干

我们把两个分开排序,然后直接双指针找满足每个人(从大到下)的最小饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int findContentChildren(int[] g, int[] s) {
int ans=0;
Arrays.sort(g);
Arrays.sort(s);
int posa=0;
int posb=0;
int n=g.length;
int m=s.length;
while(posa<n&&posb<m){
if(g[posa]<=s[posb]){ans++;posa++;posb++;}
else posb++;
}
return ans;
}
}

621. 任务调度器

我们可以直接模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int leastInterval(char[] tasks, int n) {
int buk[]=new int[26];
int pre[]=new int[26];
for(char c : tasks){
int d= c-'A';
buk[d]++;
}
int all=26;
for(int x : buk){
all -= x==0 ? 1 : 0;
}
int ans=0;
while(all!=0){
ans++;
int sel=-1;
for(int i=0;i<26;i++){
if(pre[i]!=0) continue;
if(sel==-1) sel=i;
if(buk[sel]<buk[i]) sel=i;
}
for(int i=0;i<26;i++){
if(pre[i]!=0) pre[i]--;
}
if(sel==-1) continue;
if(buk[sel]==1) all--;
buk[sel]--;
pre[sel]=n;
}
return ans;
}
}

我们也可以按任务来考虑

1354. 多次求和构造目标数组

我们直接按逆序构造即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
#define LL long long
bool isPossible(vector<int>& target) {
LL sum=0;
priority_queue<LL> Q;
int siz = 0;
for(auto x : target) {
Q.push(x);
sum+=x;
}
while(1){
LL cur= Q.top();Q.pop();
if(cur==1) break;
// LL pre= 2*cur - sum;
LL les = sum - cur;
if(Q.empty()) return false;
LL big = Q.top();
int tim =( cur - big + les - 1 ) / les;
LL pre = cur + tim * (cur - sum);
if(pre<1||tim == 0) return false;
sum=pre + sum -cur ;
Q.push(pre);
}
return true;
}
};