zoj_1151 Word Reverse

For each list of words, output a line with each word reversed without changing the order of the words.

Time Limit: 2 Seconds      Memory Limit: 65536 KB

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

You will be given a number of test cases. The first line contains a positive integer indicating the number of cases to follow. Each case is given on a line containing a list of words separated by one space, and each word contains only uppercase and lowercase letters.

Output

For each test case, print the output on one line.

Sample Input

1

3

I am happy today

To be or not to be

I want to win the practice contest

Sample Output

I ma yppah yadot

oT eb ro ton ot eb

I tnaw ot niw eht ecitcarp tsetnoc

分析：

          本题的目标很明确，就是将每行字符串的单词反转后输出（每个数据块之间空一行），但是单词之间的顺序不变，因此不能直接把整行字符串反转。

           首先要解决输入问题。

           第一个数是数据块的个数，第二个数是每个数据块中字符串的行数。使用cin输入这两个数，作为以后循环的限定。

           其次是单词反转问题。

           起初想要先把字符串拆成一个个单词，然后将单词反转，存放在数组里，再输出。此处参考了奇老师的拆分字符串方法（工程代码写的炒鸡赞啊~\(≧▽≦)/~）

          但是对于一个ACM题目，这样写代码显得略长。而且，由于题目没有给出测试案例的数目上限，我们在声明字符串数组时会尽可能申请大的空间，这样有可能造成内存不足。第一次提交时就显示Segmentation Fault，应该是测试案例超过规定数目造成的。

           在小伙伴的帮助下得到启发，每拆解到一个单词，就将其反转，无需存储，直接输出。这样每次只为一个字符串申请内存，且该空间可循环利用。这样整个代码就比较简洁，也节省了内存空间。

方法一：

#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

//通用拆分字符串函数，以空格为间隔符
string  trimFront(string str)
{
	if (str == "") return "";
	while (str[0] == ' ')
	{
		str = str.substr(1, str.length() - 1);
	}
	return str;

}
string trimEnd(string str)
{
	if (str == "") return "";
	while (str[str.length() - 1] == ' ')
	{
		str = str.substr(0, str.length() - 1);
	}
	return str;

}
string trim(string str)
{
	str = trimFront(str);
	str = trimEnd(str);
	return str;

}

string * split(string str,int & splitCnt)
{
    if(str=="")
    {
        splitCnt=0;
        return NULL;
    }
	str = trim(str);
	int index = 0;
	string * ans = new string[1000];

    str=str+" ";

    while(str!=" ")
    {
        for(int i=0;i<str.length();i++)
        {
            if(str[i]==' ')
            {
                ans[index++]=str.substr(0,i);
                str=str.substr(i,str.length()-i);
                break;
            }
        }

        str=trim(str);
        str=str+" ";
    }

    splitCnt=index;
    return  ans;
}

//完成题目要求
string line[1000];//此处声明一个尽可能大的字符串数组
int main()
{
    int index , Case;
    cin >> Case;
    for ( int cas = 1; cas <= Case; cas ++ ) {
        string curLine="";
        cin >> index;
        getline( cin , line[0] );
        for (int i = 0; i < index; i ++) getline( cin , line[i] );
        for(int i=0;i<index;i++)
        {
            int cnt=0;
            string * parts=split(line[i],cnt);
            for(int j=0;j<cnt;j++)
            {
                reverse(parts[j].begin(),parts[j].end());//将单词的字母顺序反转
                if(j<cnt-1) cout<<parts[j]<<" ";
                else cout<<parts[j];
            }
            cout<<endl;
        }
        if(cas!=Case) cout << endl;//最后一个数据块下面不空行
    }
    return 0;
}
           

方法二：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

void deal(string & line) 
{
    int len = line.length();
    for ( int i = 0; i < len; i ++ )
    {
         if ( line[i] != ' ' )
        {
            int begin = i;
            while ( i < len && line[i] != ' ' ) i ++;//计算单词字符数
            reverse( &line[begin] , &line[i] );//反转单词
        }
    }
    cout << line << endl;
}

int main()
{
    int Case , index;
    string line;
    cin >> Case;
    for ( int cas = 1; cas <= Case ; cas ++) {
        //cin自动过滤空格、tab、换行符，而getline以回车为限定符，即读到回车便结束本次输入
        //因此使用cin并没有读完当前行，需要getline结束本行输入，从而下一次输入的就是需要解析的字符串了
        cin >> index;
        getline( cin , line );
        for ( int i = 0; i < index; i ++ ) {
            getline( cin , line );
            deal( line );
        }
        if ( cas != Case ) cout << endl;//最后一个数据块下面不空行
    }
    return 0;
}