首页 > 试题广场 >

01排序

[编程题]01排序
  • 热度指数：1612 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个01串（仅由‘ 0’或‘1’组成的字符串），现在想把这个数字串排序成“非递减”有序序列，请问至少需要多少次交换（任意两个位置交换）？

输入描述:
输入数据第一行是一个正整数T(T<=100),表示有T组测试数据；
接下来的T行，每行给出01串。
数据保证——
50%的字符串长度在[1,100 ]
95%的字符串长度在[1,10000]
100%的字符串长度在[1,1000000]


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

输入

3<br/>01<br/>10<br/>110

输出

0<br/>1<br/>1
算法知识视频讲解
添加回答
推荐
猩猩舞剑头像 猩猩舞剑 
  //水题，就是快速排序的一部分~ 
  #include<cstdio> 
 #include<cstring>
 #include<cstdlib> 
 #include<algorithm> 
 #define N 1001000
 using namespace std;
 int i,j,k,m,n;
 char s[N];
 int main(){
 int t;
 scanf("%d",&t);
 while (t--){
   scanf("%s",s+1);
   n=strlen(s+1);
   i=1;j=n;
   int ans=0;
   while (i<j){
      while (i<j&&s[i]=='0')i++;
      while (i<j&&s[j]=='1')j--;
      if (i<j){ans++;i++;j--;}
   }
   cout<<ans<<endl;
 }
 return 0;
 }
编辑于 2015-07-27 16:46:24 回复(1)
慈慈乱了头像 慈慈乱了
这个题就是求出0的个数n 然后看前n个数字里面有几个1 就行了
发表于 2015-07-20 21:57:15 回复(0)
Traveller头像 Traveller 

void timesofexchange(string &s)
{
    int numberof0 = 0;
    
    int count=0;
    int cycle = 0;
    for (int i = 0; i <s.size(); ++i)
    {
        if (s[i] == '0')
        {
            
            ++numberof0;
        }
    }
    while (cycle < s.size())
    {
        if (cycle <= numberof0-1)
        {
            if (s[cycle] != '0')
            {
                count++;
            }
            ++cycle;
        }
        else
        {
            if (s[cycle] != '1')
            {
                count++;
            }
            ++cycle;
        }
    }
    count = count / 2;
    cout << count << endl;
}
我并没有用什么排序，只是做了个求与预算。
思路很简单，举个例子大家就知道了
比如：1001001
求有多少个0，最后得到个字符串0000111
每一位与原字符串相与，共有四位不同，4/2=2
所以最少交换三次

编辑于 2015-08-10 11:14:54 回复(2)
Bumb头像 Bumb
是否也可以这样：
按位异或，相同为0，不同为1，然后统计出1的个数，就是交换的所有位数，这样除以2就是交换次数。
举例：1001011，交换后得到0001111，按位异或结果1000100有2个1，因此2/2=1次。这种方法与@Traveller类似。
发表于 2015-08-04 17:45:32 回复(0)
曹野头像 曹野
快排的变种
如果正序 第一个1位置 在倒序 第一个0位置之前，表示还需要一次互换
importjava.util.Scanner;
 
publicclassMain {
    publicstaticvoidmain(String[] args) {
        Scanner scanner = newScanner(System.in);
        intnum = scanner.nextInt();
        scanner.nextLine();
        for(inti = 0; i < num; i++) {
            intcount = 0;
            char[] arr = scanner.nextLine().toCharArray();//如果使用包装类 虽然方便 但是会超时
            intOneIndex = 0;
            intZeroIndex = arr.length - 1;
            while(OneIndex < ZeroIndex){
                while(OneIndex<arr.length-1&&arr[OneIndex]!='1') {//注意条件的边界 
                    OneIndex++;
                }
                while(ZeroIndex>0&&arr[ZeroIndex] != '0') {
                    ZeroIndex--;
                }
                arr[OneIndex]='0';//将两位置互换 这里直接放值就可以了
                arr[ZeroIndex]='1';
                if(OneIndex < ZeroIndex) {//记录交换次数
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}
发表于 2016-09-20 00:50:26 回复(0)
牛客549629号头像 牛客549629号 
var cnt=function(s){
  var i=0;j=s.length-1,ct=0;
  while(i<j){
    while(s[i]==='0')i++;
    while(s[j]==='1')j--;
    if(i<j){
     ct++;i++;j--;
    }
  }
  return ct;
}
cnt('101001010100110')

nodejs怎么输入输出  擦!
发表于 2016-04-21 14:12:56 回复(1)
电信曹若钧88头像 电信曹若钧88
把精力大量浪费在研究JAVA怎么输入一行字符串上了。

import java.util.Scanner ;

public class Main {
public static int getCharCount(String sSource, int nLen , char cChar) {
int nCount = 0 ;
int i ;
for(i=0; i< nLen; i++){
if (sSource.charAt(i) == cChar){
nCount++ ;
}
}
return nCount ;
}
public static void main(String args[]) {
intnCount0, nCount1 ;
int nTimes = 0 ;
String sSource ;
Scanner sc = new Scanner(System.in) ;
nTimes = sc.nextInt() ;
sSource = sc.nextLine() ;
int i ;
for(i=0; i< nTimes; i++){
sSource = sc.nextLine() ;
nCount0 = getCharCount(sSource, sSource.length(), '0') ;
nCount1 = getCharCount(sSource, nCount0, '1') ;
System.out.println(nCount1) ;
}
}
}

发表于 2015-08-31 16:43:45 回复(0)
野花野草野世界头像 野花野草野世界 
#include "stdio.h"
 #include "stdlib.h"
 #include "string.h"
 int lingyipaixu( char * str )
 {
     int i=0;
     int jiaohuanshu=0;
     int n=strlen(str);
     int j=n-1;
     while (j>i)
     {
         if(str[i]=='0')
         {
             i++;
             if(str[j] == '1')   
             j--;  
         }
         else
         {
         
                 if(str[j]=='1')
                     j--;
                 else
                 {
                     str[j]='1';
                     str[i]='0';
                     jiaohuanshu++;
                     j--;
                     i++;
                 }
         }
     }
     return jiaohuanshu;
 }
 int main()
 {
     char str[1000];
     scanf("%s",str);
     printf("%d\n",lingyipaixu(str));
  
 }
编辑于 2015-07-20 18:02:46 回复(2)
脱缰的哈士奇～头像 脱缰的哈士奇～ 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
using namespace std;


int swapMin(string str) {
	int res = 0;
	int length = str.size();
	int index = length;
	//每次交换，将1和最后的0位置交换
	for (int i = 0; i < length; i++) {
		if (str[i] == '1') {
			for (index = index; index > i; index--) {
				if (str[index] == '0') {
					res++;
					index = index - 1;
					break;
				}
			}			
		}
	}
	return res;
}

int main() {

	int counts;
	string str;
	while (cin >> counts) {
		for (int i = 0; i < counts; i++) {
			cin >> str;
			cout << swapMin(str) << endl;
		}
	}
	return 0;
}
若要交换次数最小，则每次需要把找到的1和字符串的最后1个0进行交换。（**贪婪思想，把数值1放的尽可能靠后，保证交换次数最小**）

遍历字符串，如果遇到了1,记其下标为`i`，再`i`之后，逆序寻找0。如果找到了，则交换次数加1。如果找不到0，则循环结束，输出结果。
发表于 2017-08-31 20:31:13 回复(0)
Jimmy_gg头像 Jimmy_gg 

	#include <iostream>





	#include <vector>





	 





	intmain(){





	    using namespace std;





	    intn = 0;





	    while(cin >> n){





	        vector<int> num;





	        for(inti = 0; i < n; i ++){





	            intcount = 0;





	            string str;





	            cin >> str;





	            intret = 0;





	            for(inti = 0; i < str.size(); i ++){





	                if(str[i] == '0')





	                    ret ++;





	            }





	            intnum_zero = 0;





	            for(inti = 0; i < ret; i ++){





	                if(str[i] == '0')





	                    num_zero ++;





	            }





	            count = ret - num_zero;





	            num.push_back(count);





	        }





	        for(inti = 0; i < num.size(); i ++)





	            cout << num[i] << endl;





	    }





	    return0;





	}

发表于 2017-03-21 00:07:14 回复(0)
狗阿狗阿头像 狗阿狗阿 
import java.util.*;

public class Main{
    private static Scanner sc=new Scanner (System.in);
    public static void main(String[] args){
        sc.nextLine();
        while(sc.hasNext()){
            StringBuilder sb=new StringBuilder (sc.nextLine());
            int n=sb.length();
            int j=0;
            int k=0;
            for(int i=0;i<n;i++){
                if(sb.charAt(i)=='0')j++;
            }
            for(int i=0;i<j;i++){
                if(sb.charAt(i)=='1')k++;
            }
            System.out.println(k);
        }
    }
}
发表于 2017-02-27 04:00:55 回复(0)
ALIwang头像 ALIwang
汇编语言应该是先 XOR AX,0FFH，然后ADD AX,SI
发表于 2017-01-04 20:27:08 回复(1)
张立超头像 张立超 

	#include <iostream>





	#include <string>





	 





	using namespace std;





	 





	intmain(){





	    intT;





	    cin >> T;





	    while(T--){





	        string str;





	        cin >> str;





	        intstart = 0;





	        intend = str.size() - 1;





	        intcount = 0;





	        while(start < end){





	            while(str[start] == '0')   start++;





	            while(str[end] == '1') end--;





	             





	            //swap





	            if(start < end){





	                count++;





	             





	                start++;





	                end--;





	            }





	             





	        }





	        cout << count << endl;





	    }





	    return0;





	}

发表于 2016-08-30 11:29:35 回复(0)
lioliu头像 lioliu 

	#include <stdio.h>





	#include <iostream>





	#include <stdlib.h>





	#include <algorithm>





	#include <string.h>





	using namespace std;





	char a[1000000];





	char b[1000000];





	int main(){





	    int n;





	    scanf("%d",&n);





	    for(int time=0;time<n;time++)





	    {





	        int sum =0;





	        cin>>a;





	        memcpy(b, a, strlen(a));





	        int start=0;





	        long end = strlen(a);





	        sort(b, b+end);





	       while(start<end)





	        {





	            sum += a[start]^b[start];





	            start++;





	        }





	     printf("%d\n",sum/2);





	    }





	    return 0;





	}
简单实现了 @Bumb 的思路
发表于 2016-04-19 19:15:09 回复(0)
朱永杰头像 朱永杰 
#include<iostream>
#include<string.h>
using namespace std;

char data[1000005];

int main()
{
	int T,len;
	cin >> T;
	int *changeNums = new int[T];
	for (int i = 0; i < T; i++)
		changeNums[i] = 0;
	for (int i = 0; i < T; i++)
	{
		cin >> data;
		len = strlen(data);
		char *pFist = data;
		char *pLast = data + len - 1;
		while (pFist < pLast)
		{
			if (*pFist == '0')
			{
				pFist++;
				continue;
			}
			if (*pLast == '1')
			{
				pLast--;
				continue;
			}
			changeNums[i]++;
			pFist++;
			pLast--;
		}
	}
	for (int i = 0; i < T; i++)
		cout << changeNums[i] << endl;
	delete[]changeNums;
	return 0;
}

发表于 2015-09-17 17:19:51 回复(0)
阿俊头像 阿俊 
import java.util.Arrays;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int t = cin.nextInt();// t组测试数据
		for (int i = 0; i < t; i++) {
			String s = cin.next();
			int count = getBinaryStr(s);
			System.out.println(count);
		}
	}

	private static int getBinaryStr(String s) {
		char[] ch = s.toCharArray();
		int low = 0;
		int high = ch.length - 1;
		int count = 0;
		while (low < high) {
			while (high > 0 && ch[high] == '1') {
				high--;
			}
			while (low < ch.length - 1 && ch[low] == '0') {
				low++;
			}
			if (low < high) {
				char temp = ch[low];
				ch[low] = ch[high];
				ch[high] = temp;
				count++;
			}
		}
		return count;
	}

}


发表于 2015-09-12 16:35:13 回复(0)
wudan3551头像 wudan3551 
//solution : two pointer 
#include <iostream> #include <vector>
#include <string>
#include <algorithm>

using namespace std;

int getSwapNumber(string& s){
    int lo = 0;
    int hi = s.size() - 1;
    int count = 0;

    while(lo < hi){
	while(s[lo] == '0' && lo < hi)++lo;
	while(s[hi] == '1' && hi > lo)--hi;

	if(lo < hi){
	    swap(s[lo++],s[hi--]);
	    ++count;
	}
    }

    return count;
}

int main(){
    string s;
    int n;

    cin>>n;
    while(n--) {
	cin>>s;

	cout<<getSwapNumber(s)<<endl;
    cout<<s<<endl;
    }
    return 0;
}


编辑于 2015-09-11 16:18:49 回复(0)
指上弹兵赵小括头像 指上弹兵赵小括 
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        int swapCount = 0;
        string lineStr;
        cin >> lineStr;
        int low = 0;
        int high = lineStr.length() - 1;
        while(low < high)
        {
            while(low < high && lineStr.at(low) == '0')
            {
                ++low;
            }

            while(low < high && lineStr.at(high) == '1')
            {
                --high;
            }

            if(low != high)
            {
                ++swapCount;
                ++low;
                --high;
            }
        }
        cout << swapCount << endl;
    }

    return 0;
}


发表于 2015-09-08 16:45:40 回复(0)
fomo头像 fomo 
 在VS里运行0011100得到的结果确实是2，但是提交程序的时候一直说该用例未通过，不懂哪里有问题：
#include <iostream>
 #include <string>
using namespace std;

int count_change(string str)
{
   int count=0;
   int i=0,j=str.size()-1;

   while(i<j)
    {
        while(str[i]=='0')
            i++;
        while (str[j]=='1')
            j--;
        if(i<j)
        {
            count++;
            i++;
            j--;
        }
     
     }
    return count;
}

int main( )
{
   string str;
   int T;
    
    cin>> T;
    
    while(T--)
    {
     getline(cin,str);
     
     cout<<count_change(str)<<endl;}
    return 0;
}

发表于 2015-09-06 18:27:46 回复(0)
吃猫不吐骨头的鱼头像 吃猫不吐骨头的鱼
最佳方案。满分，就这样。

#include"iostream"
using namespace std;
intget(string input){
    inttotal = input.length(),one = 0,zero = 0;
    bool first = true;
    for(inti = 0;i < total;++i)
        if(input[i] == '1') ++one;
    zero = total - one;
    if(zero == 0|| one == 0)   return0;
    intcnt = 0;
    if(zero == one){
        for(inti = 0;i < zero;++i)
            if(input[i] == '1') ++cnt;
    }elseif(zero > one){
        for(inti = 0;i < one;++i)
            if(input[total-i-1] == '0') ++cnt;
    }elseif(zero < one){
        for(inti = 0;i < zero;++i)
            if(input[i] == '1') ++cnt;
    }
    returncnt;
}
intmain(){
    intt;
    cin>>t;
    string input;
    while(t--){
        cin>>input;
        cout<<get(input)<<endl;
    }
    return0; 
}

编辑于 2015-09-05 10:47:54 回复(0)
skylife头像 skylife 
#include<iostream>
#include<string>
using namespace std;
int main(){
	int T;
	cin >> T;
	while (T--){
		string a;
		cin >> a;
		int len, i;
		len = a.length();
		int count = 0;
		int number = 0;
		for (i = 0; i<len; i++)
			if (a[i] == '0')
				count++;
		char *arr = new char[len];
		for (i = 0; i<len; i++)
			arr[i] = '1';
		for (i = 0; i<count; i++)
			arr[i] = '0';
		for (i = 0; i < len; i++)
			number += a[i] ^ arr[i];
				
		cout << number / 2 << endl;
	}
	
	return 0;
}

编辑于 2015-08-20 09:50:42 回复(0)
提交观点

问题信息

字符串
来自：百度2015春季实习生...
难度：
25条回答 11854浏览

热门推荐

通过挑战的用户

相关试题

01排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号