首页 > ACM题库 > 九度OJ > 剑指offer(02)-替换空格[字符串处理]
2013
12-04

剑指offer(02)-替换空格[字符串处理]

题目来自九度 1510http://ac.jobdu.com/problem.php?pid=1510

题目描述:
请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
输入:
每个输入文件仅包含一组测试样例。
对于每组测试案例,输入一行代表要处理的字符串。
输出:
对应每个测试案例,出经过处理后的字符串。
样例输入:
We Are Happy
样例输出:
We%20Are%20Happy

看似很简单的一题,替换即可。但是提交上去才发现超时。下面是超时的代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char str[1000000];
int main()
{
	while (gets(str))
	{
		int len = strlen(str);
		for (int i = 0; str[i]; i++)
		{
			if (str[i] == ' ')
			{
				for (int j = len + 1; j > i + 2; j--)
					str[j] = str[j - 2];
				len += 2;
				str[i] = '%';
				str[i + 1] = '2';
				str[i + 2] = '0';
				//puts(str);
			}
		}
		puts(str);
	}
	return 0;
}

先用Java水过,在想怎么优化算法:

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line=null;
        while( (line=br.readLine()) != null){
            System.out.println(line.replaceAll(" ", "%20"));
        }
    }
}

这次用一个辅助数组,可以减少交换的次数,顺利通过!

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char str[1000000];
char res[1000000];
int main()
{
	while (gets(str))
	{
		int off = 0;
		//int len = strlen(str);
		for (int i = 0; str[i]; i++)
		{
			if (str[i] == ' ')
			{
				res[off+i] = '%'; res[off+i+1] = '2'; res[off+i+2] = '0';
				off += 2;
			}else
				res[off+i] = str[i];
		}
		puts(res);
	}
	return 0;
}

 


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测