贪心算法-点灯问题

1、题目描述
给定一个字符串str,只由 ‘X’ 和 ‘.’ 两种字符构成。‘X’ 表示墙,不能放灯,点亮不点亮都可;’.’ 表示居民点,可以放灯,需要点亮。如果灯放在i位置,可以让 i-1,i 和 i+1 三个位置被点亮。返回如果点亮str中所有需要点亮的位置,至少需要几盏灯。

2、解题思路
这题我们可以用谈心思想 分情况来去讨论:
(1)i 位置是 'X’,不管,来到 i + 1位置
(2)i 位置是 ‘.’ ,i + 1是 'X’,i 位置需要放灯,来到 i + 2位置
(3)i 位置是 ‘.’ ,i + 1是 ‘.’,i + 2是 ‘.’,i + 1 位置需要放灯,来到 i + 3位置(此步即是贪心)
(4)i 位置是 ‘.’ ,i + 1是 ‘.’,i + 2是 'X’,i 或 i + 1 位置需要放灯,来到 i + 3位置

代码实现:

	public static int minLight2(String road) {char[] str = road.toCharArray();int i = 0;int light = 0;while (i < str.length) {if (str[i] == 'X') {i++;} else {light++;if (i + 1 == str.length) {break;} else { // 有i位置 i+ 1 X .if (str[i + 1] == 'X') {i = i + 2;} else {i = i + 3;}}}}return light;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/142132.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

C语言连接MySQL并执行SQL语句(hello world)

1.新建一个控制台项目 参考【VS2022 和 VS2010 C语言控制台输出 Hello World】VS2022 和 VS2010 C语言控制台输出 Hello World_vs2022源文件在哪_西晋的no1的博客-CSDN博客 2.安装MySQL 参考【MySQL 8.0.34安装教程】MySQL 8.0.34安装教程_西晋的no1的博客-CSDN博客 3.复制MySQ…

Unity Bolt模块间通信

使用Bolt无代码设计开发的时候&#xff0c;我们不能简单的认为只需要一个FlowMachine就可以完成所有流程的开发。我们需要不同的模块进行拆分&#xff0c;以便更好的管理和协作。这就需要不同模块之间的通信处理。经过研究与使用&#xff0c;将常用的通信方式总结如下&#xff…

基于微信小程序的校园餐饮配送系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言学生微信小程序端的主要功能有&#xff1a;配送员微信小程序端的主要功能有&#xff1a;商家微信小程序端的主要功能有&#xff1a;管理员的主要功能有&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&am…

自定义类型

目录 1.结构体 1.结构体声明 1.1结构的基础知识 1.2结构的声明 1.3特殊的声明 1.4结构的自引用 1.5结构体变量的定义和初始化 1.6结构体的内存对齐 1.7修改默认对齐数 1.8结构体传参 2.位段 2.1什么是位段 2.2位段的内存分配 2.3位段的跨平台问题 2.4位段的应用 …

YOLOv5、YOLOv8改进:CotNet Transformer

1.简介 京东AI研究院提出的一种新的注意力结构。将CoT Block代替了ResNet结构中的3x3卷积&#xff0c;在分类检测分割等任务效果都出类拔萃 论文地址&#xff1a;https://arxiv.org/pdf/2107.12292.pdf 源代码地址&#xff1a;https://github.com/JDAI-CV/CoTNet 具有自注意…

Android开发之状态栏的设置

Android页面开发通常是根据UI设计进行&#xff0c;真机会遇到顶部状态栏和页面背景色或背景图片不协调的情况&#xff0c;这时候需要对状态栏进行设置。默认状态栏是有固定高度和背景色的&#xff0c;基本上我们需要将状态栏背景色设置透明并且图标能够在页面显示&#xff0c;下…

【力扣-每日一题】LCP 06. 拿硬币

class Solution { public:int minCount(vector<int>& coins) {int res0;for(auto i:coins){resi/2;res(i%2)?1:0;}return res;} };

多数据源Pagehelper怎么配置

1.遇到的问题 若依增加多数据源&#xff0c;分页报错&#xff0c;查了下pagehelper也要修改配置。 官方配置&#xff1a; 官方文档&#xff1a;连接多数据源sqlServer使用分页的情况下报错&#xff0c;不使用分页时正常。 Issue #I3NJMR 若依/RuoYi - Gitee.com 我的配置&a…

HCIE-容器docker

1、安装配置操作系统&#xff0c;使用CentOS stream 8镜像 之前&#xff1a;RHEL 8.4 发布了&#xff0c;CentOS紧随其后&#xff0c;发布CentOS 8.4 之后&#xff1a;CentOS 走在前面&#xff0c;成为RHEL上游&#xff0c;再去发布RHEL 制作模板&#xff0c;模板配置要求&…

Shader中的渲染路径LightMode

文章目录 前言一、在Shader中如何区分不同的渲染路径1、Pass Tag2、LightMode的不同类型 二、在Frame Debug下查看渲染路径之间的区别1、在摄像机可以切换渲染路径2、前向渲染路径3、延迟渲染路径4、顶点照明渲染路径&#xff08;可以看出效果很差&#xff09; 前言 Shader中的…

Leetcode 95. 不同的二叉搜索树 II

文章目录 题目代码&#xff08;9.21 首刷看解析&#xff09; 题目 Leetcode 95. 不同的二叉搜索树 II 代码&#xff08;9.21 首刷看解析&#xff09; class Solution { public:vector<TreeNode*> generateTrees(int n) {return build(1,n);}vector<TreeNode*> bu…

腾讯mini项目-【指标监控服务重构】2023-08-28

今日已办 分工 测试 - 谢雨晨、郑兆隆将1的测试结果记录整理为一个表格&#xff0c;列有&#xff1a;平均内存、最大内存、95内存、cpu的这些等等 - 邓烨钒HyperScan和官方正则库的benchmark对比 - 张锐添PPT制作 - 其他人灵活调动 进度 trace上报&#xff1a;jaeger-colle…

【Linux】【网络】传输层协议:TCP

文章目录 TCP 协议1. TCP 协议段格式2. TCP 报头解析3. TCP 的可靠性4. 面向字节流5. 粘包问题6. 连接队列维护 TCP 的 确认应答机制TCP 的 超时重传机制TCP 的 三次握手TCP 的 四次挥手setsockopt 函数&#xff1a;设置套接字选项&#xff0c;解决 TIME_WAIT 状态引起的 bind …

基于jquery开发的Windows 12网页版

预览 https://win12.gitapp.cn 首页代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"refresh" content"0;urldesktop.html" /> <meta name"viewport&…

NPDP产品经理认证怎么报名?考试难度大吗?

PMDA&#xff08;Product Development and Management Association&#xff09;是美国产品开发与管理协会&#xff0c;在中国由中国人才交流基金会培训中心举办NPDP&#xff08;New Product Development Professional&#xff09;考试&#xff0c;该考试是产品经理国际资格认证…

python+vue驾校驾驶理论考试模拟系统

管理员的主要功能有&#xff1a; 1.管理员输入账户登陆后台 2.个人中心&#xff1a;管理员修改密码和账户信息 3.用户管理&#xff1a;管理员可以对用户信息进行添加&#xff0c;修改&#xff0c;删除&#xff0c;查询 4.添加选择题&#xff1a;管理员可以添加选择题目&#xf…

upload-labs靶场未知后缀名解析漏洞

upload-labs靶场未知后缀名解析漏洞 版本影响&#xff1a; phpstudy 版本&#xff1a;5.2.17 ​ 1 环境搭建 1.1 在线靶场下载&#xff0c;解压到phpstudy的www目录下&#xff0c;即可使用 https://github.com/c0ny1/upload-labs1.2 已启动&#xff1a;访问端口9000&…

lS1028 + 六网口TSN 硬交换+QNX/Linux实时系统解决方案在轨道交通系统的应用

lS1028 六网口TSN 硬交换QNX/Linux实时系统解决方案在轨道交通系统的应用 以下是在轨道交通应用的实物&#xff1a; CPUNXP LS1028A架构双核Cortex-A72主频1.5GHzRAM2GB DDR4ROM8GB eMMCOSUbuntu20.04供电DC 12V工作温度-40℃~ 80℃ 功能数量参数Display Port≤1路支持DP1.3…

WebDAV之葫芦儿·派盘+NMM

推荐一款文件管理器,可以对手机中的文件进行多方面的管理,支持语法高亮和ftp等远程的文件的管理。支持从WebDav服务器连接葫芦儿派盘服务下载文件和上传文件。 NMM文本编辑器是一款文件管理器,在功能上面更加的适合于一些编程人员进行使用,需要在手机上面进行各种代码编辑的…

HarmonyOS 4.0 实况窗上线!支付宝实现医疗场景智能提醒

本文转载自支付宝体验科技&#xff0c;作者是蚂蚁集团客户端工程师博欢&#xff0c;介绍了支付宝如何基于 HarmonyOS 4.0 实况窗实现医疗场景履约智能提醒。 1.话题背景 8 月 4 日&#xff0c;华为在 HDC&#xff08;华为 2023 开发者大会&#xff09;上推出了新版本操作系统…