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

Leetcode.664 奇怪的打印机

题目链接

Leetcode.664 奇怪的打印机 hard

题目描述

有台奇怪的打印机有以下两个特殊要求:

  • 打印机每次只能打印由 同一个字符 组成的序列。
  • 每次可以在从起始到结束的任意位置打印新字符,并且会覆盖掉原来已有的字符。

给你一个字符串 s ,你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1:

输入:s = “aaabbb”
输出:2
解释:首先打印 “aaa” 然后打印 “bbb”。

示例 2:

输入:s = “aba”
输出:2
解释:首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来的字符 ‘a’。

提示:

  • 1 ≤ s . l e n g t h ≤ 100 1 \leq s.length \leq 100 1s.length100
  • s 由小写英文字母组成

解法:区间dp

  • s = "a",需要打印 1 1 1 次;
  • s = "ab",需要打印 2 2 2 次;
  • s = "aba",需要打印 2 2 2 次;
  • s = "abab",需要打印 3 3 3 次;

当 最后一个字符 和 第一个字符 相同 时,例如 s = "aba" 。那么 s = "aba" 就和 s = "ab"的打印次数一样。

当 最后一个字符 和 第一个字符 不同 时,例如 s = "abab"。那么 s = "abab" 的打印次数,就应该是所有组合中最小的打印次数:

  • a + bab = 1 + 2 = 3
  • ab + ab = 2 + 2 = 4
  • aba + b = 2 + 1 = 3

所以 s = "abab" 的最少打印次数是 3 3 3

我们定义 f ( i , j ) f(i,j) f(i,j) 为打印区间 [ i , j ] [i,j] [i,j] 所需要的最少打印次数,那么最终返回的答案就是 f ( 0 , n − 1 ) f(0,n-1) f(0,n1)

  • i = j i = j i=j时,区间 [ i , j ] [i,j] [i,j] 只有一个字符,所以只需要打印一次,即 f ( i , j ) = 1 f(i,j) = 1 f(i,j)=1
  • s [ i ] = s [ j ] s[i] = s[j] s[i]=s[j]时, f ( i , j ) = f ( i , j − 1 ) f(i,j) = f(i,j-1) f(i,j)=f(i,j1)
  • s [ i ] ≠ s [ j ] s[i] \neq s[j] s[i]=s[j]时, f ( i , j ) = m i n { f ( i , k ) + f ( k + 1 , j ) } ( i ≤ k < j ) f(i,j) = min\{ f(i,k) + f(k+1,j) \} \quad (i \leq k < j) f(i,j)=min{f(i,k)+f(k+1,j)}(ik<j)

时间复杂度: O ( n 3 ) O(n^3) O(n3)

C++代码:

class Solution {
public:int strangePrinter(string s) {int n = s.size();vector<vector<int>> f(n,vector<int>(n,1e9));for(int i = 0;i < n;i++) f[i][i] = 1;for(int i = n-1;i >= 0;i--){for(int j = i + 1;j < n;j++){if(s[i] == s[j]){f[i][j] = f[i][j - 1];}else{for(int k = i;k < j;k++) f[i][j] = min(f[i][j] , f[i][k]+f[k+1][j]);}//printf("f[%d][%d] = %d\n",i,j,f[i][j]);}}return f[0][n-1];}
};

相关文章:

Leetcode.664 奇怪的打印机

题目链接 Leetcode.664 奇怪的打印机 hard 题目描述 有台奇怪的打印机有以下两个特殊要求&#xff1a; 打印机每次只能打印由 同一个字符 组成的序列。每次可以在从起始到结束的任意位置打印新字符&#xff0c;并且会覆盖掉原来已有的字符。 给你一个字符串 s &#xff0c;你…...

正中优配:散户怎么实现T+0?散户在股市上怎么变相T+0?

T0是指当天买入的标的物&#xff0c;在当天就能卖出的买卖方式&#xff0c;其中&#xff0c;在a股市场上&#xff0c;散户能够通过一些办法直接地完成T0买卖方式&#xff0c;接下来&#xff0c;正中优配为大家预备了相关内容&#xff0c;以供参阅。 散户在股票市场上&#xff0…...

ZooInspector

一、在window&#xff0c;使用我们先打开Zookeeper,目录bin下的zkServer.cmd&#xff0c;把Zookeeper运行起来 ​编辑https://img.111com.net/attachment/art/187687/5f0c25fbe580c.png 二、可以使用目录bin下的zkCli.cmd&#xff0c;查询Zookeeper数据的方式&#xff0c;但是…...

2023高教社杯 国赛数学建模B题思路 - 多波束测线问题

1 赛题 B 题 多波束测线问题 单波束测深是利用声波在水中的传播特性来测量水体深度的技术。声波在均匀介质中作匀 速直线传播&#xff0c; 在不同界面上产生反射&#xff0c; 利用这一原理&#xff0c;从测量船换能器垂直向海底发射声波信 号&#xff0c;并记录从声波发射到信…...

【计算机视觉 | 目标检测】arxiv 计算机视觉关于目标检测的学术速递(9 月 4 日论文合集)

文章目录 一、检测相关(8篇)1.1 Impact of Image Context for Single Deep Learning Face Morphing Attack Detection1.2 A Theoretical and Practical Framework for Evaluating Uncertainty Calibration in Object Detection1.3 What Makes Good Open-Vocabulary Detector: A…...

游戏优化注意点

特效性能分析&#xff1a; 1、粒子数量太多&#xff0c;这个会对CPU的耗时产生一定的压力。 2、粒子的size太大&#xff0c;这样容易导致渲染的像素数量非常高。 3、Overdraw非常高&#xff0c;当场上粒子数非常高导致叠层很高&#xff0c;会造成Overdraw很高&#xff0c;这会…...

【unity3D】如何修改相机的默认视角

&#x1f497; 未来的游戏开发程序媛&#xff0c;现在的努力学习菜鸡 &#x1f4a6;本专栏是我关于游戏开发的学习笔记 &#x1f236;本篇是unity的如何修改相机的默认视角 如何修改相机的默认视角 Game窗口运行的话视角是这样的&#xff1a; 此时Scene窗口的视角是这样的&…...

Docker的初级使用

Docker的初级使用 Docker的安装1.1 如果之前安装过旧版本的Docker,可以使用下面命令卸载:1.2.安装docker1.3.启动docker1.4.配置镜像加速2.CentOS7安装DockerCompose2.1.下载2.2.修改文件权限2.3.Base自动补全命令:3.Docker镜像仓库3.1.简化版镜像仓库3.2.带有图形化界面版本…...

minimumLineSpacing和minimumInteritemSpacing问题研究

结论&#xff1a;minimumLineSpacing和minimumInteritemSpacing问题研究 (1)如果cell的宽度是固定的&#xff0c;方向是水平时&#xff0c; 1 3 5 2 4 6 minimumLineSpacing 是 12 到 34的距离 minimumInteritemSpacing 是1到2的距离 (2)如果cell的宽度是不固定的&#xff0…...

【操作系统】聊聊Linux内存工作机制

内存主要是用来存储系统和应用程序的指令、数据、缓存等 内存映射 内存是需要安全机制保护的&#xff0c;所以只有内核才可以直接访问物理内存。进程如果要访问内存需要通过独立的虚拟地址空间。 虚拟地址空间其实包含两部分。一部分是内核空间&#xff0c;另一部分就是用户…...

MySQL索引的类型有哪些?

分析&回答 从功能逻辑角度&#xff0c;可分为&#xff1a; 普通索引 INDEX(普通索引) ALTER TABLE table_name ADD INDEX index_name ( column )唯一索引 UNIQUE(唯一索引) ALTER TABLE table_name ADD UNIQUE (column)主键索引 PRIMARY KEY&#xff08;主键索引…...

【JavaScript】在指定dom元素前面创建标签元素

一、基础操作过程 要在指定的DOM元素前面创建标签元素&#xff0c;有以下步骤&#xff1a; 获取指定的DOM元素&#xff1a;使用document.querySelector()或document.getElementById()等方法来获取指定的DOM元素。 const targetElement document.querySelector(#targetElement…...

ARMv8 TTBRx寄存器

ARMv8 TTBRx寄存器 1 TTBR0_ELx and TTBR1_ELx2 TTBR0_ELx2.1 TTBR0_EL12.2 TTBR0_EL22.3 TTBR0_EL33 TTBR13.1 TTBR1_EL13.2 TTBR1_EL2 4 访问TTBRx寄存器4.1 TTBR0_ELx4.2 TTBR1_ELx 5 TTBRx保留的是物理地址还是虚拟地址5.1 保存的是物理地址还是虚拟地址5.2 为什么是物理地…...

C51智能小车(循迹、跟随、避障、测速、蓝牙、wifie、4g、语音识别)总结

目录 1.电机模块开发 1.1 让小车动起来 1.2 串口控制小车方向 1.3 如何进行小车PWM调速 1.4 PWM方式实现小车转向 2.循迹小车 2.1 循迹模块使用 2.2 循迹小车原理 2.3 循迹小车核心代码 3.跟随/避障小车 3.1 红外壁障模块分析​编辑 3.2 跟随小车的原理 3.3 跟随小…...

回归预测 | MATLAB实现PCA-BP主成分降维结合BP神经网络多输入单输出回归预测

回归预测 | MATLAB实现PCA-BP主成分降维结合BP神经网络多输入单输出回归预测 目录 回归预测 | MATLAB实现PCA-BP主成分降维结合BP神经网络多输入单输出回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 MATLAB实现PCA-BP主成分降维算法结合BP神经网络多输入单输出回…...

Kubernetes(k8s)部署高可用多主多从的Redis集群

Kubernetes部署高可用多主多从的Redis集群 环境准备准备Kubernetes准备存储类 部署redis准备一个命名空间命令创建yaml文件创建&#xff08;推荐&#xff09; 准备redis配置文件准备部署statefulset的资源清单文件执行文件完成部署初始化集群 环境准备 准备Kubernetes 首先你…...

算法专题:前缀和

文章目录 Acwing&#xff1a;前缀和示例2845.统计趣味子数组的数目思路容易理解的写法&#xff1a;前缀和两层循环存在问题&#xff1a;超时 优化写法&#xff1a;两数之和思路&#xff0c;转换为哈希表 前缀和&#xff0c;就是求数组中某一段的所有元素的和。 求子数组中某一…...

bs4库爬取天气预报

Python不仅用于网站开发&#xff0c;数据分析&#xff0c;图像处理&#xff0c;也常用于爬虫技术方向&#xff0c;最近学习了解下&#xff0c;爬虫技术入门一般先使用bs4库&#xff0c;爬取天气预报简单尝试下。 第一步&#xff1a;首先选定目标网站地址 网上查询&#xff0c…...

l8-d8 TCP并发实现

一、TCP多进程并发 1.地址快速重用 先退出服务端&#xff0c;后退出客户端&#xff0c;则服务端会出现以下错误&#xff1a; 地址仍在使用中 解决方法&#xff1a; /*地址快速重用*/ int flag1,len sizeof (int); if ( setsockopt(fd, SOL_SOCKET, SO_REUSEADDR, &a…...

编写中间件以用于 Express 应用程序

概述 中间件函数能够访问请求对象 (req)、响应对象 (res) 以及应用程序的请求/响应循环中的下一个中间件函数。下一个中间件函数通常由名为 next 的变量来表示。 中间件函数可以执行以下任务&#xff1a; 执行任何代码。对请求和响应对象进行更改。结束请求/响应循环。调用堆…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

李沐--动手学深度学习--GRU

1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...

python基础语法Ⅰ

python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器&#xff0c;来进行一些算术…...