1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int ans=0;
        int index=s.length-1;
        for(int i=g.length-1;i>=0;i--)
        {
            if(s[index]>g[i])
            {
                ans++;
                index--;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length<=1)return nums.length;
        int prediff=0;
        int curdiff=0;
        int res=1;
        for(int i=0;i<nums.length-1;i++)
        {
            curdiff=nums[i+1]-nums[i];
            if((prediff>=0&&curdiff<0)||(prediff<=0&&curdiff>0))
            {
                res++;
                prediff=curdiff;
            }
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maxSubArray(int[] nums) {
        int res=Integer.MIN_VALUE;
        int count=0;
        for(int i=0;i<nums.length;i++)
        {
            count+=nums[i];
            if(count>res)
                res=count;
            if(count<=0)
            {
                count=0;
            }
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int maxProfit(int[] prices) {
        int res=0;
        for(int i=1;i<prices.length;i++)
        {
            if(prices[i]-prices[i-1]>0)
                res+=prices[i]-prices[i-1];
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int res=0;
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]<0&&k>0)
            {
                nums[i]=-nums[i];
                k--;
            }
        }
        if(k%2==1)
        {
            Arrays.sort(nums);
            nums[0]=-nums[0];
        }
        for(int i=0;i<nums.length;i++)
        {
            res+=nums[i];
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n=cost.length;
        // 从start出发的净油量
        int curSum=0;
        // 从0开始的净油量
        int totalSum=0;
        int start=0;
        for(int i=0;i<n;i++){
            curSum+=gas[i]-cost[i];
            totalSum+=gas[i]-cost[i];
            if(curSum<0){
                start=i+1;
                curSum=0;
            }
        }
        if(totalSum<0){
            return -1;
        }
        return start;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n=cost.length;
        int x=0;
        while(x<n){
            int sumGas=0;
            int sumCost=0;
            int cnt=0; //覆盖的加油站数
            while(cnt<n){
                int y=(x+cnt)%n; // 计算加油站编号y
                // 计算x~y的油量和花费
                sumGas+=gas[y];
                sumCost+=cost[y];
                // 无法到达则直接停止循环
                if(sumGas<sumCost){
                    break;
                }
                cnt++;
            }
            // 成功环绕一圈则直接返回x
            if(cnt==n){
                return x;
            }else{
                x=x+cnt+1; // 更新x为x+y的下一个位置
            }
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    public boolean lemonadeChange(int[] bills) {
        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)
            {
                tenCount++;
                fiveCount--;
                if(fiveCount<0)
                {
                    return false;
                }
            }
            else if(bills[i]==20)
            {
                twentyCount++; // 收下一张二十
                // 优先找一张十块和一张五块
                if(fiveCount>=1&&tenCount>=1)
                {
                    fiveCount--;
                    tenCount--;
                }
                // 其次找三张五块
                else if(fiveCount>=3)
                {
                    fiveCount-=3;
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int candy(int[] ratings) {
        int n=ratings.length;
        int[]candy=new int[n];
        Arrays.fill(candy,1);
        // 从左往右遍历，处理左孩子小于右孩子
        for(int i=1;i<n;i++){
            if(ratings[i-1]<ratings[i]){
                candy[i]=candy[i-1]+1;
            }
        }
        // 从右往左遍历，处理左孩子大于右孩子
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                candy[i]=Math.max(candy[i],candy[i+1]+1);
            }
        }
        int res=0;
        for(Integer i:candy){
            res+=i;
        }
        return res;

    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0])
                    return o1[1]-o2[1];
                return o2[0]-o1[0];
            }
        });
        LinkedList<int[]>que=new LinkedList<>();
        for(int[]p:people){
            que.add(p[1],p);
        }
        return que.toArray(new int[people.length][]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 对区间的左端点排序
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0],o2[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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// 求解个数
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        int count=1;
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]>=intervals[i-1][1]){
                count++;
            }else{
                intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
            }
        }
        return intervals.length-count;
    }
}

// 求解区间
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        LinkedList<int[]>res=new LinkedList<>();
        res.add(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]>=res.getLast()[1]){
                res.add(intervals[i]);
            }else{
                res.set(res.size()-1,new int[]{res.getLast()[0],Math.min(res.getLast()[1],intervals[i][1])});
            }
        }
        return intervals.length-res.size();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 统计每个字符最后出现的位置
        int[]hash=new int[26];
        List<Integer>res=new ArrayList<>();
        for(int i=0;i<s.length();i++){
            hash[s.charAt(i)-'a']=i;
        }
        // 记录区间的起点和终点
        int start=0;
        int end=0;
        for(int i=0;i<s.length();i++){
            end=Math.max(end,hash[s.charAt(i)-'a']);
            if(i==end){
                res.add(end-start+1);
                start=end+1;
            }
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        LinkedList<int[]> res=new LinkedList<>();
        res.add(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            // 不重叠
            if(intervals[i][0]>res.getLast()[1]){
                res.add(intervals[i]);
            }else{
                int left=res.getLast()[0];
                int right=Math.max(res.getLast()[1],intervals[i][1]);
                res.removeLast();
                res.add(new int[]{left,right});
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String str=String.valueOf(n);
        char[]chars=str.toCharArray();
        // 记录转折点
        int start=chars.length;
        for(int i=chars.length-2;i>=0;i--){
            // 非d
            if(chars[i]>chars[i+1]){
                chars[i]--;
                start=i+1;
            }
        }
        for(int i=start;i<chars.length;i++){
            chars[i]='9';
        }
        return Integer.valueOf(new String(chars));
    }
}