首页 > ACM题库 > 九度OJ > 九度-1525-子串逆序打印[解题代码]
2013
12-13

九度-1525-子串逆序打印[解题代码]

题目来源:2012年Google校园招聘笔试题目

题目描述:

小明手中有很多字符串卡片,每个字符串中都包含有多个连续的空格,而且这些卡片在印刷的过程中将字符串的每个子串都打印反了,现在麻烦你帮小明将这些字符串中的子串修正过来,同时为了使卡片美观,压缩其中的连续空格为1个。

输入:

输入包含多个测试用例,每个测试用例的第一行是一个正整数 n,1=<n<=100000,代表卡片上字符串的长度。第二行输入长度为n的字符串(字符串仅包含小写字母和空格)。当n为0时,代表输入结束。

输出:

对应每个测试用例,请按照要求输出修正过的字符串。

样例输入:
3
abc
13
abc   efg hij
样例输出:
cba
cba gfe jih

cpp 代码如下:
#include <stdio.h>
int n;
char str[100011];
int main() {
	while(scanf("%d", &n)!=EOF && n > 0) {
		gets(str);
		gets(str);
		int i=0;
		if(str[0] == ' ')
		printf("%c",' ');
		while(str[i] == ' ') i++;
		int start=i;
		for(; i<n; i++) {
			if(str[i] == ' ') {
			for(int j=i-1; j>=start; j--) {
				printf("%c",str[j]);
			}
			printf("%c",' ');
			while(str[i] == ' ') i++;
			start = i;
		}
	}
	if(str[n-1] != ' ') {
		for(int j=i-1; j>=start; j--)  printf("%c",str[j]);
	}
	printf("\n");
}
return 0;
}
/**************************************************************
	Problem: 1525
	User: coder
	Language: C
	Result: Accepted
	Time:80 ms
	Memory:1016 kb
****************************************************************/


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。