MGJ12. 字符串分割
描述
给定一个由小写字母组成的字符串s，请将其分割成尽量多的子串，并保证每个字母最多只在其中一个子串中出现。请返回由一个或多个整数表示的分割后各子串的长度。
输入描述
来自标准输入的一行由小写字母组成的字符串。输出描述
字符串最优分割后各子串的长度，多个数字之间由空格分隔。示例1
输入:
ababbacadefgdehijhklij
输出:
8 6 8
说明:
该样例下最优的分割为"ababbaca" + "defgde" + "hijhklij"，在该分割下字母abc仅出现在"ababbaca"中、字母defg仅出现在"defgde"中、字母hijkl仅出现在"hijhklij"中C 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2020-07-22
#include <stdio.h>
#include <stdlib.h>
int main(void) {
char buf[10000];
int i,j,len,maxi=0,last=0;
scanf("%s",buf);
len=strlen(buf);
for(i=0;i<len;i++)
{
if(i>maxi)
{
printf("%d ",maxi+1-last);
maxi=i;
last=maxi;
}
if(i==len-1)
printf("%d",maxi+1-last);
for(j=i+1;j<len;j++)
{
if(buf[i]==buf[j])
{
if(j>maxi) maxi=j;
}
}
}
}
C 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2021-07-19
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(const int argc, const char* argv[]) {
char input[1024] = "";
gets(input);
int last_index[26]; // 每个字符最后出现的位置
int i, len = strlen(input);
for (i = 0; i < len; ++i)
last_index[input[i] - 97] = i;
int start = 0, end = 0;
for (i = 0; i < len; ++i) {
end = fmax(end, last_index[input[i] - 97]);
if (i == end) {
fprintf(stdout, "%d", end - start + 1);
if (i < len - 1) fputc(32, stdout);
start = end + 1;
}
}
return 0;
}
C 解法, 执行用时: 1ms, 内存消耗: 380KB, 提交时间: 2020-05-03
#include<stdio.h>
#include<string.h>
#define Len 30
int main()
{
int fun(char *s,int n);
char s[Len];
int A[5];
int j=0;
int sum=0;
int temp,zt=0;
int count=0;
int t=0;
scanf("%s",s);
temp=strlen(s);
if(temp==1)
{
count=1;
j=1;
A[0]=1;
t=1;
}
while(t<temp)
{
count=fun(s,t);
if(count==0)
{
zt=1;
t++;
sum++;
}
else
{
t=count+1;
zt=count-sum+1;
sum=sum+zt;
}
A[j]=zt;
j++;
}
for(int i=0;i<j-1;i++)
printf("%d ",A[i]);
printf("%d\n",A[j-1]);
return 0;
}
int fun(char *s,int n)
{
int num=0;
int len=1;
int temp=strlen(s);
for(int j=n+1;j<temp;j++)
{
if(*(s+n)==*(s+j))
{
len=j;
num=j;
}
}
for(int i=n+1;i<len;i++)
{
for(int j=n+2;j<temp;j++)
{
if(*(s+i)==*(s+j))
{
if(j>num)
{
num=j;
}
}
}
}
return num;
}
C 解法, 执行用时: 2ms, 内存消耗: 304KB, 提交时间: 2019-08-30
#include<stdio.h>
#include<string.h>
#define Len 30
int main()
{
int fun(char *s,int n);
char s[Len];
int A[5];
int j=0;
int sum=0;
int temp,zt=0;
int count=0;
int t=0;
scanf("%s",s);
temp=strlen(s);
if(temp==1)
{
count=1;
j=1;
A[0]=1;
t=1;
}
while(t<temp)
{
count=fun(s,t);
if(count==0)
{
zt=1;
t++;
sum++;
}
else
{
t=count+1;
zt=count-sum+1;
sum=sum+zt;
}
A[j]=zt;
j++;
}
for(int i=0;i<j-1;i++)
printf("%d ",A[i]);
printf("%d\n",A[j-1]);
return 0;
}
int fun(char *s,int n)
{
int num=0;
int len=1;
int temp=strlen(s);
for(int j=n+1;j<temp;j++)
{
if(*(s+n)==*(s+j))
{
len=j;
num=j;
}
}
for(int i=n+1;i<len;i++)
{
for(int j=n+2;j<temp;j++)
{
if(*(s+i)==*(s+j))
{
if(j>num)
{
num=j;
}
}
}
}
return num;
}
C 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2019-04-09
#include "stdio.h"
#include "string.h"
int main()
{
char c[100];
gets(c);
int a[26][2]={30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0,30,0};
int s[26][2]={-1};
int k=0;
int i,ind;
for(i=0;i<strlen(c);i++)
{
ind = c[i]-'a';
if(i<a[ind][0])
a[ind][0]=i;
if(i>a[ind][1])
a[ind][1]=i;
}
int t = 1,flag=0;
s[0][0]=a[0][0];
s[0][1]=a[0][1];
// printf("%d,%d\n", a[2][0],a[2][1]);
for(i=1;i<26;i++)
{
while(flag==0)
{
if(a[i][0]<=s[k][0]&&a[i][1]<=s[k][1]&&a[i][1]>=s[k][0])
{
s[k][0]=a[i][0];
flag=1;
}
else if(a[i][0]<=s[k][0]&&a[i][1]>=s[k][1])
{
s[k][0]=a[i][0];
s[k][1]=a[i][1];
flag=1;
}
else if(a[i][0]>=s[k][0]&&a[i][1]>=s[k][1]&&a[i][0]<=s[k][1])
{
s[k][1]=a[i][1];
flag=1;
}
else if(a[i][0]>=s[k][0]&&a[i][1]<=s[k][1])
flag=1;
else
k++;
if(k>=t)
{
flag=1;
s[k][0]=a[i][0];
s[k][1]=a[i][1];
t++;
}
}
flag=0;
k=0;
}
for(i=0;i<t;i++)
{
printf("%d",s[i][1]-s[i][0]+1);
if(i!=t-1)
printf(" ");
}
return 0;
}