分发饼干

力扣

尽量满足需求小的孩子。

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) {
        if (g == null || s == null)
            return 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int gi = 0,si = 0;
        while (gi<g.length&&si<s.length){
            if (g[gi] <= s[si]){
                gi++;
            }
            si++;
        }
        return gi;

    }
}

无重叠区间

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));//按结尾排序
        int ret = 1;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                continue;
            }
            end = intervals[i][1];
            ret++;
        }
        return intervals.length - ret;


    }
}

用最少数量的箭引爆气球

和上体类似，计算不重叠区间的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0)
            return 0;
        Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
        int ret = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= end)
                continue;
            ret++;
            end = points[i][1];
        }
        return ret;

    }
}

根据身高重建队列

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
        for (int i = 0;i<people.length;i++){
            System.out.println(people[i][0]+" "+people[i][1]);
        }
        List<int[]> queue = new ArrayList<>();
        for (int i = 0;i< people.length;i++){
            queue.add(people[i][1],people[i]);
        }
        return queue.toArray(new int[queue.size()][]);
    }
}

买卖股票的最佳时机

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0)
            return 0;
        int min = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min)
                min = prices[i];
            else
                max = Math.max(max, prices[i] - min);
        }
        return max;
    }
}

买卖股票的最佳时机Ⅱ

力扣

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int ret = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                ret += prices[i] - prices[i - 1];
            }
        }
        return ret;
    }
}

种花问题

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 1)
                continue;
            int pre = 0, next = 0;
            if (i != 0)
                pre = flowerbed[i - 1];
            if (i != flowerbed.length - 1 )
                next = flowerbed[i + 1];
            if (pre == 0 && next == 0) {
                flowerbed[i] = 1;
                count++;
            }

        }
        return count >= n;
    }
}

判断子序列

力扣

1
2
3
4
5
6
7
8
9
10
public boolean isSubsequence(String s, String t) {
    int index = -1;
    for (char c : s.toCharArray()) {
        index = t.indexOf(c, index + 1);
        if (index == -1) {
            return false;
        }
    }
    return true;
}

非递减序列

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= nums[i - 1]) {
                continue;
            }
            count++;
            if (i - 2 >= 0 && nums[i - 2] > nums[i]) {
                nums[i] = nums[i - 1];
            } else {
                nums[i - 1] = nums[i];
            }
        }
        return count <= 1;
    }
}

最大子序和

力扣

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int ret = nums[0],sum = 0;
        for (int i = 0;i< nums.length;i++){
            sum += nums[i];
            ret = Math.max(sum,ret);
            if (sum < 0)
                sum = 0;
        }
        return ret;
    }
}

划分字母区间

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> list = new ArrayList<>();
        int start = 0,end = 0;
        while (true){
            for (int i = start;i <= end;i++){
                end = Math.max(S.lastIndexOf(S.charAt(i)),end);
            }
            list.add(end - start + 1);
            if (end == S.length() - 1){
                break;
            }
            else {
                start = ++end;
            }
        }
        return list;
    }
}