算法学习 | 贪心算法~通过局部最优的选择来得到整体最优解

目录

贪心算法

贪心算法相关OJ题

选择排序

​编辑 平衡字符串 

买卖股票的最佳时机 II 

跳跃游戏 

最多可以参加的会议数目 

---

贪心算法

· 贪心算法是指在对问题求解时总是做出在当时来看是最好的选择，也就是不考虑整体的最优，他所做的是在某种意义上的局部最优解，通过一系列的局部最优的选择来实现整体最优解.

· 贪心算法的基本思路是从问题的的某一个初始解出发一步一步的进行，根据某个优化测度，每一步都要确保能获得局部最优解.每一步只考虑一个数据，它的选取应满足局部优化的条件.如果下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完或者不能再添加算法停止

贪心算法的过程 

①建立数学模型来描述过程；

②把求解的问题分解成若干个子问题；

③对每一个子问题求解，得到子问题的局部最优解；

④把子问题的局部最优解合成原问题的一个解.

贪心算法存在的问题

· 不能保证求得的解是最佳的

· 不能用来求最大值或最小值的问题

· 只能求满足某些约束条件的可行解的范围 

贪心算法相关OJ题

选择排序

选择排序其实就是贪心思想，每次选取最小值放在未排序数据的起始位置，直至未排序数据为0为止

import java.util.Arrays;
public class Test {
    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 2, 6, 8, 7};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    private static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
}

 平衡字符串 

OJ链接：leetcode-1221.分割平衡字符串

在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。

返回可以通过分割得到的平衡字符串的最大数量 。

例如

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

本题根据贪心思想，只要达到平衡就对其进行分割，定义一个balance变量，初始值为0，遇到L，balance-1，遇到R，balance + 1，当balance为0时，就说明得到了一个分割，直到遍历完字符串为止.

class Solution {
    public int balancedStringSplit(String s) {
        int balance = 0;
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'L') {
                balance--;
            } else {
                balance++;
            }
            if (balance == 0) {
                count++;
            }
        }
        return count;
    }
}

买卖股票的最佳时机 II 

 OJ链接：leetcode-122.买卖股票的最佳时机 II

 题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有 一股 股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润 。

例如 

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

本题依据贪心策略，只要股票处于上涨期，就一直买卖，如果处于下跌期就不进行买卖，这样就不会亏本，只要第二天的股票价格大于第一天就进行买卖.

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

跳跃游戏 

OJ链接：leetcode-55.跳跃游戏 

题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

例如 

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

根据贪心策略，对于每一个位置x，计算其最远可到达的距离，例如[2,3,1,1,4]，其在下标为0的位置时，最远可到达的位置为x+nums[x]，即 0 + 2，其最远可到达距离为2，将其位置记录，其可以到达第二个位置，则继续更新最大可到达位置为1 + 3 = 4，此时更新最大可到达距离为4，此时已经可以到达最后一个下标，则返回true.

class Solution {
    public boolean canJump(int[] nums) {
        int rightMost = 0;
        for (int i = 0; i < nums.length; i++) {
            //如果可以到达当前位置，则更新最大可到达位置
            if (i <= rightMost) {
                rightMost = Math.max(rightMost, i + nums[i]);
                //如果最大可到达位置大于最大长度，则返回true
                if (rightMost >= nums.length - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

最多可以参加的会议数目 

OJ链接：leetcode-1353.最多可以参加的会议数目

题目描述

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。

请你返回你可以参加的 最大 会议数目。

 例如

输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。

对于此题，首先根据会议的开始时间对其进行排序，然后从第一天开始，将每一个会议区间的截止时间加入到优先级队列中(小根堆)，对每一天进行会议选择，选择截止时间最早的会议先参加，最终就可以得到最多参加会议数.

class Solution {
    public int maxEvents(int[][] events) {
        //按照会议开始时间排序
        Arrays.sort(events, (o1, o2) -> o1[0] - o2[0]);
        //定义小根堆，存放会议截至时间
        PriorityQueue heap = new PriorityQueue<>();
        int ret = 0;//记录结果
        int n = events.length;//总的会议数量
        int i = 0;//记录会议数
        int last = 1;//会议开始时间
        while (i < n || !heap.isEmpty()) {
            //将开始时间相同的会议截至时间放在优先级队列中
            while (i < n && events[i][0] == last) {
                heap.offer(events[i++][1]);
            }
            //将截至时间到了的会议去掉
            while (!heap.isEmpty() && heap.peek() < last) {
                heap.poll();
            }
            if (!heap.isEmpty()) {
                heap.poll();
                ret++;
            }
            last++;
        }
        return ret;
    }
}