Java 贪心算法求解01串最小删除次数

给定一个仅由 '0' 和 '1' 组成的字符串，每次可以删除一个连续子串，要求子串字符相同。求最少删除多少次可以把字符串变成空串。

使用贪心算法可以解决这个问题。思路如下：

定义一个变量 count，用于记录删除的次数。
遍历字符串，如果当前字符与前一个字符相同，则不需要删除，继续遍历。
如果当前字符与前一个字符不同，则需要删除当前字符，将 count 加 1。
最后返回 count 即为最少删除次数。

以下是使用 Java 实现的代码：

public class Main {
    public static void main(String[] args) {
        String str = '100111001';
        int count = minDeletion(str);
        System.out.println(count);
    }
    
    public static int minDeletion(String str) {
        int count = 0;
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i) != str.charAt(i - 1)) {
                count++;
            }
        }
        return count;
    }
}

输出结果为：3，表示最少删除 3 次可以将 01 串变成空串。

代码解析：

minDeletion() 函数遍历字符串，比较相邻字符。
如果相邻字符不同，则需要删除当前字符，并将 count 加 1。
最终返回 count 即为最少删除次数。

总结：

本文介绍了使用 Java 贪心算法解决 01 串最小删除次数问题的思路和代码实现。通过遍历字符串，比较相邻字符，统计需要删除的次数，最终得到最少删除次数。