37. 交换字符(第三期模拟笔试)
题目:
给定一个01串(仅由字符'0'和字符'1'构成的字符串)。每次操作可以交换两个相邻的字符。 例如:对于字符串"001110"来说, 可以交换第二个字符'0'和第三个字符'1',交换之后的字符串变成了"010110"。 如果想要最终字符串任意两个相邻的字符都不相同,最少需要多少操作次数? 保证输入的所有字符串测试用例通过交换后一定能够形成相邻两个字符都不相同的字符串。 |
样例:
|
3 |
思路:
贪心思路,观察01串我们知道,如果要01串相邻字符不相同,那么有两种情况出现。
1、当 0 和 1 个数不相同的时候, 我们知道肯定是 个数最多的数字作开头, 个数最少的操作的时候可能无法达到01串相邻字符不相同 ---------------------------------------------------------------------------------------------- 2、当 0 和 1 个数相同的时候, 有可能两个数字都可以作为开头,而我们需要找到最少的操作数 |
沿着这个思路,我们需要的是操作函数,对于操作的时候,我们应该取最近的不同字符进行交换,所以我们需要一个 pos 来错开一个字符,即 pos += 2,
操作步数:对应需要操作数字的下标 - pos 即: step += abs(i - pos)
代码详解如下:
#include <iostream>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;string s; // 01 串
int len; // 长度
int ans; // 答案
inline int swapStep(char c)
{// 交换的步数int step = 0;// 交换的最近距离int pos = 0;for(int i = 0;i < len;++i){// 从左往右遍历,找到是操作的数字if(s[i] == c){// 累加交换字符的步数step += abs(i - pos);// 这里是错开一个位置的字符// 达到相邻字符不相同,所以 pos += 2;// 例如: 11100 /* 操作 1 : i = 0 pos = 0 step = 0;i = 1 pos = 2 step += abs(i - pos) = 0 + 1;i = 2 pos = 4 step += abs(i - pos) = 1 + 2 = 3;操作 0 :i = 3 pos = 0 step = 0;i = 4 pos = 2 step += abs(i - pos) = 2; 从上面例子模拟,可以知道,0 只需要操作两次,即: 11010 第一次11001 第二次所以不能变成 相邻不相同而操作 1 的时候: 11010 第一次10110 第二次10101 第三次 */pos += 2;}}// 返回操作步数return step;
}inline void solve()
{getline(cin,s);len = s.size();int r[2] = {0,0}; // 统计 0 和 1 的个数for(auto i : s){int num = i - '0';++r[num]; // 统计 0 和 1 个数}// 取出 0 和 1 的操作步数int op0 = swapStep('0');int op1 = swapStep('1');// 如果 0 和 1 的数量相同// 说明 0 和 1 都可以做开头if(r[0] == r[1]){// 所以我们取最少的操作数即可ans = min(op0,op1);}else{// 否则我们应该让 个数 最多的数字开头// 所以我们取 个数最多的操作数// 因为个数最多,相当于操作最少// 为什么不直接取 min (op1,op0)// 是因为 当我们个数不相等的时候,个数最少的操作数是不合法了// 因为它只进行了一次交换一样达到了相邻字符不相同ans = r[0] > r[1] ? op0 : op1; } cout << ans << endl;}int main()
{
// freopen("a.txt", "r", stdin);
// ___G;int _t = 1;
// cin >> _t;while (_t--){solve();}return 0;
}
最后提交:
相关文章:

37. 交换字符(第三期模拟笔试)
题目: 给定一个01串(仅由字符0和字符1构成的字符串)。每次操作可以交换两个相邻的字符。 例如:对于字符串"001110"来说, 可以交换第二个字符0和第三个字符1,交换之后的字符串变成了"0101…...

git 查看当前分支最近一次提交的commit SHA
获取当前分支最近一次commit SHA (长度为40个16进制数字的字符)命令如下: git rev-parse HEAD 获取简写(短) commit SHA git rev-parse --short HEAD...

LuatOS 开发指南
NDK 开发 官方教程 官方例程 API 下载软件 下载官方NDK例程压缩包到本地,并解压。可以看到目录如下: doc: 文档教程 env: 编译环境 example: NDK示例 platform: 需要编译的平台(air72x/air8xx) tools: 其他辅助软件 VSCode 使…...

maven推包The environment variable JAVA_HOME is not correctly set
解决办法: 打开idea查看jdk安装位置 1.在/etc下面创建(如果存在就是更新)launchd.conf。里面添加一行: setenv JAVA_HOME /Library/Java/JavaVirtualMachines/jdk1.8.0_351.jdk/Contents/Home #JAVA_HOME后面是我的java安装路径…...

Python VScode 配置
在上一章节中我们已经安装了 Python 的环境,本章节我们将介绍 Python VScode 的配置。 准备工作: 安装 VS Code安装 VS Code Python 扩展安装 Python 3 安装 VS Code VSCode(全称:Visual Studio Code)是一款由微软…...

【vue2第九章】组件化开发和根组件以及style上的scoped作用
组件化开发和根组件 什么是组件化开发? 一个页面可以拆分为多个组件,每个组件有自己的样式,结构,行为,组件化开发的好处就是,便于维护,利于重复利用,提升开发的效率。 便于维护&…...

从零开始的Hadoop学习(五)| HDFS概述、shell操作、API操作
1. HDFS 概述 1.1 HDFS 产出背景及定义 1)HDFS 产生背景 随着数据量越来越大,在一个操作系统存不下所有的数据,那么就分配到更多的操作系统管理的磁盘中,但是不方便管理和维护,迫切 需要一种系统来管理多台机器上的…...
【spark】序列化和反序列化,transient关键字的使用
序列化 Spark是基于JVM运行的进行,其序列化必然遵守Java的序列化规则。 序列化就是指将一个对象转化为二进制的byte流(注意,不是bit流),然后以文件的方式进行保存或通过网络传输,等待被反序列化读取出来。…...
2.4 Vector<T> 动态数组(随机访问迭代器)
C自学精简教程 目录(必读) 该 Vector 版本特点 这里的版本主要是使用模板实现、支持随机访问迭代器,支持std::sort等所有STL算法。(本文对随机迭代器的支持参考了 复旦大学 大一公共基础课C语言的一次作业) 随机访问迭代器的实现主要是继承std::iterator<std:…...
Ubuntu下运行QEMU模拟riscv64跑Debian
1.安装QEMU 下载地址: https://www.qemu.org/download/ 建议选择稳定版本,下载后解压,然后make wget https://download.qemu.org/qemu-8.0.3.tar.xz tar xjvf qemu-8.0.3.tar.xz cd qemu-8.0.3 ./configure --enable-kvm --enable-virtfs …...

移动基站ip的工作原理
原理介绍 Basic Principle 先说一下概念,大家在不使用 WIFI 网络的时候,使用手机通过运营商提供的网络进行上网的时候,目前都是在用户端使用私有IP,然后对外做 NAT 转换,这样的情况就导致大家统一使用一些 IP 段进行访…...

Kubernetes技术--使用kubeadm搭建高可用的K8s集群(贴近实际环境)
1.高可用k8s集群架构(多master) 2.安装硬件要求 一台或多台机器,操作系统 CentOS7.x-86_x64 硬件配置:2GB或更多RAM,2个CPU或更多CPU,硬盘30GB或更多 注: 这里属于教学环境,所以使用三台虚拟机模拟实现。 3.部署规划 4.部署前准备 (1).关闭防火墙 systemctl stop fi…...

【Linux】文件
Linux 文件 什么叫文件C语言视角下文件的操作文件的打开与关闭文件的写操作文件的读操作 & cat命令模拟实现 文件操作的系统接口open & closewriteread 文件描述符进程与文件的关系重定向问题Linux下一切皆文件的认识文件缓冲区缓冲区的刷新策略 stuout & stderr 什…...

Android OTA 相关工具(六) 使用 lpmake 打包生成 super.img
我在 《Android 动态分区详解(二) 核心模块和相关工具介绍》 介绍过 lpmake 工具,这款工具用于将多个分区镜像打包生成一个 Android 专用的动态分区镜像,一般称为 super.img。Android 编译时,系统会自动调用 lpmake 并传入相关参数来生成 sup…...
信创环境 Phytium S2500 虚拟机最大内存规格测试
在 ARM 架构中,"IPA" 通常指的是 "Instruction Set Architecture"(指令集架构),arm环境的虚拟机支持的最大内存规格与母机上内存多少无关,由arm本身的ipa size决定,ipa size 可以理解为虚拟机的物理地址空间,kernel5.4.32中ipa默认是44bits(16T si…...

新建工程——第一个S32DS工程
之前的"测试开发板"章节 测试开发板——第一个AutoSAR程序,使用了一个 demo 工程,不管是裸机程序还是 AutoSAR 程序,那都是别人已经创建好的工程。本节来介绍如何来创建自己的工程,本节介绍如何创建一个 S32DS 的工程,点亮开发板上的 LED 我们从官方提供的例程…...

基于Open3D的点云处理16-特征点匹配
点云配准 将点云数据统一到一个世界坐标系的过程称之为点云配准或者点云拼接。(registration/align) 点云配准的过程其实就是找到同名点对;即找到在点云中处在真实世界同一位置的点。 常见的点云配准算法: ICP、Color ICP、Trimed-ICP 算法…...

设计模式—简单工厂
目录 一、前言 二、简单工厂模式 1、计算器例子 2、优化后版本 3、结合面向对象进行优化(封装) 3.1、Operation运算类 3.2、客户端 4、利用面向对象三大特性(继承和多态) 4.1、Operation类 4.2、加法类 4.3、减法类 4…...

真机安装Linux Centos7
准备工具: 8G左右U盘最新版UltraISOCentOS7光盘镜像 操作步骤 下载镜像 地址:http://isoredirect.centos.org/centos/7/isos/x86_64/ 安装刻录工具UltraISO,刻录镜像到U盘 ① 选择ISO镜像文件 ② 写入磁盘镜像,在这里选择你的U盘…...

ceph peering机制-状态机
本章介绍ceph中比较复杂的模块: Peering机制。该过程保障PG内各个副本之间数据的一致性,并实现PG的各种状态的维护和转换。本章首先介绍boost库的statechart状态机基本知识,Ceph使用它来管理PG的状态转换。其次介绍PG的创建过程以及相应的状…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...

让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...