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.length){
if(s[indexS] >= 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 < nums.length; i++){
cur = nums[i] - nums[i - 1];
if((cur > 0 && pre <= 0) || (cur < 0 && pre >= 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.length; i++){
if(prices[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 <= coverMax; i++){//防止中途就出现覆盖范围中断
coverMax = Math.max(coverMax, i + nums[i]);
if(coverMax >= 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; i++){
// 更新在当前覆盖范围内的最大覆盖范围（下一步可以跳到的最大范围）
maxCover = Math.max(nums[i] + i, maxCover);
// 再跳一步就可以到达
if(maxCover >= 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] < 0){
nums[index] = -nums[index];
if(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){
index = (i + 1)%arr.length;
curSum = 0;
}
}
if(sum >= 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.length; i++){
arrResult[i] = ratings[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<Integer> 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<int[]> 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.length; i++){
if(points[i][0] > 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<Integer> partitionLabels(String s) {
List<Integer> result = new ArrayList<>();
char temp;
int right = 0;
int left = 0;
for(int j = 0; j < s.length(); j++){
temp = s.charAt(j);
for(int i = s.length() - 1; i >= 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<int[]> 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 < prices.length; i++){
if(prices[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;
}
}
}