Greedy-Easy
Abstract： 更新部分
Easy难度 Greedy相关题解
122. Best Time to Buy and Sell Stock II
解法一：贪心
显然，如果允许无限次交易的话，那么只要有差价就能赚，因此总利润就是升价之和
class Solution {
public int maxProfit(int[] prices) {
if(prices.length<=1){return 0;} //特殊情况
int profit=0;
for(int i=1;i<prices.length;i++){
int check=prices[i]-prices[i-1];
profit+=check>0?check:0; //只要本次交易有利可得就去赚，必定能使利益最大化
}
return profit;
}
}
455. Assign Cookies
解法一：贪心
- 策略：先排序，用最小的饼干先喂胃口最小的小鬼
- 特殊情况：两者可能为空要注意，但是本题不会有不良影响就是了
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);//先排序
int cookie=0,maxAssign=0;//记录饼干的位置和最大人数
for(int i=0;i<g.length;i++){
while(cookie<s.length){
if(s[cookie]>=g[i]){//如果满足的话，人数++，饼干用掉了所以移动到下一块，cookie++
maxAssign++;
cookie++;
break;//代码中注意不要出现break，影响美观，这里是反面教材了
}
cookie++;//不满足的话就换下一个饼干
}
}
return maxAssign;
}
}
- 简洁版：根本不需要专门记录最大人数，另外改掉
break这样的不良习惯，出现break只会让代码丑且丢人
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);//先排序
int cookie=0,greedy=0;//记录饼干的位置、小鬼位置
while(cookie<s.length && greedy<g.length){
if(g[greedy]<=s[cookie])greedy++;
cookie++;
}
return greedy;//根本不需要记录最大人数，greedy的最终值就是最大人数
}
}
1046. Last Stone Weight（TopK问题）
解法一：排序
依题意，每次都用最重的两块石头，那么就每轮排一次序就行了
虽然简洁易懂，但是缺点是快排空间消耗比较大，另外数据规模大时额外消耗的时间也比较大
class Solution {
public int lastStoneWeight(int[] stones) {
if(stones==null || stones.length==0){return 0;} //特殊情况 null或为空
int stoneNum=stones.length,len=stones.length;
while(stoneNum>1){//每轮都排一次序，直到石头小于一颗
Arrays.sort(stones);
stones[len-1]=stones[len-1]-stones[len-2];
stones[len-2]=0;
stoneNum--;
}
return stones[len-1];//返回最后一颗石子的重量即为答案
}
}
解法二：优先队列
由于问题本质是TopK问题，因此用优先队列是相当王道的做法
小数据下比简单排序略逊，但是数据量增大时优于排序
class Solution {
public int lastStoneWeight(int[] stones) {
if(stones==null || stones.length==0){return 0;}
Queue<Integer> stoneQ=
new PriorityQueue<Integer>(Collections.reverseOrder());//优先队列
for(int stone:stones){stoneQ.add(stone);}//初始化
while(stoneQ.size()>2){//边界处理，如果>1的话可能会让空队列poll
int stoneSmashed=stoneQ.poll()-stoneQ.poll();
if(stoneSmashed>0)stoneQ.add(stoneSmashed);//如果没彻底smashed，就放回队列中
}
return stoneQ.size()>1?stoneQ.poll()-stoneQ.poll():stoneQ.peek();
//依据情况返回对应结果
}
}
860. Lemonade Change
解法一：贪心
如果是5块和10块没什么可说的，重点是20块
如果是20块，要优先找10块和5块组合，实在不行才用三张5块
class Solution {
public boolean lemonadeChange(int[] bills) {
int five=0,ten=0;//分别记录5块和10块
for(int i=0;i<bills.length;i++){
if(bills[i]==5)five++; //5块时直接++
else if(bills[i]==10){ //10块时直接找5块，没有就gg
if(five>0){ten++;five--;}
else return false;
}
else if(bills[i]==20){ //优先找10块
if(ten>0 && five>0){ten--;five--;}
else if(five>=3){five-=3;}
else return false;
}
}
return true;
}
}
874. Walking Robot Simulation
解法一：HashSet+模拟
麻烦在写逻辑
class Solution {
public int robotSim(int[] commands, int[][] obstacles) {
int x=0,y=0,turn=0,maxDistance=0;
int[] moves = new int[2];
//借用官方的编码模式
Set<Long> obstacleSet = new HashSet();
for (int[] obstacle: obstacles) {
long ox = (long) obstacle[0] + 30000;
long oy = (long) obstacle[1] + 30000;
obstacleSet.add((ox << 16) + oy);
}
for(int i=0;i<commands.length;i++){
if(commands[i] == -1){turn=(turn+1)%4;} //右转90度
else if(commands[i] == -2){turn=(turn+3)%4;} //左转90度，注意不要--，因为负数不能%
else{ //否则应该是移动
for(int k=0;k<commands[i];k++){ //一格一格地走
moves = move(turn,moves); //根据方向和command计算移动的(x,y)
int nx=x+moves[0];
int ny=y+moves[1];
long code = (((long) nx + 30000) << 16) + ((long) ny + 30000);
if (!obstacleSet.contains(code)) {
x = nx;
y = ny;
maxDistance = Math.max(maxDistance, x*x + y*y);
}
}
}
}
return maxDistance;
}
public int[] move(int turn,int[] moves){ //判断移动的x,y
if(turn%4 == 0){moves[0]=0;moves[1]=1;return moves;}
else if(turn%4 == 1){moves[0]=1;moves[1]=0;return moves;}
else if(turn%4 == 2){moves[0]=0;moves[1]=-1;return moves;}
else if(turn%4 == 3){moves[0]=-1;moves[1]=0;return moves;}
return moves;
//throw new IllegalArgumentException;
}
}