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的创建过程以及相应的状…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...