【编程题】01串排序

￡神魔★判官ぃ 2022-08-01 14:48 195阅读 0赞

# 题目 #

给定一个01串（仅由‘ 0’或‘1’组成的字符串），现在想把这个数字串排序成“非递减”有序序列，请问至少需要多少次交换（任意两个位置交换）？  
输入描述:  
输入数据第一行是一个正整数T(T<=100),表示有T组测试数据；  
接下来的T行，每行给出01串。  
数据保证——  
50%的字符串长度在\[1,100 \]  
95%的字符串长度在\[1,10000\]  
100%的字符串长度在\[1,1000000\]

输出描述:  
对于每组测试数据，请输出排成“非递减有序序列”的最小交换次数。  
每组输出占一行。

输入例子:  
3  
01  
10  
110

输出例子:  
0  
1  
1

# 分析 #

使用快速排序的思想，使用两个指针i和j，i从左往右扫描，j从右往左扫描。左边遇到1，右边遇到0的时候就要进行一次交换。

# 代码 #

#include <iostream>
    #include <string>
    using namespace std;
    int func(string str){
        int len = str.length();
        int i = 0, j = len-1;
        int cnt = 0;
        while(i < j){
            while(i < j && str.at(i) == '0') i++;
            while(i < j && str.at(j) == '1') j--;
            if(i < j){
       //由于此题只求需要交换的次数，故不需要真正交换。
                i++;
                j--;
                cnt++;
            }
        }
        return cnt;
    }
    int main(){
        int T;
        cin >> T;
        while(T--){
            string str;
            cin >> str;
            cout << func(str) << endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，195人围观）

还没有评论，来说两句吧...

相关阅读

相关 NYOJ 252 01串

01串时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述 ACM的zyc在研究01串，他知道某一01串的长度，但他想知道不含有“11”

àì夳堔傛蜴生んèń/ 2022年08月25日 02:10/ 0 赞/ 181 阅读

相关最长01串

最长01串 Time Limit: 2666ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给定一个0-1串，请找到

浅浅的花香味﹌/ 2022年08月18日 02:30/ 0 赞/ 201 阅读

相关【编程题】01串排序

题目给定一个01串（仅由‘ 0’或‘1’组成的字符串），现在想把这个数字串排序成“非递减”有序序列，请问至少需要多少次交换（任意两个位置交换）？输入描述: 输

￡神魔★判官ぃ/ 2022年08月01日 14:48/ 0 赞/ 196 阅读

相关 [编程题]字符串排序

> Talk is cheap, show me the code. 一、问题描述编写一个程序，将输入字符串中的字符按如下规则排序。规则1：英文字母从A到Z排列

矫情吗；*/ 2022年07月14日 14:38/ 0 赞/ 210 阅读

相关又是01串

2272: 又是01串题目描述给定一个0-1串s，长度为n，下标从0开始，求一个位置k，满足0<=k<=n, 并且子串s0..k−1中的0的个数与子串

墨蓝/ 2022年05月25日 11:29/ 0 赞/ 229 阅读

相关混合串排序

两个字符串（字符串1、字符串2）的大小比较，字符串可能既含有字符（a～z）又含有数字（0～9）。比较规则： (1)从左到右分离单纯的子字符串（全字符）和子数字串（全数

喜欢ヅ旅行/ 2022年05月17日 07:04/ 0 赞/ 113 阅读

相关 01字串

对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是： 00000 00001 00010 00011 00100 请按从小到大的顺序

桃扇骨/ 2022年04月10日 05:28/ 0 赞/ 233 阅读

相关【Java】交错01串

题目描述如果一个01串任意两个相邻位置的字符都是不一样的,我们就叫这个01串为交错01串。例如: “1”,“10101”,"0101010"都是交错01串。小易现在

谁践踏了优雅/ 2022年01月30日 03:51/ 0 赞/ 247 阅读

相关 01字串

蓝桥杯学习记录 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

男娘i/ 2021年07月24日 23:14/ 0 赞/ 406 阅读

相关【阿里云在线编程】 65.Alice的01串

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

清疚/ 2021年06月10日 20:38/ 0 赞/ 360 阅读