第十四届蓝桥杯集训——练习解题阶段(无序阶段)-贪心算法
2023-03-07 09:06:20 时间
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-贪心算法
贪心算法简介
局部最优解->整体最优解,这是贪心算法的核心解释。
百度的官方解释是:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。
其实都是一样的,我们最开始学习排序的时候使用了一种叫做选择排序的就是利用贪心(贪婪)算法来布局的。
基础示例·选择排序·贪婪策略
每次从数组后面还没有排序的数据中选取小的下标值挨个判断,连续比较那个最小,并把最小值放在未排序数据的起始位置,也就是比较的那个下标值,直到最后一个下标值,则本次排序结束,继续下一次循环。
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、只能满足一些特性的题目,没有一通变万法的能力。
综合来看,就是一个简单的小题目。
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的