当前位置: 首页 > news >正文

贪心算法-点灯问题

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&#xff0c;只由 ‘X’ 和 ‘.’ 两种字符构成。‘X’ 表示墙&#xff0c;不能放灯&#xff0c;点亮不点亮都可&#xff1b;’.’ 表示居民点&#xff0c;可以放灯&#xff0c;需要点亮。如果灯放在i位置&#xff0c;可以让 i-1&#xff0c;i 和…...

软件测试之单元测试自动化入门基础

单元测试自动化 所谓的单元测试(Unit Test)是根据特定的输入数据&#xff0c;针对程序代码中的最小实体单元的输入输出的正确性进行验证测试的过程。所谓的最小实体单元就是组织项目代码的最基本代码结构&#xff1a;函数&#xff0c;类&#xff0c;模块等。在Python中比较知名…...

93 # 实现 express 错误处理中间件

上一节实现了 express 的中间件&#xff0c;这一节来实现错误处理中间件 执行某一步出错了&#xff0c;统一规定调用 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 表 一个数据表有一个唯一名称&#xff0c;并有行和列组成。 使用 MySQLi 和 PDO 创建 MySQL 表 CREATE TABLE 语句用于创建 MySQ…...

中兴R5300 G4服务器iSAC管理员zteroot密码遗失的重置方法及IPV6地址启用设置

本文讲解中兴R5300 G4服务器BMC带外iSAC管理员zteroot密码遗失&#xff0c;无法登录时如何对其进行密码重置&#xff0c;以及iSAC启用IPV6地址的方法。 一、重置中兴R5300 G4服务器iSAC管理员zteroot密码 1、通过SSH登录到iSAC&#xff0c;默认用户名&#xff1a;sysadmin&am…...

大数据分布式处理框架Hadoop

大数据是什么 大数据容量常以TB、PB、甚至EB为单位&#xff0c;远超传统数据库的承载能力&#xff0c;无论入库还是查询都出现性能瓶颈。 Hadoop是什么 Hadoop是开源的分布式计算技术框架&#xff0c;用于处理大规模数据和实现分布式存储。 Hadoop核心组件 HDFS&#xff08;…...

echarts学习总结

一、新建一个简单的Echarts 1、首先新建一个vue2的项目&#xff0c;项目中安装Echarts cnpm install echarts --save2、新建一个ref <template><div ref"myecharts" id"myecharts"></div> </template> 3、引入echarts <scri…...

与初至波相关的常见误解

摘要: 初至波是指检波器首次接收到的波. 对它的误解会使我们失去重要的信息. 1. 波从震源到检波器的传导过程 从震源产生波以后, 有些波通过地面直接传导到检波器, 这些称为直达波 (面波);有些在地层中传播,遇到两种地层的分界面时 产生波的反射,在原来地层中形成一种新波, …...

screenfull全屏、退出全屏、指定元素全屏的使用步骤

文章目录 页面全屏页面全屏完整代码 1.下载插件 建议下载指定版本5.1.0&#xff0c;不然可能有一个报错 npm install --save screenfull5.1.02.页面引入 import screenfull from "screenfull"页面全屏 3.在标签上绑定点击事件 <div click"handleFull"…...

问题 - 谷歌浏览器 network 看不到接口请求解决方案

谷歌浏览器 -> 设置 -> 重置设置 -> 将设置还原为其默认值 查看接口情况&#xff0c;选择 All 或 Fetch/XHR&#xff0c;勾选 Has blocked cookies 即可 如果万一还不行&#xff0c;卸载浏览器重装。 参考&#xff1a;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 日志&#xff0c;妙啊&#xff01; 来源&#xff1a;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 类功能索引&#xff08;全&#xff09; 本文以表描述形式收录了Flutter中提供的各个类&#xff0c;旨在方便地进行查询相关组件。 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/133415589 跳转&#xff1a;字母索引 A 组件名称描述Animat…...

电脑技巧:笔记本电脑升级固态硬盘的注意事项,看完你就懂了

目录 1、接口类型 2、接口速率 3、固态硬盘的尺寸 4、发热情况 5、总结 如今的固态硬盘价格越来越便宜了&#xff0c;甚至某品牌4TB的PCIe4.0 M.2还爆出过不到900元的“报恩价”&#xff0c;让不少小伙伴都动了扩容甚至囤货的心思。但对于笔记本电脑用户来说&#xff0c;升…...

TLS/SSL(一)科普之加密、签名和SSL握手

一 背景知识 感悟&#xff1a; 不能高不成低不就备注&#xff1a; 以下内容没有逻辑排版,仅做记录 https基础面经 ① 加密方式 说明&#xff1a; 单向和双向认证遗留&#xff1a; 如何用openssl从私钥中提取公钥? ② 互联网数据安全可靠条件 说明&#xff1a; 二者相…...

UVA-1374 旋转游戏 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版 由于书上给了思路&#xff0c;所以做起来并不难。 即使超时&#xff0c;因为数据量不大&#xff08;1000个&#xff09;&#xff0c; 我们也可以直接打表直接返回结果。 但是如果想不打表完…...

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 &#x1f449;上期速览✈更多精彩请移步主页 Daily Computer Vision Papers SHACIRA: Scalable HAsh-grid Compression for Implicit Neural Representations Authors Sharath Girish, Abhinav Shriva…...

2023-9-28 JZ26 树的子结构

题目链接&#xff1a;树的子结构 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) …...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...