当前位置: 首页 > 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; 执行任何代码。对请求和响应对象进行更改。结束请求/响应循环。调用堆…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...