[Java知识库]面试题5：替换空格

时间复杂度O(n) 空间复杂度O(1)

package com.basic;

public class ReplaceBlank {
	public static void main(String[] args) {
		char[] s=new char[50];
		String str="we are happy";
		int i = 0;
		for (; i < str.length(); i++) {
			s[i] = str.charAt(i);
		}
		s[i]='\0';
		
		for(int j=0;s[j]!='\0';j++){
			System.out.print(s[j]+" ");
		}
		System.out.println();
		replace(s,50);
		System.out.println("------------------换行-----------------------");
		for(int j=0;s[j]!='\0';j++){
			System.out.print(s[j]+" ");
		}
	}
	
	public  static void replace(char [] string,int length/*这个长度是字符数组的定义长度*/){
		if(string==null||length<=0){
			throw new IllegalArgumentException("参数不正确");
		}
		// 计算字符串中有多少个空格
		int originalLength=0;
		int numberofBlank=0;
		// 下标计数器
		int i=0;
		while(string[i]!='\0'){
			// 计算字符数组中真正的有效长度
			originalLength++;
			// 计算字符串中的空格数
			if(string[i]==' '){
				numberofBlank++;
			}
			// 计数器++
			i++;
		}
		
		int newLength=originalLength+numberofBlank*2;
		// 如果加上需要替换字符的长度超过了原本的数组长度则不能操作
		if(newLength>length){
			throw new RuntimeException("数组长度不够");
		}
		// 设置指针p1的位置
		int p1=originalLength;
		// 设置指针p2的位置
		int p2=newLength;
		while(p1>=0 && p2>p1){
			// 如果是空格那么就把p2一次往前赋值为%20
			if(string[p1]==' '){
				string[p2--]='0';
				string[p2--]='2';
				string[p2--]='%';
			}else{
				// 否则照常复制其他字符
				string[p2--]=string[p1];
			}
			// p1 在这里进行-1 操作应为不管p1是否遇到空格都会进行一次-1操作
			--p1;
		}
	}
}

此代码思路来自剑指offer面试题