java实现贪心算法代码示例

什么是贪心算法？

贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。

算法思路
贪心算法一般按如下步骤进行：
①建立数学模型来描述问题 。
②把求解的问题分成若干个子问题。
③对每个子问题求解，得到子问题的局部最优解。
④把子问题的解局部最优解合成原来解问题的一个解。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。

存在问题
贪心算法也存在如下问题：
1、不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑；
2、贪心算法一般用来解决求最大或最小解；
3、贪心算法只能确定某些问题的可行性范围 。

示例：
在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。
输入：s = “RLLLLRRRLR”
输出：3
解释：s 可以分割为 “RL”、“LLLRRR”、“LR” ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。

测试代码：

package com.atguigu.common.utils;


/**
 * @ClassName Solution
 * @Description: 在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。
 *
 * 给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
 *
 * 注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
 *
 * 返回可以通过分割得到的平衡字符串的 最大数量 。
 *
 * 输入：s = "RLLLLRRRLR"
 * 输出：3
 * 解释：s 可以分割为 "RL"、"LLLRRR"、"LR" ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。
 *
 * 解题思路: 不要有嵌套的平衡，只要达到平衡，就立即分割(贪心策略).我们假设 ‘R’ == 1, ‘L’ == -1 .只要累加等于 0 就算分割一次.
 * @Author: mischen
 * @date: 19:57 2022/12/5
 * @Version 1.0
 */
public class Solution {

    public static void main(String[] args) {
        String string = "RLLLLRRRLR";
        System.out.println(balancedStringSplit(string));
        String strin = "LLLLRRRR";
        System.out.println(balancedStringSplit(strin));
        String strin1 = "RLRRRLLRLL";
        System.out.println(balancedStringSplit(strin1));
    }

    public static int balancedStringSplit(String s) {
        int cnt = 0;
        int balance = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == 'L'){
                balance--;
            }
            if(s.charAt(i) == 'R'){
                balance++;
            }
            if(balance == 0){
                cnt++;
            }
        }
        return cnt;
    }
}

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
43
44
45
46
47
48
49
50
51