贪心算法 - 贪心算法 - 《Java 后端开发秋招》

455.分发饼干 376摆动序列 53最大子序列和 55跳跃游戏 45跳跃游戏II 1005 K次取反后的最大化数组和 134加油站 135分发糖果 860柠檬水找零 406根据身高重建队列

455. 分发饼干

public int findContentChildren(int[] g, int[] s) {
    if(s==null||s.length==0){
        return 0;
    }
    Arrays.sort(g);
    Arrays.sort(s);
    int res=0;
    int index=s.length-1;
    //遍历胃口，先喂饱大胃王
    for(int i=g.length-1;i>=0;i--){
        if(s[index]>=g[i]){
            res++;
            index--;
        }
    }
    return res;
}
第二种方式：
if(s==null||s.length==0){
return 0;
}
Arrays.sort(g);
Arrays.sort(s);
int res=0;
int index=0;
//遍历饼干，小饼干先喂饱小胃口
for(int i=0;i<s.length&&index<g.length;i++){
    if(s[i]>=g[index]){
        res++;
        index++;
    }
}
        return res;

376. 摆动序列

int count=1;
int lastDiff=0;
int curDiff=0;
for(int i=1;i<nums.length;i++){
    curDiff=nums[i]-nums[i-1];
    if((curDiff>0&&lastDiff<=0)||(curDiff<0&&lastDiff>=0)){
        count++;
        lastDiff=curDiff;
    }
}
return count;

53. 最大子数组和

int[]dp=new int[nums.length];
int res=nums[0];
dp[0]=res;
for(int i=1;i<nums.length;i++){
    dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
    res=Math.max(res,dp[i]);
}
   return res;

55. 跳跃游戏

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

45. 跳跃游戏 II

if(nums.length==1){
  return 0;
}
int res=0;
int maxCover=0;
int curCover=0;
for(int i=0;i<nums.length;i++){
  maxCover=Math.max(i+nums[i],maxCover);
  if(maxCover>=nums.length-1){
    res++;
    break;
  }
  if(i==curCover){
    curCover=maxCover;
    res++;
  }
}
return res;

1005. K 次取反后最大化的数组和

Arrays.sort(nums);
int res=0;
int index=0;
while (index<nums.length){
  if(nums[index]<0&&k>0){
    nums[index]=-nums[index];
    k--;
    index++;
  }else{
    break;
  }
}
if(k%2==1){
  if(index-1<0) {
    nums[index] = -nums[index];
  }else if(index==nums.length){
    nums[index-1]=-nums[index-1];
  }else if(nums[index]<nums[index-1]){
    nums[index]=-nums[index];
  }else{
    nums[index-1]=-nums[index-1];
  }
}
for (int num : nums) {
  res+=num;
}
return res;

134. 加油站

int curSum=0;
int totalSUm=0;
int res=0;
for(int i=0;i<gas.length;i++){
  totalSUm+=(gas[i]-cost[i]);
  curSum+=(gas[i]-cost[i]);
  if(curSum<0){
    res=i+1;
    curSum=0;
  }
}
if(totalSUm<0){
  return -1;
}else{
  return res;
}

135. 分发糖果

int[]dp=new int[ratings.length];
Arrays.fill(dp,1);
for(int i=1;i<dp.length;i++){
  if(ratings[i]>ratings[i-1]){
    dp[i]=dp[i-1]+1;
  }
}
for(int i=dp.length-2;i>=0;i--){
  if(ratings[i]>ratings[i+1]&&dp[i]<=dp[i+1]){
    dp[i]=dp[i+1]+1;
  }
}
int res=0;
for (int i : dp) {
  res+=i;
}
return res;

860. 柠檬水找零

int fiveCount=0;
int tenCount=0;
int twentyCount=0;
for(int i=0;i<bills.length;i++){
  if(bills[i]==5){
    fiveCount++;
  }else if(bills[i]==10){
    if(fiveCount==0){
      return false;
    }else{
      fiveCount--;
      tenCount++;
    }
  }else{
    if(tenCount>=1&&fiveCount>=1){
      tenCount--;
      fiveCount--;
      twentyCount++;
    }else if(fiveCount>=3){
      fiveCount-=3;
    }else{
      return false;
    }
  }
}
return true;

406. 根据身高重建队列

Arrays.sort(people, new Comparator<int[]>() {
  @Override
  public int compare(int[] o1, int[] o2) {
    if(o1[0]==o2[0]){
      return o1[1]-o2[1];
    }else{
      return o2[0]-o1[0];
    }
  }
});
LinkedList<int[]> res = new LinkedList<>();
for (int[] person : people) {
  res.add(person[1],person);
}
return res.toArray(new int[res.size()][]);

452. 用最少数量的箭引爆气球

Arrays.sort(points, new Comparator<int[]>() {
  @Override
  public int compare(int[] o1, int[] o2) {
    if(o1[0]<o2[0]){
      return -1;
    }else if(o1[0]>o2[0]){
      return 1;
    }else{
      return 0;
    }
  }
});
int res=1;
for(int i=1;i<points.length;i++){
  if(points[i][0]<=points[i-1][1]){
    points[i][1]=Math.min(points[i][1],points[i-1][1]);
  }else{
    res++;
  }
}
return res;

435. 无重叠区间

int res=0;
Arrays.sort(intervals, new Comparator<int[]>() {
  @Override
  public int compare(int[] o1, int[] o2) {
    if(o1[1]<o2[1]){
      return -1;
    }else if(o1[1]>o2[1]){
      return 1;
    }else{
      return o1[0]-o2[0];
    }
  }
});
int last=intervals[0][1];
for(int i=1;i<intervals.length;i++){
  if(intervals[i][0]<last){
    res++;
  }else{
    last=intervals[i][1];
  }
}
return res;

763. 划分字母区间

char[] chars = s.toCharArray();
int[]dp=new int[26];
for(int i=0;i<chars.length;i++){
  dp[chars[i]-'a']=i;
}
List<Integer>res=new ArrayList<>();
int max=Integer.MIN_VALUE;
int last=-1;
for(int i=0;i<chars.length;i++) {
  max = Math.max(max, dp[chars[i] - 'a']);
  if(i==max){
    res.add(i-last);
    last=i;
  }
}
return res;

56. 合并区间

Deque<int[]>res=new LinkedList<>();
Arrays.sort(intervals, new Comparator<int[]>() {
  @Override
  public int compare(int[] o1, int[] o2) {
    if(o1[0]==o2[0]){
      return o1[1]-o2[1];
    }else{
      return o1[0]-o2[0];
    }
  }
});
res.add(intervals[0]);
for(int i=1;i<intervals.length;i++){
  if(intervals[i][0]<=intervals[i-1][1]){
    int[] ints = res.pollLast();
    ints[0]=Math.min(ints[0],intervals[i][0]);
    ints[1]=Math.max(ints[1],intervals[i][1]);
    res.addLast(ints);
    intervals[i]=ints;
  }else{
    res.addLast(intervals[i]);
  }
}
return res.toArray(new int[res.size()][]);

738. 单调递增的数字

if(n%10==n){
  return n;
}
char[] chars = String.valueOf(n).toCharArray();
for(int i=chars.length-2;i>=0;i--){
  if(chars[i]>chars[i+1]){
    chars[i+1]='9';
    chars[i]--;
  }
}
for(int i=1;i<chars.length;i++){
  if(chars[i]<chars[i-1]){
    chars[i]='9';
  }
}
String s=new String(chars);
return Integer.parseInt(s);

968. 监控二叉树

//1表示该节点安装摄像头，0表示当前节点没有被覆盖，2表示该节点被覆盖
        int monitor = monitor(root);
        if(monitor==0){
            res++;
        }
        return res;
    }
    private int monitor(TreeNode root){
        if(root==null){
            return -1;
        }
        int monitorLeft = monitor(root.left);
        int monitorRight = monitor(root.right);
        if(monitorLeft==0||monitorRight==0){
            res++;
            return 1;
        }else if(monitorLeft==1||monitorRight==1){
            return 2;
        }else{
            return 0;
        }
    }