【代码随想录】贪心算法专栏（java版本含注释）

前言

所谓的贪心算法，就是局部最优到全局最优

关于该算法的学习路线如下：
代码随想录的贪心算法路线

455. 分发饼干（简单）

题目：leetcode：455. 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int m=g.length;
        int n=s.length;
        
        int sum=0;

        for(int i=m-1,j=n-1;i>=0&&j>=0;i--,j--){

            //此处为移动小孩的位置，大胃口移除，在while中要多加一个i大于等于0，防止数组越界
            while(i>=0 && g[i]>s[j])i--;
            
            //不能通过这种方式进行比较，因为上一个i--，可能会导致数组的越界
            //if(g[i]<=s[j])sum++;

            //默认就是g[i]<=s[j]，所以只需i与j数组不越界即可sum++
            if(i>=0&&j>=0)sum++;
            

            
        }

        return sum;

    }
}
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 findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);


        int sum=0;

        for(int i=g.length-1,j=s.length-1;i>=0&&j>=0;i--){
            if(g[i]<=s[j]){
                j--;
                sum++;
            }
        }
     return sum;   
    }
}
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 sum=0;

        for(int i=0,j=0;i<g.length&&j<s.length;++j){
            if(g[i]<=s[j]){
                ++i;
                sum++;
            }
        }
     return sum;   
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

376. 摆动序列（中等）

题目：leetcode：376. 摆动序列

动态规划的做法：

class Solution {
    public int wiggleMaxLength(int[] nums) {

        int n=nums.length;
        //比较的是摆动序列的上升和下降最后的值，可以不通过dp数组进行存储
        //只需用两个变量进行迭代即可

        //默认一个数字就有个1
        int up=1,down=1;
        for(int i=1;i<n;i++){
            //每一次的up和down都会被上一个影响到，所以直接使用if else
            if(nums[i]>nums[i-1]){
                up=down+1;
            }else if(nums[i]<nums[i-1]){
                down=up+1;
            }

        }


        //输出最后两者的最大值即可
        return Math.max(up,down);

    }
}
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 wiggleMaxLength(int[] nums) {

        int n=nums.length;

        //当前的差值        
        int cur=0;
        //上一个的差值
        int pre=0;

        //默认第一个的sum为1
        int sum=1;
        for(int i=1;i<n;i++){
            //计算当前差值
            cur=nums[i]-nums[i-1];

            //判定的条件通过模拟算法
            //如果当前差值大于0，而且上一个差值小于等0，则sum+1，以及将其当前差值赋值给上一个差值，另一种情况同理
            if(( cur > 0 && pre <= 0) || (cur < 0 && pre >= 0)){
                sum++;
                pre=cur;
            }
        }
        
        return sum;
    }
}
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

53. 最大子数组和（简单）

题目：leetcode：53. 最大子数组和

贪心算法：

class Solution {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        if(n==1)return nums[0];

        //此处之所以定义为0，如果值为-2，-1，可能最后的返回值就是0
        //所以将其定义为Integer.MIN_VALUE
        int sum=Integer.MIN_VALUE; //-2,-1

        //用来计数，保证子数组之和的count要时刻大于0，如果小于0，则重新开始计数
        int count=0;
        for(int i=0;i<n;i++){
            count+=nums[i];
            //每次都保留sum的最大值
            sum=Math.max(sum,count);
            if(count<=0)count=0;
        }

        //返回最后的sum最大值即可
        return sum;

        

    }
}
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 maxSubArray(int[] nums) {
        int n=nums.length;
        if(n==1)return nums[0];

        int pre=0;
        int max=Integer.MIN_VALUE;//或者使用nums【0】来保存其开始的值

        for(int i = 0;i < n;i++){
            //刚开始pre保存的值：按照顺序的子数组较大的值，如果小于相加的数，则说明开始大规模减少，则重开，变为nums【i】
            //如果前边累加后还不如自己本身大，那就把前边的都扔掉，从此自己本身重新开始累加。
            pre=Math.max(nums[i],pre+nums[i]);
            //不用dp数组，是因为只要保存最后的总值即可，所以通过max保存每个值的迭代即可
            max=Math.max(max,pre);
        }

        return max;

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

分治算法：

class Solution {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        if(n==0)return 0;

        return getMax(nums,0,n-1);
    }

    public int getMax(int []nums,int left,int right){
        if(left==right)return nums[left];

        int mid=(left+right)/2;
        
        // 求左数组的最大和
        int leftmax=getMax(nums,left,mid);
        //右
        int rightmax=getMax(nums,mid+1,right);
        //跨越
        int midmax=crossMax(nums,left,mid,right);

        return Math.max(leftmax,Math.max(midmax,rightmax));
    }

    public int crossMax(int []nums,int left,int mid,int right){

        int sum=0;
        int leftSum=Integer.MIN_VALUE;
        for(int i=mid;i>=left;i--){
            sum+=nums[i];
            if(sum>leftSum)leftSum=sum;
        }

        sum=0;
        int rightSum=Integer.MIN_VALUE;
        for(int i=mid+1;i<=right;i++){
            sum+=nums[i];
            if(sum>rightSum)rightSum=sum;
        }

        return leftSum+rightSum;
    }
}
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

122. 买卖股票的最佳时机 II（中等）

题目：leetcode：122. 买卖股票的最佳时机 II

动态规划：

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        
        //定义数组的时候不要越界
        int [][]dp=new int[n][2];
        //dp[0][0]不持有股票，dp[0][1]持有股票
        dp[0][0]=0;
        //持有股票数是买了，所以资金为负数
        dp[0][1]=-prices[0];
        for(int i=1;i<n;i++){
            //不持有，可能昨天就没有，以及昨天持有今天已经卖了（加上今天的收益）
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            //持有，可能昨天就还有（没卖）以及昨天不持有入股买了一个（买到的要减去收益）
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }

        //全部交易结束后，持有股票的收益一定低于不持有股票的收益
        return dp[n-1][0];


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

贪心算法：

这题的思路比较巧妙，只需要算起上坡值即可

class Solution {
    public int maxProfit(int[] prices) {

        int n=prices.length;
        int sum=0;

        for(int i=1;i<n;i++){
            if(prices[i]>prices[i-1])
            sum+=(prices[i]-prices[i-1]);
        }
        return sum;

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

55. 跳跃游戏（中等）

题目：leetcode：55. 跳跃游戏

贪心算法：

class Solution {
    public boolean canJump(int[] nums) {
        int n=nums.length;
        //可以跳动的最远距离位置
        int range=0;
        for(int i=0;i<n;i++){
            //每一次的跳动都要判定当前位置是否和最远距离的比较
            //如果当前位置比最远距离小，则还可以继续走动，如果已经超出了最远距离则直接返回false
            if(i<=range){
                //保存每个值的最远距离，在进入条件的时候要比较
                range=Math.max(i+nums[i],range);
                //提前到达n-1数组这个位置则直接返回true
                if(range>=n-1)return true;
            }
            
        }
        return false;

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

45. 跳跃游戏 II（中等）

题目：leetcode：45. 跳跃游戏 II

class Solution {
    public int jump(int[] nums) {

        int n=nums.length;
        
        int nextdistance=0;
        int step=0;
        int curdistance=0;

        //本身默认是可以到达最后一个位置的，所以只需要遍历数组到倒数第一个即可
        //不然更新到最后一个位置的时候，条件处理会多一个step++
        for(int i=0;i<n-1;i++){
            //更新每个下标的最远距离
            nextdistance=Math.max(nextdistance,i+nums[i]);
            //如果遇到当前最远距离的下标
            if(curdistance==i){
                //则在这一范围内，将其当前距离的最远下标更换为 下一个下标的最远距离
                curdistance=nextdistance;
                step++;
            }
        }
        return step;

    }
}
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

如果遍历到n的话，则执行条件如下：

class Solution {
    public int jump(int[] nums) {
        
        //要多一个初值条件的判定，示例为0的时候输出为0，而不是1，本身就不用跳了
         if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }

        int n=nums.length;
        
        int nextdistance=0;
        int step=0;
        int curdistance=0;

        //此处的循环条件为n，则在内部条件中要多一个判定
        for(int i=0;i<n;i++){
            //更新每个下标的最远距离
            nextdistance=Math.max(nextdistance,i+nums[i]);
            
            //当前一步，再跳一步就到达了末尾
            if (nextdistance>=n-1){
                step++;
                break;
            }

            //如果遇到当前最远距离的下标
            if(curdistance==i){
                //则在这一范围内，将其当前距离的最远下标更换为 下一个下标的最远距离
                curdistance=nextdistance;
                step++;
            }
        }
        return step;

    }
}
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

两者区别：

• 如果遍历到n-1，内部条件每次都要判定是不是到最后一个节点，就step++，直接退出循环
• 如果遍历到n-2，则内部不需要判定是不是最后一个，而且也不用遍历最后一个，因为最后一个本身就到达位置了，不用在step++。只要在倒数第二个的时候等于当前最远距离，最少为1，也会step++（本身就确保可以到达最后一个）

1005. K 次取反后最大化的数组和（简单）

题目：leetcode：1005. K 次取反后最大化的数组和

贪心的模拟算法：

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int count = 0;
        for(int i = 0; i < nums.length;i++){
            if(k > 0 && nums[i] < 0){
                nums[i] = -nums[i];
                k--;
            }
            // 不弄在上面相加，因为如果是正数不好加
            count += nums[i];
        }

        Arrays.sort(nums);
        // 一开始 count统计的时候已经加过一个nums，所以此处要 *2
        return count - (k%2 == 0 ? 0 : 2*nums[0]); 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

134. 加油站（中等）

题目：leetcode：134. 加油站

（思路点来源与 代码随想录，分门别类，还是很容易记住）

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        int ret = 0;
        for(int i = 0;i < gas.length;i++){
            sum += (gas[i] - cost[i]);
            // 比较每次的值，如果最小的的值，都不是0，则起点在0
            ret = Math.min(sum,ret);
        }

        if(ret >= 0)return 0;
        //无法走一圈
        if(sum < 0) return -1;

        // 此处为累加的最小负值
        //System.out.println(ret);

        // 查找不是从0起点开始的
        for(int i = gas.length - 1;i > 0;i--){
            // 对应如果可以把这个负值 填平，说明起始点就是位置
            ret += (gas[i] - cost[i]);
            if(ret >= 0)return i;
        }

        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

另外一种全局思路来定贪心算法：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalsum = 0;
        int cursum = 0;
        int start = 0;
        for(int i = 0;i < gas.length;i++){
            totalsum += (gas[i] - cost[i]);
            cursum += (gas[i] - cost[i]);
            // 累加cursum，如果出现小于0，则更新起始位置为i+1。剩余量的总油耗值
            if(cursum < 0){
                start = i + 1;
                cursum = 0;
            }
        }
        // 所有加起来都小于0，那就直接返回-1
        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

135. 分发糖果（困难）

题目：leetcode：135. 分发糖果

class Solution {
    public int candy(int[] ratings) {
        int[] candynum = new int[ratings.length];
        // 设置一个初始化的数字
        candynum[0] = 1;

        // 从左往右遍历，如果左边大于右边，则多前面
        for(int i = 1; i < ratings.length;i++){
            if (ratings[i] > ratings[i - 1]){
                // 不可直接设置为2，要通过前面的的进行贪心
                candynum[i] = candynum[i - 1] + 1;
            }else {
                candynum[i] = 1;
            }
        }

        // 从右往前遍历，利用右边大于左边
        for(int i = ratings.length - 2;i >= 0;i--){
            if(ratings[i] > ratings[i + 1]){
                candynum[i] = Math.max(candynum[i],candynum[i + 1] + 1);
            }
        }

        int ans = 0;
        for (int s : candynum){
            ans += s;
        }
        return ans;
    }
}
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

860. 柠檬水找零（简单）

题目：leetcode：860. 柠檬水找零

单独对其进行模拟算法

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for(int i = 0;i < bills.length;i++){
            if(bills[i] == 5){
                five++;
            }else if(bills[i] == 10){
                five--;
                ten++;
            }else if(bills[i] == 20){
                if(ten > 0){
                    ten--;
                    five--;
                // 注意此处不需要在多一个判断 five > 0
                // five 可能会等于0 直接在每一层的最后进行判断即可
                }else {
                    five -= 3;
                }
            }
            if(five < 0 || ten < 0)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
26

406. 根据身高重建队列（中等）

题目：leetcode：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[]> list = new ArrayList<>();
        for(int []p : people){
            // 将其p[1] 这个index的元素添加到p集合种
            list.add(p[1],p);
        }

        return list.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

对应数组的排序进行改写

Arrays.sort(people, new Comparator<int[]>() {
    public int compare(int[] person1, int[] person2) {
        if (person1[0] != person2[0]) {
            return person2[0] - person1[0];
        } else {
            return person1[1] - person2[1];
        }
    }
});
1
2
3
4
5
6
7
8
9

452. 用最少数量的箭引爆气球（中等）

题目：leetcode：452. 用最少数量的箭引爆气球

class Solution {
    public int findMinArrowShots(int[][] points) {

        // 此处数组的排序 将其有边界对应进行排序
        // 此为排序右边界的范围数组，从小到大
        Arrays.sort(points,new Comparator<int[]>(){
            public int compare(int[] points1,int []points2){
                if(points1[1] > points2[1])return 1;
                else if(points1[1] < points2[1]) return -1;
                else return 0;
            }
        });

        int m = points.length;
        // 标记右边界的值
        int right = points[0][1];
        // 默认初始值是1
        int sum = 1;

        for(int i = 1;i < m;i++){
            // 下一个左边界的值 如果大于前一个有边界的值，则sum++
            if(points[i][0] > right){
                sum++;
                right = points[i][1];
            }
        }
        return sum;
    }
}
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

补充关于Arrays.sort的排序：

Arrays.sort(int[],Comparator)这个api，需要返回一个int类型的值，一般会直接使用两数相减来直接得出这两个数的相对顺序，如果大数据的时候会溢出

Arrays.sort(points,new Comparator<int []>(){
            public int compare(int[] points1,int []points2){
                return points1[1]-points2[1];
            }
        });
1
2
3
4
5

具体使用下标0还是下标1排序，主要看用的左边界排序还是右边界排序

正确的格式防止溢出可看以下：
为此可使用三目运算符

Arrays.sort(points,new Comparator<int []>(){
            public int compare(int[] points1,int []points2){
                if(points1[1]>points2[1])return 1;
                else if(points1[1]<points2[1])return -1;
                else return 0;
            }
        });

//或者lambda表达式
Arrays.sort(points, (p1, p2) -> p1[1] < p2[1] ? -1 : 1);
1
2
3
4
5
6
7
8
9
10

或者使用如下：Integer.compare(int,int)

Arrays.sort(points,(o1,o2)->Integer.compare(o1[1],o2[1]));
1

以上的条件都是用的右边界，如果使用左边界，注意边界条件：

class Solution {
    public int findMinArrowShots(int[][] points) {

        //此为排序右边界的范围数组，从小到大
        Arrays.sort(points,new Comparator<int []>(){
            public int compare(int[] points1,int []points2){
                if(points1[0]>points2[0])return 1;
                else if(points1[0]<points2[0])return -1;
                else return 0;
            }
        });

        int m=points.length;
        int right=points[0][1];
        int sum=1;
        for(int i=1;i<m;i++){
            if(points[i][0]>right){
                sum++;
                right=points[i][1];
                //这个条件必须加上，否则会出错
                //因为右边界没有排序，需要更新一下最右边界的最远距离
            }else{
                right=Math.min(points[i][1],right);
            }
            
        }

        return sum;
    }
}
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

435. 无重叠区间（中等）

题目：leetcode：435. 无重叠区间

此题与上一题的区别在于

• 弓箭数量要的是非交叉区间的数量
• 此题相领区间也可算上，只需大于等于即可，求无重叠的那个区间，只需要总数减去弓箭数即可

贪心算法：

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
         //本身Arrays的排序为Integer类型，所以完整修改Comparator函数中的compare方法
        Arrays.sort(intervals,new Comparator<int []>(){
            public int compare(int[] intervals1,int[] intervals2){
                return intervals1[1] - intervals2[1];
            }
        });

        int m = intervals.length;
        int right = intervals[0][1];
        int sum = 1;

        for(int i = 1;i < m;i++){
            //如果下一个边界的左边大于等于上一个边界的右边，则sum++
            if(intervals[i][0] >= right){
                sum++;
                right = intervals[i][1];
            }
        }

        //使用否命题，所以用m减去即可
        return m - sum;
    }
}
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 eraseOverlapIntervals(int[][] intervals) {
         //本身Arrays的排序为Integer类型，所以完整修改Comparator函数中的compare方法
        Arrays.sort(intervals,new Comparator<int []>(){
            public int compare(int[] intervals1,int[] intervals2){
                return intervals1[0] - intervals2[0];
            }
        });

        int m = intervals.length;
        int right = intervals[0][1];
        int sum = 1;

        for(int i = 1;i < m;i++){
            //如果下一个边界的左边大于等于上一个边界的右边，则sum++
            if(intervals[i][0] >= right){
                sum++;
                right = intervals[i][1];
            }else {
                //右边界取最小的一个，因为一处区间的最小数量， 所以范围小一些的剔除
                right = Math.min(intervals[i][1],right);
            }
        }

        //使用否命题，所以用m减去即可
        return m - sum;
    }
}
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

补充知识点：

Arrays.sort(intervals,(a,b)->{
            return Integer.compare(a[0],b[0]);
        });

//或者
 Arrays.sort(intervals,new Comparator<int []>(){
            public int compare(int[] intervals1,int[] intervals2){
                return intervals1[1]-intervals2[1];
            }
        });
1
2
3
4
5
6
7
8
9
10

763. 划分字母区间（中等）

题目：leetcode：763. 划分字母区间

数组（耗时4ms）

//遍历所有的字母，找到该字母的最远边界，就是一个片段

/*
思路：统计每个字母中的最远位置，将其跟下标标记在一起，如果该字母与下标吻合，说明为分割点
*/
class Solution {
    public List<Integer> partitionLabels(String s) {

        int []last=new int[26];
        //将其字母依次更新，使其该字母为最远的字母
        for(int i=0;i<s.length();i++){
            last[s.charAt(i)-'a']=i;
        }

        List<Integer>list=new ArrayList<>();
        
        int start=0,end=0;
        for(int i=0;i<s.length();i++){
            //时刻更新尾节点，如果该节点等同于下标，则list添加
            end=Math.max(end,last[s.charAt(i)-'a']);
            if(end==i){
                list.add(end-start+1);
                start=end+1;
            }
        }

        return list;

    }
}
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

如果使用哈希表的话，耗时8ms

class Solution {
    public List<Integer> partitionLabels(String s) {
        Map<Character,Integer> map = new HashMap<>();
        // 将其字母更新到最远的下表位置
        for(int i = 0;i < s.length();i++){
            map.put(s.charAt(i),i);
        }

        List<Integer> list = new ArrayList<>();
        // 定义start 以及 end 
        int start = 0;
        int end = 0;
        for(int i = 0;i < s.length();i++){
            // 时刻获取该元素的下标值，赋值给end
            end = Math.max(end,map.get(s.charAt(i)));
            // 如果相等则添加list，并且更新start值
            if(end == i){
                list.add(end - start + 1);
                start = end + 1;
            }
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

56. 合并区间（中等）

题目：leetcode：56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {

        if(intervals.length == 0)return new int[][]{};

        int m = intervals.length;
        //比较左边界的
        Arrays.sort(intervals,(o1,o2) -> (o1[0] - o2[0]));

        int [][]dp = new int[m][2];
        int left = intervals[0][0];
        int right = intervals[0][1];
        int index = 0;

        /*
        合并区间需要保存上一个值以及记录当前值
        如果左边节点小于等于上一个的右边节点，则不断更新右边节点的最大值
        如果左边节点大于上一个的右边节点，则更新dp数组的上一个值，以及记录当前的左边节点以及右边节点
        遍历完之后，还需要输出记录下的左边节点以及有边节点
        */ 
        for(int i = 1;i < m;i++){
            if(intervals[i][0] > right){
                dp[index][0] = left;
                dp[index][1] = right;
                index++;
                left = intervals[i][0];
                right = intervals[i][1];
                

            }else {
                right = Math.max(intervals[i][1],right);
            }
            
        }
        dp[index][0] = left;
        dp[index][1] = right;

        return Arrays.copyOfRange(dp,0,index+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
41

使用list列表

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
            //或者
            //return new int[0][2];
        }

        Arrays.sort(intervals,(o1,o2)->Integer.compare(o1[0],o2[0]));

        List<int[]> list = new ArrayList<>();

        for (int i = 0; i < intervals.length; ++i) {
            //每次遍历的时候记住左右位置
            int L = intervals[i][0], R = intervals[i][1];

            //如果列表为0，记录第一个数|| 左边界大于上一个的右边界，则添加
            if(list.size()==0 || list.get(list.size()-1)[1]<L){
                list.add(new int[]{L,R});
                //如果左边界小于等于上一个的右边界，则合并，但不着急合并，只需要记住R位置即可，更新list最后一个的右边界即可
            }else{
                list.get(list.size()-1)[1]=Math.max(R,list.get(list.size()-1)[1]);
            }
        }

        //列表转换为数组
        return list.toArray(new int[list.size()][]);

    }
}
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

738. 单调递增的数字（中等）*

题目：leetcode：738. 单调递增的数字

class Solution {
    public int monotoneIncreasingDigits(int n) {
        //char []c =Integer.toString(n).toCharArray();
        char []c =String.valueOf(n).toCharArray();

        int i=1;
        while(i<c.length && c[i-1]<=c[i]){
            i++;
        }
        if(i==c.length)return n;
        //之所以用while，因为233332 变为223332在变为229999，这样子中途会有递增的某个数，不满足递增的关系
        //因此都让其保持递增的关系
        while(i>0 && c[i-1]>c[i]){
            c[i-1]-=1;
            i--;
        }
        for(i+=1;i<c.length;i++){
            c[i]='9';
        }

        //将其数字转换为字符串
        return Integer.parseInt(new String(c));
    
    }
}
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

714. 买卖股票的最佳时机含手续费（中等）*

题目：714. 买卖股票的最佳时机含手续费

此题标*，主要是贪心算法这一块

卖出时候的费用条件区别：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n=prices.length;
        int [][]dp=new int[n][2];

        // 0为持有股票买入
        //  fee先不着急付，在卖出的时候在付
        dp[0][0]=-prices[0];

        for(int i=1;i<n;i++){
            // 1.昨天也持有；2. 昨天不持有，今天买入。两者取较大值。
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            // 卖出的时候 付fee的费用
            //1. 昨天也不持有；2. 昨天持有，今天卖出。两者取较大值。
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
        }

        return dp[n-1][1];

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

买入的时候费用 条件区别：

class Solution {
    public int maxProfit(int[] prices, int fee) {

        int n=prices.length;
        int [][]dp=new int[n][2];

        dp[0][0]=-prices[0]-fee;

        for(int i=1;i<n;i++){
            //买入
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]-fee);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }

        return dp[n-1][1];

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

贪心算法：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        
        /**
        此题的贪心算法比较难想
        在买入的时候就把费用加入
         */
        int n=prices.length;
        int buy=prices[0]+fee;
        int sum=0;
        for(int i=1;i<n;i++){
            //如果隔天的买入价格比较小，则将其小的买入价格更新。而且此处还可以反悔，发现价格不行了，buy会重新更新
            if(prices[i]+fee<buy){
                buy=prices[i]+fee;

                //如果隔天的价格比买入的价格要大，说明要涨，则利益加上
            }else if(prices[i]>buy){
                sum+=prices[i]-buy;
                //但是隔天的隔天可能还是涨，这里比较关键，使用buy不用费用的存储价格，如果隔天价格不行，可以反悔
                buy=prices[i];
            }
        }
        return sum;
    }
}
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

968. 监控二叉树（困难）*

题目：leetcode：968. 监控二叉树