当前位置: 首页 > 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) …...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...