跳跃游戏
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-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
分发糖果
class Solution {
public int candy(int[] ratings) {
int[] sum=new int[ratings.length];
sum[0]=1;
for(int i=1;iratings[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
柠檬水找零
class Solution {
public boolean lemonadeChange(int[] bills) {
int ten=0;
int five=0;
for(int i=0;i0)
{
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 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;iintervals[i][0])
{
pre=Math.min(pre,intervals[i][1]);
count++;
}
else{
pre=intervals[i][1];
}
}
return count;
}
}
划分字母区间
class Solution {
public List partitionLabels(String s) {
List result=new LinkedList<>();
int[] ch=new int[26];
for(int i=0;i
合并区间
class Solution {
public int[][] merge(int[][] intervals) {
List 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+feebuy)
{
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;
}
}