笔试题之以单词为最小单位翻转字符串

  最近做了几个公司的笔试题，都考到了以单词为最小单位翻转字符串，这里自己总结一下：
  Write the function void reverseStringWordByWord(char[] input) that reverses 
  a string word by word.  For instance, 
  reverseStringWordByWord("this is my test program about string reverse !") --> "! reverse string about program test my is this"
注意：方法要求以字符数组为输入参数

思路：

首先将整个字符数组翻转一遍，例如this is my test program about string reverse ! 翻转为

!esrever gnirts tuoba margorp tset ym si siht

接着使用两个索引i和j分别指向每个单词的起始和结束位置，利用单词分隔符（这里是空格）确定单词的结束位置，找到单词的起始位置后直接在原字符数组中对该单词进行翻转。结果为! reverse string about program test my is this。需要注意的是最后一个单词后面没有分隔符了，需要通过数组长度进行判断最后一个单词的结束位置。

public class StringReverse {

	public static void main(String[] args) {
		
		String str = "this is my test program about string reverse !";
		char[] chars = str.toCharArray();
		print(chars);
		reverseString(chars);
		print(chars);
	}
	/**
	 * 翻转方法，用来翻转字符数组chars
	 * 首先将字符数组中的所有字符包括空格按顺序翻转；
	 * 然后从头开始遍历，记录开始位置i，结束位置j，直到j对应元素是空格时就翻转i到j
	 * 之间的元素，翻转完后，使i=++j,i记录下一次翻转的开始位置.
	 * 有一种特殊情况是当i和j到了最后一个单词时，最后面没有空格了，不能再根据空格得到
	 * 结束位置，而是直接j是否等于数组长度-1来判断j是否移动到最后一个元素了，此时再把
	 * i和数组长度传给reverse方法
	 * 
	 * @param chars
	 */
	private static void reverseString(char[] chars) {
		int length = chars.length;
		reverse(chars, 0, length);
		int i=0, j=0; //i表示每一个单词翻转的起始位置，翻转时j表示结束位置+1，即空格的位置
		while(j<length) {
			if(j == length-1) {
				reverse(chars, i, j+1);
				break;
			} else {
				if(chars[j] != ' ' )
					j++;
				else if(chars[j] == ' '){
					reverse(chars, i, j);
					i = ++j;
				}
			}
		}
	}
	/**
	 * 打印函数，打印chars数组
	 * @param chars 
	 */
	public static void print(char[] chars) {
		for(char c:chars)
			System.out.print(c);
		System.out.println();
	}
	/**
	 * 翻转char数组中从begin到end位置之间的元素，end是比最后一个翻转位置大一
	 * @param chars 翻转数组
	 * @param begin 起始位置
	 * @param end 结束位置+1
	 */
	private static void reverse(char[] chars, int begin, int end) {
		int total = begin+end-1;
		for(int i=begin; i<=total/2; i++ ) {
			char temp = chars[i];
			chars[i] = chars[total-i];
			chars[total-i] = temp;
		}
		print(chars);
	}
}

 

 

评论

2 楼 xifangyuhui 2010-11-07  

yangphere 写道

public static void main(String[] args) {
		String str = "this is my test program about string reverse !";

		String[] ss = str.split(" ");

		StringBuffer sb = new StringBuffer(ss.length);

		for (int i = ss.length - 1; i >= 0; i--) {
			String string = ss[i];
			sb.append(string).append(" ");
		}
		System.out.println(sb.toString().substring(0, sb.toString().length() - 1));
	}

笔试题不是直接用字符串做参数的，而是一个字符数组。

1 楼 yangphere 2010-11-07  

public static void main(String[] args) {
		String str = "this is my test program about string reverse !";

		String[] ss = str.split(" ");

		StringBuffer sb = new StringBuffer(ss.length);

		for (int i = ss.length - 1; i >= 0; i--) {
			String string = ss[i];
			sb.append(string).append(" ");
		}
		System.out.println(sb.toString().substring(0, sb.toString().length() - 1));
	}