【划分型DP-最优划分】力扣2767. 将字符串分割为最少的美丽子字符串

给你一个二进制字符串 s ,你需要将字符串分割成一个或者多个 子字符串 ,使每个子字符串都是 美丽 的。

如果一个字符串满足以下条件,我们称它是 美丽 的:

它不包含前导 0 。
它是 5 的幂的 二进制 表示。
请你返回分割后的子字符串的 最少 数目。如果无法将字符串 s 分割成美丽子字符串,请你返回 -1 。

子字符串是一个字符串中一段连续的字符序列。

示例 1:
输入:s = “1011”
输出:2
解释:我们可以将输入字符串分成 [“101”, “1”] 。

  • 字符串 “101” 不包含前导 0 ,且它是整数 51 = 5 的二进制表示。
  • 字符串 “1” 不包含前导 0 ,且它是整数 50 = 1 的二进制表示。
    最少可以将 s 分成 2 个美丽子字符串。

示例 2:
输入:s = “111”
输出:3
解释:我们可以将输入字符串分成 [“1”, “1”, “1”] 。

  • 字符串 “1” 不包含前导 0 ,且它是整数 50 = 1 的二进制表示。
    最少可以将 s 分成 3 个美丽子字符串。

示例 3:
输入:s = “0”
输出:-1
解释:无法将给定字符串分成任何美丽子字符串。

提示:
1 <= s.length <= 15
s[i] 要么是 ‘0’ 要么是 ‘1’ 。

记忆化搜索

// 预处理 2**15 以内的 5 的幂的二进制表示
vector<string> pow5 = {"1", "101", "11001", "1111101", "1001110001", "110000110101", "11110100001001"
};class Solution {
public:int minimumBeautifulSubstrings(string s) {int n = s.size();vector<int> memo(n, -1);function<int(int)> dfs = [&](int i) -> int{if(i == n) return 0;if(memo[i] != -1) return memo[i];if(s[i] == '0') return INT_MAX;int res = INT_MAX;for(string &t : pow5){if(i + t.size() > n) break;if(s.substr(i, t.size()) == t){int sub_res = dfs(i + t.size());if(sub_res != INT_MAX){res = min(res, sub_res + 1);}}}return memo[i] = res;};return dfs(0) == INT_MAX ? -1 : dfs(0);}
};

时间复杂度:O(N*K)
空间复杂度: O(N)

我们首先先找出预处理 2^15 以内的 5 的幂的二进制表示,记录在容器pow5中。memo是记忆化用。最重要的是回溯的思路,我们定义dfs(i)的含义是从第i个字符后的字符串被分割成最少的美丽子字符串的个数,所以我们可以思考,我们从第0个字符开始,举个例子,如果找到了一个5的二进制表示101,那么也就是说,在这个回溯中,我们dfs(0)也就是dfs(3)+1,然后dfs(3)会继续往上回溯。那么既然使用了回溯,就要知道在回溯的末端我们该如何处理,在回溯末端我们刚好可以分割完字符串为美丽数组,那么就返回0,也就代表这个回溯的过程是可行的。如果无法分割,还有剩下的字符,那么res依旧为INT_MAX,也就是代表该回溯过程是不可行的。最后返回dfs(0)即可。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/12250.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Mac中安装OhMyZsh

Mac中安装OhMyZsh 文章目录 Mac中安装OhMyZsh一、Homebrew二、OhMyZsh1、Oh-My-Zsh配置1.1&#xff1a;主题配置1.2&#xff1a;插件配置&#xff08;语法高亮和自动提示&#xff09;1、zsh-autosuggestions&#xff08;需下载安装&#xff09;&#xff1a;高亮显示所有支持的命…

7、computed计算属性使用

代码 Student.vue <template> <div><h2>computed计算属性使用</h2><input type"text" v-model"name"/><br/><input type"text" v-model"sex"/><br/>完整信息&#xff1a;{{info}}&…

SystemVerilog学习笔记(三):结构体与联合体

结构体 结构包含具有不同大小的不同数据类型&#xff0c;这些数据类型分组在一个结构体名称下。默认情况下&#xff0c;结构体最初是未压缩的形式&#xff0c;但可以使用“packed”关键字将其转换为压缩结构。 结构与普通数组不同&#xff0c;因为数组仅使用相同类型和大小的…

无人飞手培训机构大量新增,如何选择好的培训机构?

随着无人机技术的普及和应用领域的拓展&#xff0c;无人机飞手培训机构确实在大量新增。为了选择一家好的培训机构&#xff0c;可以从以下几个方面进行考量&#xff1a; 一、培训资质 官方认证&#xff1a;选择具备中国航空器拥有者及驾驶员协会&#xff08;AOPA-China&#x…

Wi-Fi背后的工作原理与技术发展历程介绍【无线通信小百科】

1个视频说清楚WIFI&#xff1a;频段/历程/技术参数/常用模块 智能手机拥有率越来越高的今天&#xff0c;大家已经习惯了通过无线网络上网的方式。除了在外面需要用手机流量&#xff0c;我们通常在家里或者机场&#xff0c;商场都可以通过Wi-Fi连接上网。本期文章将为大家介绍Wi…

入门车载以太网(4) -- 传输层(TCP\UDP)

目录 1.ECU通信方式的变化 2.传输层概述 2.1 UDP 2.2 TCP 3. TCP和ISO 15765-2 1.ECU通信方式的变化 我们先回顾下两种通信方式&#xff1a;Signal-Based Messaging、Service-Based Messaging。 Signal-Based Messaging 基于信号的通信方式&#xff0c;例如CAN通信&…

软件测试第二篇软件测试技术

第五章单元测试和集成测试的技术 单元静态测试主要由开发人员完成。 标准&#xff1a;规定什么能做&#xff0c;什么不能做。 规范&#xff1a;建议你要怎么做。 5.1.2 代码评审 代码评审是一种发现代码缺陷的另一种测试方法。 代码审查的最佳实践&#xff1a; 创建代码审…

w035基于web的学科竞赛管理

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0…

导航系统非完整性约束汽车运动公约

Back to FDISYSTEMS Knowledge Base 惯性&导航传感器 导航系统&运动约束 数学基础 & 约定 参考坐标系载体 & 传感器坐标系方向/旋转表示非线性卡尔曼滤波器SPKF汽车运动公约船舶运动公约 惯性传感器安装 惯性传感器运行 技术洞察 Knowledge Base /数学基础…

Centos8 安装 JDK / Python / MySQL / Redis / Nginx

安装 JDK 华为镜像 JDK 下载地址&#xff1a;https://repo.huaweicloud.com:8443/artifactory/java-local/jdk/ 这里安装 JDK8 为例&#xff1a; # 这里直接通过 wget 下载 wget https://repo.huaweicloud.com:8443/artifactory/java-local/jdk/8u202-b08/jdk-8u202-linux-x…

【Qt-ROS开发】使用 Qt Creator 构建和编译含 ROS 库的 Qt 项目

【Qt-ROS】使用 Qt Creator 构建和编译含 ROS 库的项目 网上大多数办法是在 Qt creator中安装 ros_qtc_plugin 插件&#xff0c;项目以 ROS1 工作空间的形式构建&#xff0c;还是使用 catkin 来构建整个项目。但是这种方式局限很大&#xff0c;导入 Qt 的组件反而变得很麻烦&a…

【RabbitMQ】07-业务幂等处理

1. 方式一 序列化设置唯一Id。 Beanpublic MessageConverter messageConverter() {Jackson2JsonMessageConverter jjmc new Jackson2JsonMessageConverter();jjmc.setCreateMessageIds(true);return jjmc;}RabbitListener(bindings QueueBinding(value Queue(name "d…

SparseDrive 论文学习

论文链接&#xff1a;https://arxiv.org/pdf/2405.19620 代码链接&#xff1a;https://github.com/swc-17/SparseDrive 解决了什么问题&#xff1f; 传统模块化的自动驾驶系统可以被解耦为不同的独立模块&#xff0c;如感知、预测和规划&#xff0c;这种范式会面临信息丢失和…

如何提高自动驾驶中惯性和卫星组合导航pbox的精度?

Mems纯惯导里程推算精度做到千分之一&#xff0c;两分钟航向精度保持0.001弧度&#xff0c;是如何做到的&#xff1f; 简单的来说&#xff0c;导航系统的误差来源于这三方面:1.传感器误差 2.时间和迭代频率 3.算法精度。 接下来逐一分析。 1.传感器误差&#xff0c;传感器误差…

机器学习——贝叶斯

&#x1f33a;历史文章列表&#x1f33a; 机器学习——损失函数、代价函数、KL散度机器学习——特征工程、正则化、强化学习机器学习——常见算法汇总机器学习——感知机、MLP、SVM机器学习——KNN机器学习——贝叶斯机器学习——决策树机器学习——随机森林、Bagging、Boostin…

20241111,LeetCode 每日一题,用 Go 实现旋转链表

题目 给你一个链表的头节点 head &#xff0c;旋转链表&#xff0c;将链表每个节点向右移动 k 个位置。 解题思路 计算链表长度&#xff1a;遍历链表来获取链表的长度 n&#xff0c;因为链表的旋转其实是循环移动&#xff0c;所以将 k 对 n 取模 k k % n&#xff0c;这样可以…

Linux驱动开发(4):Linux的设备模型

在前面写的驱动中&#xff0c;我们发现编写驱动有个固定的模式只有往里面套代码就可以了&#xff0c;它们之间的大致流程可以总结如下&#xff1a; 实现入口函数xxx_init()和卸载函数xxx_exit() 申请设备号 register_chrdev_region() 初始化字符设备&#xff0c;cdev_init函数…

在线项目管理系统有哪些选择?2024年9款推荐

本文提及的2024值得关注的9款在线项目管理系统有: 1.PingCode&#xff1b; 2.Worktile&#xff1b; 3.华炎魔方&#xff1b; 4.企业微信&#xff1b; 5.Tapd&#xff1b; 6.青云客&#xff1b; 7.ClickUp&#xff1b; 8.Wrike&#xff1b; 9.Smartsheet。 许多企业在选择在线项…

pytorch量化训练

训练时量化&#xff08;Quantization-aware Training, QAT&#xff09;是一种在模型训练过程中&#xff0c;通过模拟低精度量化效应来增强模型对量化操作的鲁棒性的技术。与后训练量化不同&#xff0c;QAT 允许模型在训练过程中考虑到量化引入的误差&#xff0c;从而在实际部署…

datastage在升级版本到11.7之后,部分在11.3上正常执行的SP报错SQLSTATE = 22007: 本机错误代码 = -180

在升级版本到11.7之后&#xff0c;部分在11.3上正常执行的SP开始报错&#xff0c;报的SQL错误是时间参数问题&#xff0c;但是一样的SP可以直接call sp执行&#xff0c;也可以手动调用作业执行&#xff0c;只有设置定时调度时作业会报错&#xff0c; CALLXXX.XXX(1,CURRENT TIM…