Java实现7-32 说反话-加强版（通过所有测试点）

Java实现7-32 说反话-加强版（通过所有测试点）

最开始的想法就是用空格分割成数组，然后倒序输出。

下面这个版本除了卡时的点都过。然后开始了漫长而曲折的探索为啥超时之路，再下面放的是过了的代码，直接看通过代码的移步到最后。

public class B732 {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String N = in.nextLine().trim();
		// 当输入前面有空格时会保留前面的空格到字符数组里,.trim()避免这情况
		in.close();

		String str[] = N.split(" +"); // 分割一个或者多个空格
		// 正则表达式s表示匹配任何空白字符，+表示匹配一次或多次split("\s+")也行

		if (str.length != 1) {
			for (int i = str.length - 1; i > 0; i--) {
				System.out.print(str[i] + " ");
			}
		}
		System.out.print(str[0]);

		// 这一套输出就是不对，只有一个数时，还是要输出空格
//		for(int i=str.length-1; i>0; i--) {
//			System.out.print(str[i]);
//			System.out.print(" ");
//		}
//		System.out.print(str[0]);//格式错误应该是结尾不能多一个空格的
	}
}

其实最先通过的是用C写的。由于上面那版java改了又改没过，换了个逻辑，倒着读字符串，用两个指针记录一个单词，然后输出。

#include
#include

int main()
{
    char str[500001];
    gets(str);

    int b = strlen(str)-1; //单词开始指针
    int e = b; //单词结束指针
    int tmp = b;
    int flag = 1;
    
    while (b > 0)
    {
        if (str[b] == 32 && b == e)
        {
            // 多个空格跳过
            b--;
            e--;
        }
        else if (str[b] == 32 && b < e)
        {
            // 该输出一个单词了
            if(flag)
            {
                flag = 0;
            }
            else
            {
                printf(" ");
            }
            tmp = b + 1;
            while (tmp <= e)
            {
                printf("%c", str[tmp]);
                tmp++;
            }
            b--;
            e = b;
        }
        else
        {
            b--;
        }
    }
    if (b != e || e == 0)
    {
        // 输出最后一个单词
        if(str[b] != 32)
        {
            if(flag)
            {
                flag = 0;
            }
            else
            {
                printf(" ");
            }
            tmp = b;
            while (tmp <= e)
            {
                printf("%c", str[tmp]);
                tmp++;
            }
        }
    }
}

用cpp的栈实现也很简洁：原作者

#include 
#include 
#include 

using namespace std;

int main(){
    stack v;
    string s;
    while(cin >> s) v.push(s);
    if(v.empty()) return 0;
    cout << v.top();
    v.pop();
    while(!v.empty()){
        cout << " " << v.top();
        v.pop();
    }
    return 0;
}

为了避免java哪个函数超时了，我完全仿照C，写了一份。还是超时了，C占用内存100多k，但是java占用1W多k，C几毫秒用时的测试点，java接近100ms了（99ms）。

import java.util.Scanner;

public class B732 {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String N = in.nextLine(); // .trim()难道会超时？
		in.close();

		// char[] str = N.toCharArray(); // 难道这个也超时？
		int b = N.length() - 1; // 一个单词的首指针
		int e = N.length() - 1; // 一个单词的尾指针
		int tmp = b;
		boolean flag = true;

		while (b > 0) {
			if (N.charAt(b) == 32 && b == e) {
				// 多个空格跳过
				b--;
				e--;
			} else if (N.charAt(b) == 32 && b < e) {
				// 该输出一个单词了
				if (flag) {
					flag = false;
				} else {
					System.out.print(" ");
				}
				tmp = b + 1;
				while (tmp <= e) {
					System.out.print(N.charAt(tmp));
					tmp++;
				}
				b--;
				e = b;
			} else {
				b--;
			}
		}
		if (b != e || e == 0) {
			// 输出最后一个单词
			if (N.charAt(b) != 32) {
				if (!flag) {
					System.out.print(" ");
				} 
				tmp = b;
				while (tmp <= e) {
					System.out.print(N.charAt(tmp));
					tmp++;
				}
			}
		}
	}
}

我想不可能呀，肯定哪里有问题，于是搜了搜java提升速度的方式，结果是输出可以减少很多用时，忽然想起一年多以前老师上课强调过的……于是把模仿C那版的输出改了，但是还是超时，而且和第一版差不多。

最初版的输出也改了，用处不大，按照字符串数组输出，本身输出次数就远远小于按照字符输出。

public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String N = in.nextLine().trim();
		in.close();

		String str[] = N.split(" +"); 
		
		StringBuilder sb = new StringBuilder();
		if (str.length != 1) {
			for (int i = str.length - 1; i > 0; i--) {
				sb.append(str[i]);
				sb.append(" ");
			}
		}
		sb.append(str[0]);
		System.out.print(sb);
	}
}

怎么可能这么简单就过了，而且速度和第一版差不多……

最后我把能想到的，优化的部分都改了，真的已经不敢再提交了，然后过了，呜呜呜（我要好好学cpp，java可能真的不适合）

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String N = in.nextLine().trim();
		in.close();

		char[] str = N.toCharArray();
		//不用N是因为N很大，感觉数组会节省一点
		int b = str.length - 1; // 一个单词的首指针
		int e = b; // 一个单词的尾指针
		int tmp = b;

		StringBuilder sb = new StringBuilder();
		while (b > 0) {
			if (str[b] == 32 && b == e) {
				// 多个空格跳过
				b--;
				e--;
			} else if (str[b] == 32 && b < e) {
				// 该输出一个单词了
				tmp = b + 1;
				while (tmp <= e) {
					sb.append(str[tmp]);
					tmp++;
				}
				sb.append(" ");
				b--;
				e = b;
			} else {
				b--;
			}
		}
		if (b != e || e == 0) {
			// 输出最后一个单词
			tmp = b;
			if(b != 0) {
				while (tmp <= e) {
					sb.append(str[tmp]);
					tmp++;
				}
				System.out.print(sb);
			}else {
				System.out.print(sb);
				System.out.print(N.substring(0,e+1));
			}
		}else {
			System.out.print(sb);
		}
	}
}

最后如果有哪位大佬很简洁的用java过了，欢迎分享