第十四届蓝桥杯集训——练习解题阶段(无序阶段)-贪心算法

​

 ​编辑

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-贪心算法

贪心算法简介

局部最优解->整体最优解，这是贪心算法的核心解释。

百度的官方解释是：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

其实都是一样的，我们最开始学习排序的时候使用了一种叫做选择排序的就是利用贪心(贪婪)算法来布局的。

​编辑

基础示例·选择排序·贪婪策略

        每次从数组后面还没有排序的数据中选取小的下标值挨个判断，连续比较那个最小，并把最小值放在未排序数据的起始位置，也就是比较的那个下标值，直到最后一个下标值，则本次排序结束，继续下一次循环。

package com.item.action;
public class Demo {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 12, 3, 12, 4, 1, 5, 4, 662, 2 };
		// 选择排序·贪心·贪婪
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if (arr[i] < arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		//遍历输出
		for (int i : arr) {
			System.out.print(i+",");
		}
	}
}

​编辑

力扣的分割平衡字符串题

下面是我去截的图，为了测试方便，我把示例的输入输出也复制过来。

​编辑

示例 1：

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

示例 2：

输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3：

输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR" 。

​编辑

代码

只要平衡，就立即分割(贪心策略)。

假设R== 1，L==-1。

只要累加等于0就算分割一次。

class Solution {
    public 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、只能满足一些特性的题目，没有一通变万法的能力。

综合来看，就是一个简单的小题目。

​