贪心算法-点灯问题
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;}
相关文章:
贪心算法-点灯问题
1、题目描述 给定一个字符串str,只由 ‘X’ 和 ‘.’ 两种字符构成。‘X’ 表示墙,不能放灯,点亮不点亮都可;’.’ 表示居民点,可以放灯,需要点亮。如果灯放在i位置,可以让 i-1,i 和…...
软件测试之单元测试自动化入门基础
单元测试自动化 所谓的单元测试(Unit Test)是根据特定的输入数据,针对程序代码中的最小实体单元的输入输出的正确性进行验证测试的过程。所谓的最小实体单元就是组织项目代码的最基本代码结构:函数,类,模块等。在Python中比较知名…...
93 # 实现 express 错误处理中间件
上一节实现了 express 的中间件,这一节来实现错误处理中间件 执行某一步出错了,统一规定调用 next 传递的参数就是错误信息 先看 express 实现的demo const express require("express"); const app express();app.use("/", (re…...
PHP 创建 MySQL 表
目录 PHP 创建 MySQL 表 使用 MySQLi 和 PDO 创建 MySQL 表 实例 (MySQLi - 面向对象) 实例 (MySQLi - 面向过程) 实例 (PDO) PHP 创建 MySQL 表 一个数据表有一个唯一名称,并有行和列组成。 使用 MySQLi 和 PDO 创建 MySQL 表 CREATE TABLE 语句用于创建 MySQ…...
中兴R5300 G4服务器iSAC管理员zteroot密码遗失的重置方法及IPV6地址启用设置
本文讲解中兴R5300 G4服务器BMC带外iSAC管理员zteroot密码遗失,无法登录时如何对其进行密码重置,以及iSAC启用IPV6地址的方法。 一、重置中兴R5300 G4服务器iSAC管理员zteroot密码 1、通过SSH登录到iSAC,默认用户名:sysadmin&am…...
大数据分布式处理框架Hadoop
大数据是什么 大数据容量常以TB、PB、甚至EB为单位,远超传统数据库的承载能力,无论入库还是查询都出现性能瓶颈。 Hadoop是什么 Hadoop是开源的分布式计算技术框架,用于处理大规模数据和实现分布式存储。 Hadoop核心组件 HDFS(…...
echarts学习总结
一、新建一个简单的Echarts 1、首先新建一个vue2的项目,项目中安装Echarts cnpm install echarts --save2、新建一个ref <template><div ref"myecharts" id"myecharts"></div> </template> 3、引入echarts <scri…...
与初至波相关的常见误解
摘要: 初至波是指检波器首次接收到的波. 对它的误解会使我们失去重要的信息. 1. 波从震源到检波器的传导过程 从震源产生波以后, 有些波通过地面直接传导到检波器, 这些称为直达波 (面波);有些在地层中传播,遇到两种地层的分界面时 产生波的反射,在原来地层中形成一种新波, …...
screenfull全屏、退出全屏、指定元素全屏的使用步骤
文章目录 页面全屏页面全屏完整代码 1.下载插件 建议下载指定版本5.1.0,不然可能有一个报错 npm install --save screenfull5.1.02.页面引入 import screenfull from "screenfull"页面全屏 3.在标签上绑定点击事件 <div click"handleFull"…...
问题 - 谷歌浏览器 network 看不到接口请求解决方案
谷歌浏览器 -> 设置 -> 重置设置 -> 将设置还原为其默认值 查看接口情况,选择 All 或 Fetch/XHR,勾选 Has blocked cookies 即可 如果万一还不行,卸载浏览器重装。 参考:https://www.cnblogs.com/tully/p/16479528.html...
Java:正则表达式的命名捕获组
命名捕获组格式 (?<year>.*)-(?<month>.*)-(?<date>.*)完整示例 package com.example.demo;import java.util.regex.Matcher; import java.util.regex.Pattern;public class RegexTests {public static void main(String[] args) {String text "2…...
ELK 处理 Spring Boot 日志
ELK 处理 Spring Boot 日志,妙啊! 来源:ibm.com/developerworks/cn/java /build-elk-and-use-it-for-springboot -and-nginx/index.html ELK 简介 Logstash Elasticsearch Kibana ELK 实现方案 ELK 平台搭建 安装 Logstash 安装 Elas…...
No152.精选前端面试题,享受每天的挑战和学习
🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…...
Flutter:类功能索引(全)
Flutter 类功能索引(全) 本文以表描述形式收录了Flutter中提供的各个类,旨在方便地进行查询相关组件。 本文地址:https://blog.csdn.net/qq_28550263/article/details/133415589 跳转:字母索引 A 组件名称描述Animat…...
电脑技巧:笔记本电脑升级固态硬盘的注意事项,看完你就懂了
目录 1、接口类型 2、接口速率 3、固态硬盘的尺寸 4、发热情况 5、总结 如今的固态硬盘价格越来越便宜了,甚至某品牌4TB的PCIe4.0 M.2还爆出过不到900元的“报恩价”,让不少小伙伴都动了扩容甚至囤货的心思。但对于笔记本电脑用户来说,升…...
TLS/SSL(一)科普之加密、签名和SSL握手
一 背景知识 感悟: 不能高不成低不就备注: 以下内容没有逻辑排版,仅做记录 https基础面经 ① 加密方式 说明: 单向和双向认证遗留: 如何用openssl从私钥中提取公钥? ② 互联网数据安全可靠条件 说明: 二者相…...
UVA-1374 旋转游戏 题解答案代码 算法竞赛入门经典第二版
GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版 由于书上给了思路,所以做起来并不难。 即使超时,因为数据量不大(1000个), 我们也可以直接打表直接返回结果。 但是如果想不打表完…...
logback.xml springboot 项目通用logback配置,粘贴即用,按日期生成
<configuration scan"false" scanPeriod"10 seconds"><!-- 定义日志存放的根目录 --><property name"log.dir" value"./logs" /><!-- 彩色日志依赖的渲染类 --><conversionRule conversionWord"clr&q…...
【AI视野·今日CV 计算机视觉论文速览 第256期】Thu, 28 Sep 2023
AI视野今日CS.CV 计算机视觉论文速览 Thu, 28 Sep 2023 Totally 96 papers 👉上期速览✈更多精彩请移步主页 Daily Computer Vision Papers SHACIRA: Scalable HAsh-grid Compression for Implicit Neural Representations Authors Sharath Girish, Abhinav Shriva…...
2023-9-28 JZ26 树的子结构
题目链接:树的子结构 import java.util.*; /** public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;}} */ public class Solution {public boolean HasSubtree(TreeNode root1,TreeNode root2) …...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
