跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
       if(nums.length==1) return true;
       int cover=0;
        //覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
        //在覆盖范围内更新最大的覆盖范围
       for(int i=0;i<=cover;i++)
       {
           cover=Math.max(cover,i+nums[i]);
           if(cover>=nums.length-1)
           {
               return true;
           }
       }
       return false;
    }
}

跳跃游戏Ⅱ

class Solution {
    public int jump(int[] nums) {
      int max=0;
      int cur=0;
      int count=0;
      for(int i=0;i<nums.length;i++)
      {
          max=Math.max(max,i+nums[i]);
          if(i>=nums.length-1)
          {
              return count;
          }
          if(i==cur)
          {
              count++;
              cur=max;
          }
      }
      return count;
    }
}

k次取反后的最大化的数组

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        nums = IntStream.of(nums)
		     .boxed()
		     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
		     .mapToInt(Integer::intValue).toArray();
	int len = nums.length;	    
	for (int i = 0; i < len; i++) {
	    if (nums[i] < 0 && k > 0) {
	    	nums[i] = -nums[i];
	    	k--;
	    }
	}
	if (k % 2 == 1) nums[len - 1] = -nums[len - 1];
	return Arrays.stream(nums).sum();
    }
}

加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum=0;
        int rest=0;
        int start=0;
        for(int i=0;i<gas.length;i++)
        {
           sum+=gas[i]-cost[i];
           rest+=gas[i]-cost[i];
           if(rest<0)
           {
               start=i+1;
               rest=0;
           }
        }
        if(sum<0) return -1;
        return start;
    }
}

分发糖果

class Solution {
    public int candy(int[] ratings) {
        int[] sum=new int[ratings.length];
        sum[0]=1;
          for(int i=1;i<ratings.length;i++)
        {
            if(ratings[i]>ratings[i-1])
            {
                sum[i]=sum[i-1]+1;
            }
            else{
                sum[i]=1;
            }
        }
        for(int i=ratings.length-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1])
            {
                sum[i]=Math.max(sum[i],sum[i+1]+1);
            }
        }
        int count=0;
        for(int i=0;i<sum.length;i++)
        {
            count+=sum[i];
        }
        return count;
    }
}

柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int ten=0;
        int five=0;
        for(int i=0;i<bills.length;i++)
        {
            if(bills[i]==5)
            {
                five++;
            }
            if(bills[i]==10)
            {
                ten++;
                five--;
            }
            if(bills[i]==20)
            {
                if(ten>0)
                {
                    ten--;
                    five--;
                }else{
                    five=five-3;
                }
            }
            if(five<0)
            {
                return false;
            }
        }
        return true;
    }
}

根据身高重建队列

class Solution {
    public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people,(a,b)->
    {
        if(a[0]==b[0]) return a[1]-b[1];
        else return b[0]-a[0];
    });
    LinkedList<int[]> que=new LinkedList<>();
    for(int[] p:people)
    {
        que.add(p[1],p);
    }
    return que.toArray(new int[people.length][people[0].length]);
    }
}

无重叠区间

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
       Arrays.sort(intervals,(a,b)->{
           return a[0]-b[0];
       });
       int count=0;
       int pre=intervals[0][1];
       for(int i=1;i<intervals.length;i++)
       {
           if(pre>intervals[i][0])
           {
               pre=Math.min(pre,intervals[i][1]);
               count++;
           }
           else{
               pre=intervals[i][1];
           }
       }
       return count;
    }
}

划分字母区间

class Solution {
    public List<Integer> partitionLabels(String s) {
         List<Integer> result=new LinkedList<>();
         int[] ch=new int[26];
         for(int i=0;i<s.length();i++)
         {
             ch[s.charAt(i)-'a']=i;
         }
         int right=-1;
         int left=0;
         for(int i=0;i<s.length();i++)
         {
             right=Math.max(right,ch[s.charAt(i)-'a']);
             if(i==right)
             {
                 result.add(right-left+1);
                 left=i+1;
             }
         }
         return result;
    }
}

合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, (o1, o2) ->{
            return o1[0]-o2[0];
        });

        int start = intervals[0][0];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > intervals[i - 1][1]) {
                res.add(new int[]{start, intervals[i - 1][1]});
                start = intervals[i][0];
            } else {
                intervals[i][1] = Math.max(intervals[i][1], intervals[i - 1][1]);
            }
        }
        res.add(new int[]{start, intervals[intervals.length - 1][1]});
        return res.toArray(new int[res.size()][]);
    }
}

买卖股票含手续费

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int buy=prices[0]+fee;
        int sum=0;
        for(int p:prices)
        {
            if(p+fee<buy)
            {
                buy=p+fee;
            }
            else if(p>buy)
            {
                sum+=p-buy;
                buy=p;
            }
        }
        return sum;
    }
}

监控二叉树

class Solution {
    private int count = 0;
    public int minCameraCover(TreeNode root) {
       if(cal(root)==0) count++;
       return count;
    }
    public int cal(TreeNode root)
    {
        if(root==null) return -1;
        int left=cal(root.left);
        int right=cal(root.right);
        if(left==0||right==0){
            count++;
            return 2;
        }
        if(left==2||right==2) return 1;
        return 0;
    }
}