455、分发饼干
class Solution { public int count; public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); count = 0; int indexS = 0; int indexG = 0; while(indexS < s.length && indexG = g[indexG]){ count++; indexG++; indexS++; }else{ indexS++; } } return count; }}376、摆动序列
class Solution { public int wiggleMaxLength(int[] nums) { if(nums.length <= 1){ return nums.length; } int pre = 0; int cur = 0; int count = 1; for(int i = 1; i 0 && pre <= 0) || (cur = 0)){ count++; pre = cur; } } return count; }}53、最大子数组和
class Solution { public int maxSubArray(int[] nums) { if(nums.length == 1){ return nums[0]; } int count = 0; int sum = Integer.MIN_VALUE; for(int i = 0; i < nums.length; i++){ count += nums[i]; sum = Math.max(sum, count); if(count <= 0){ count = 0; } } return sum; }}122、买卖股票的最佳时机 II
class Solution { public int maxProfit(int[] prices) { int max = 0; for(int i = 1; i prices[i - 1]){ max += prices[i] - prices[i - 1]; } } return max; }}55、跳跃游戏
class Solution { public boolean canJump(int[] nums) { if(nums.length == 1){ return true; } int coverMax = 0; for(int i = 0; i = nums.length - 1){ return true; } } return false; }}45、跳跃游戏 II
class Solution { public int jump(int[] nums) { int count = 0; if(nums.length == 1){ return count; } // 当前覆盖范围 int coverMax = 0; // 最大覆盖范围 int maxCover = 0; for(int i = 0; i = nums.length - 1){ count++; break; } // 到达当前覆盖范围最大值，需要下一跳 if(i == coverMax){ count++; coverMax = maxCover; } } return count; }}1005、K 次取反后最大化的数组和
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { Arrays.sort(nums); int index = 0; for(int i = 0; i < k; i++){ if(i < nums.length - 1 && nums[index] = Math.abs(nums[index + 1])){ index++; } continue; } nums[index] = -nums[index]; } int sum = 0; for(int j = 0; j < nums.length; j++){ sum += nums[j]; } return sum; }}134、加油站
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int[] arr = new int[gas.length]; int sum = 0; int curSum = 0; int index = 0; for(int i = 0; i < arr.length; i++){ arr[i] = gas[i] - cost[i]; sum += arr[i]; curSum += arr[i]; if(curSum = 0){ return index; }else{ return -1; } }}135、分发糖果
class Solution { public int candy(int[] ratings) { // 最少糖果数目 int[] arrResult = new int[ratings.length]; arrResult[0] = 1; for(int i = 1; i ratings[i - 1] ? arrResult[i - 1] + 1 : 1; } for(int i = ratings.length - 2; i >= 0; i--){ if(ratings[i] > ratings[i + 1]){ arrResult[i] = Math.max(arrResult[i],arrResult[i + 1] + 1); } } int sum = 0; for(int j = 0; j < arrResult.length; j++){ sum += arrResult[j]; } return sum; }}860、柠檬水找零
class Solution { public boolean lemonadeChange(int[] bills) { if(bills[0] != 5){ return false; } if(bills.length == 1){ return true; } List money = new LinkedList(); money.add(5); for(int i = 1; i < bills.length; i++){ if(bills[i] == 5){ money.add(5); }else if(bills[i] == 10){ if(!money.contains(5)){ return false; } money.add(10); money.remove(new Integer(5)); }else if(bills[i] == 20){ if(money.contains(5) && money.contains(10)){ money.add(20); money.remove(new Integer(5)); money.remove(new Integer(10)); }else if(money.contains(5)){ for(int j = 0; j < 3; j++){ if(!money.contains(5)){ return false; } money.remove(new Integer(5)); } money.add(20); }else{ return false; } } } return true; }}406、根据身高重建队列
class Solution { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people,(a,b)->{ if(a[0]==b[0]) return a[1] - b[1]; return b[0] - a[0]; }); List queue = new LinkedList(); for(int[] p: people){ queue.add(p[1],p); } return queue.toArray(new int[people.length][]); }}452、用最少数量的箭引爆气球
class Solution { public int findMinArrowShots(int[][] points) { Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])); int count = 1; for(int i = 1; i points[i-1][1]){ count++; }else{ points[i][1] = Math.min(points[i-1][1],points[i][1]); } } return count; }}435、 无重叠区间
class Solution { public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals,(a,b)->{ if(a[0]==b[0])return a[1]-b[1]; return a[0]-b[0]; }); int resultCount = 0; int right = intervals[0][1]; for(int i = 1; i < intervals.length; i++){ if(intervals[i][0] < right){ resultCount++; if(intervals[i][1] < right){ right = intervals[i][1]; } }else{ right = intervals[i][1]; } } return resultCount; }}763、划分字母区间
class Solution { public List partitionLabels(String s) { List result = new ArrayList(); char temp; int right = 0; int left = 0; for(int j = 0; j = 0; i--){ if(temp == s.charAt(i)){ right = Math.max(right,i); break; } } if(j==right){ result.add(right-left+1); left = right+1; } } return result; }}56、合并区间
class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals,(a,b)->{ if(a[0]==b[0])return a[1]-b[1]; return a[0]-b[0]; }); List result = new LinkedList(); int right = intervals[0][1]; int left = intervals[0][0]; int count = 1; for(int i = 1; i < intervals.length; i++){ if(intervals[i][0]<=right){ right = Math.max(right,intervals[i][1]); }else{ result.add(new int[]{left,right}); left=intervals[i][0]; right=intervals[i][1]; count++; } } result.add(new int[]{left,right}); return result.toArray(new int[count][]); }}738、单调递增的数字
class Solution { public int monotoneIncreasingDigits(int n) { String str = String.valueOf(n); char[] arr = str.toCharArray(); int start = arr.length; for(int i = arr.length - 2; i >= 0; i--){ if(arr[i] > arr[i+1]){ arr[i]--; start = i+1; } } for(int j = start; j<arr.length; j++){ arr[j]='9'; } return Integer.parseInt(String.valueOf(arr)); }}714、买卖股票的最佳时机含手续费
class Solution { public int maxProfit(int[] prices, int fee) { if(prices.length==1){ return 0; } int index = prices[0]+fee; int sum=0; for(int i = 1; i index){ sum+=prices[i]-index; index=prices[i]; }else if(prices[i]+fee<index){ index=prices[i]+fee; } } return sum; }}968、监控二叉树
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { int res=0; public int minCameraCover(TreeNode root) { // 对根节点的状态做检验,防止根节点是无覆盖状态 . if(minCame(root)==0){ res++; } return res; } /** 节点的状态值： 0 表示无覆盖 1 表示 有摄像头 2 表示有覆盖 后序遍历，根据左右节点的情况,来判读 自己的状态 */ public int minCame(TreeNode root){ if(root==null){ // 空节点默认为 有覆盖状态，避免在叶子节点上放摄像头 return 2; } int left=minCame(root.left); int right=minCame(root.right); // 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头 if(left==2&&right==2){ //(2,2) return 0; }else if(left==0||right==0){ // 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头 // (0,0) (0,1) (0,2) (1,0) (2,0) // 状态值为 1 摄像头数 ++; res++; return 1; }else{ // 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头， // 那么本节点就是处于被覆盖状态 return 2; } }}