贪心算法（无规则）

1.easy

1.455. 分发饼干

链接: 455. 分发饼干

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

2.1005. K 次取反后最大化的数组和

链接: 1005. K 次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        //1.给数组排序
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(k>0&&nums[i]<0){//满足条件
                nums[i]=Math.abs(nums[i]);//将目前绝对值最大的负数变为正数
                k--;
            }else{//k==0或者没有负数了退出循环
                break;
            }
        }
        if(k%2==1){//如果剩余k的值为奇数，
            Arrays.sort(nums);//给当前全为正数的数组排序，
            nums[0]=-1*nums[0];//num[0]为最小值取反
        }
        return Arrays.stream(nums).sum();
    }
}

3.860. 柠檬水找零

链接: 860. 柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five=0,ten=0,twenty=0;
        for(int i:bills){
            if(i==5){
                five++;
            }else if(i==10){
                if(five==0){
                    return false;
                }else{
                    five--;
                    ten++;
                }
            }else if(i==20){
                if(five!=0&&ten!=0){
                    five--;
                    ten--;
                    twenty++;
                }else if(five>=3){
                    five-=3;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}

2.medium

1.序列问题

1.376. 摆动序列

链接: 376. 摆动序列

贪心解法

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        //当前差值
        int curDiff = 0;
        //上一个差值
        int preDiff = 0;
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            //得到当前差值
            curDiff = nums[i] - nums[i - 1];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff>0&&preDiff<=0)||(curDiff<0&&preDiff>=0)){
                res++;
                preDiff=curDiff;
            }
        }
        return res;
    }
}

2.738. 单调递增的数字

链接: 738. 单调递增的数字

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = Integer.MAX_VALUE;
        for(int i=s.length()-2;i>=0;i--){
            if(chars[i]>chars[i+1]){
                chars[i]--;
                start=i+1;
            }
        }
        for(int i=start;i<s.length();i++){
            chars[i]='9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

2.贪心解决股票问题

1.122. 买卖股票的最佳时机 II

链接: 122. 买卖股票的最佳时机 II

//2.贪心解法
class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        if(n==0){
            return 0;
        }
        int result=0;
        for(int i=1;i<n;i++){
            if(prices[i]-prices[i-1]>0){
                result+=prices[i]-prices[i-1];
            }
        }
        return result;
    }
}

//1.动态规划解法
// class Solution {
//     public int maxProfit(int[] prices) {
//         int n=prices.length;
//         if(n==0){
//             return 0;
//         }
//         int [][]dp=new int[n][2];
//         dp[0][0]=-prices[0];
//         dp[0][1]=0;
//         for(int i=1;i<n;i++){
               //持有股票
//             dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);//和1唯一不同
               //不持有股票
//             dp[i][1]=Math.max(dp[i-1][1],prices[i]+dp[i-1][0]);
//         }
//         return dp[n-1][1];
//     }
// }

3.两个维度权衡问题

1.135. 分发糖果

链接: 135. 分发糖果

class Solution {
    public int candy(int[] ratings) {
        /**
         分两个阶段
         1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
         2、起点下标 ratings.length-2 从右往左，只要左边比右边大，此时左边的糖果应该 取本身的糖果数（符合比它左边大）和右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
    */
        int candy[]=new int[ratings.length];
        candy[0]=1;
        for(int i=0;i<ratings.length-1;i++){
            if(ratings[i]<ratings[i+1]){//从左向右排
                candy[i+1]=candy[i]+1;
            }else{
                candy[i+1]=1;
            }
        }
        for(int i=ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){//从右向左排
                candy[i]=Math.max(candy[i],candy[i+1]+1);
            }
        }
        int ans = 0;
        for (int num : candy) {
            ans += num;
        }
        return ans;
    }
}

*2.406. 根据身高重建队列(linklist，labmda表达式)

链接: 406. 根据身高重建队列

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 身高从大到小排（身高相同k小的站前面）
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        LinkedList<int[]> que = new LinkedList<>();

        for (int[] p : people) {
            que.add(p[1],p);
        }

        return que.toArray(new int[people.length][]);
    }
}

3.hard

1.区间问题

1.55. 跳跃游戏

链接: 55. 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        //覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
        int cover=0;
        //在覆盖范围内更新最大的覆盖范围
        for(int i=0;i<=cover;i++){
            cover=Math.max(cover,i+nums[i]);
            if(cover>=nums.length-1){
                return true;
            }
        }
        return false;
    }
}

2.45. 跳跃游戏 II

链接: 45. 跳跃游戏 II

class Solution {
    public int jump(int[] nums) {
        int n=nums.length;
        if(n==1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for(int i=0;i<n;i++){
            // 更新下一步覆盖最远距离下标
            nextDistance = Math.max(nums[i] + i, nextDistance);  
            // 遇到当前覆盖最远距离下标
            if (i == curDistance) {                    
                // 如果当前覆盖最远距离下标不是终点     
                if (curDistance < n - 1) {       
                    ans++; // 需要走下一步
                    // 更新当前覆盖最远距离下标（相当于加油了）
                    curDistance = nextDistance;            
                    // 下一步的覆盖范围已经可以达到终点，结束循环 
                    if (nextDistance >= n - 1) 
                        break; 
                } else // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
                    break;                               
            }
        }
        return ans;
    }
}

3.452. 用最少数量的箭引爆气球

链接: 452. 用最少数量的箭引爆气球

/**
 * 时间复杂度 : O(NlogN)  排序需要 O(NlogN) 的复杂度
 * 空间复杂度 : O(logN) java所使用的内置函数用的是快速排序需要 logN 的空间
 */
class Solution {
    public int findMinArrowShots(int[][] points) {
        // 根据气球直径的开始坐标从小到大排序
        // 使用Integer内置比较方法，不会溢出
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        int count = 1;  // points 不为空至少需要一支箭
        for (int i = 1; i < points.length; i++) {
            // 气球i和气球i-1不挨着，注意这里不是>=
            if (points[i][0] > points[i - 1][1]) {  
                count++; // 需要一支箭
            } else {  // 气球i和气球i-1挨着
            // 更新重叠气球最小右边界
                points[i][1] = Math.min(points[i][1], points[i - 1][1]); 
            }
        }
        return count;
    }
}

4.435. 无重叠区间

链接: 435. 无重叠区间

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //按照左边界排序
        Arrays.sort(intervals, (a,b)-> {
            return Integer.compare(a[0],b[0]);
        });
        int remove = 0;
        int pre = intervals[0][1];//初始化最左边的区间最右边界为pre
        for(int i = 1; i < intervals.length; i++) {
            if(pre > intervals[i][0]) {//重叠
                remove++;
                pre = Math.min(pre, intervals[i][1]);
            }
            else pre = intervals[i][1];
        }
        return remove;
    }
}

5.763. 划分字母区间

链接: 763. 划分字母区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result=new ArrayList<>();
        int len=s.length();
        //记录每个字母最后出现的位置
        int hush[]=new int[27];
        for(int i=0;i<len;i++){
            hush[s.charAt(i)-'a']=i;
        }
        int right=0;
        int left=0;
        for(int i=0;i<len;i++){
            right=Math.max(right,hush[s.charAt(i)-'a']);
            if(i==right){// 找到字符出现的最远边界
                result.add(right-left+1);
                left=right+1;
            }
        }
        return result;
    }
}

6.56. 合并区间

链接: 56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
         List<int[]> res = new LinkedList<>();
        //按照左边界排序
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
        //initial start 是最小左边界
        int start = intervals[0][0];
        int mostRightIndex = intervals[0][1];
        for(int i=1;i<intervals.length;i++){
            //如果左边界大于最大右边界
            if(intervals[i][0]>mostRightIndex){
                res.add(new int[]{start,mostRightIndex});
                start=intervals[i][0];
                mostRightIndex=intervals[i][1];
            }else{//如果左边界小于最大右边界
                //更新最大右边界
                mostRightIndex = Math.max(mostRightIndex, intervals[i][1]);
            }
        }
        res.add(new int[]{start, mostRightIndex});
        return res.toArray(new int[res.size()][]);
    }
}

2.其他

1.53. 最大子数组和

链接: 53. 最大子数组和

贪心解法

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
            if (count <= 0){
                count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            }
        }
       return sum;
    }
}

动态规划

class Solution {
    /**
     * 1.dp[i]代表当前下标对应的最大值
     * 2.递推公式 dp[i] = max (dp[i-1]+nums[i],nums[i]) res = max(res,dp[i])
     * 3.初始化 都为 0
     * 4.遍历方向，从前往后
     * 5.举例推导结果。。。
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int res = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = res > dp[i] ? res : dp[i];
        }
        return res;
    }


}

2.134. 加油站

链接: 134. 加油站
文章来源地址https://www.toymoban.com/news/detail-456929.html

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
                index = (i + 1) % gas.length ; 
                curSum = 0;
            }
        }
        if (totalSum < 0) return -1;
        return index;
    }
}

到了这里，关于贪心算法（无规则）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！