最小二进制数

最小二进制数

时间: 1ms        内存:128M

描述:

如果字符串由“0”和“1”组成并且没有前导零,则可以将此字符串称为正确的
以下是一些示例:“0”,“10”,“1001”。
给你一个正确的字符串s,您可以对此字符串执行两种不同的操作:
1. 交换任何一对相邻字符(例如,“1 01” “1 10”);
2. 将“11”替换为“1”(例如,“11 0” “1 0”)。
设val(s)是一个数字,s是它的二进制表示。
正确的字符串a小于其他正确的字符串b if (val(a)<  val(b))。
您的任务是找到可以使用上述操作从给定字符串中获取的最小正确字符串。您可以按任何顺序多次使用这些操作(甚至根本不使用任何操作)。

输入:

第一行为一个整数 n (1<=n <= 100)。
第二行为一个长度为n且只包含0或1的字符串s, 保证字符串s是正确的。

输出:

输出一个您可以从给定字符串中获取的最小正确字符串。

示例输入:

4
1001

示例输出:

100

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
int main()
{
    int n;
    char s[101];
    int i,sum=0;
    scanf("%d",&n);
    scanf("%s",&s);
    if(n==1)
    {
        printf("%s\n",s);
    }
    else
    {
        for(i=1;i<n;i++)
        {
            if(s[i]=='1')
                sum++;
        }
        printf("1");
        for(i=0;i<n-sum-1;i++)
            printf("0");
        printf("\n");
    }
    return 0;
}

参考答案(时间最优[2]):

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string s;
int n;
int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n >> s;
	int a=0, b=0;
	for (int i = 0;s[i];++i)
	{
		if (s[i] == '0') a++;
		else b++;
	}
	if (!b) cout << 0 << endl;
	else
	{
		cout << 1;
		for (int i = 0;i < a;++i) cout << 0;
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注