package partice1;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
/**
* “student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”
*/
public class ReverseSetence
{
/**
* 先将每一个单词逆序, 然后再将句子整体逆序
* 时间复杂度O(N) , 空间复杂度O(1) , 但由于java string是不可变字符串, 所以由此带来的空间复杂度为O(N), 用c则没有这个...
*/
public String ReverseSentence_best(String str)
{
if(str == null || str.length() == 0 )
return str ;
char[] chars = str.toCharArray() ;
int left = 0 ;
int right = 0 ;
boolean change = false ; //用于表示数组是否发生过逆序, 用于防止只有一个单词的句子出现, 如整个句子只有student一个单词, 就不需要整体逆序, 直接输出即可
while (right < str.length())
{
boolean flag = false ; //用于标记不是空格的字母是否是第一个, 如果是就赋值给left进行逆序; 这个可以防止中间有多个空格如: student i am这种情况
while (right < chars.length && chars[right] != ' ')
{
if(!flag)
{
left = right ;
flag = true ;
}
right++ ;
}
if(flag)
{
change = true ;
int r = right - 1;
while (left < r)
{
swap(chars, left++, r--);
}
}
right++ ;
}
if(change)
{
left = 0;
right = chars.length-1;
while (left < right)
swap(chars, left++, right--);
}
return new String(chars) ;
}
private void swap(char[] chars , int p , int q)
{
chars[p] ^= chars[q] ;
chars[q] ^= chars[p] ;
chars[p] ^= chars[q] ;
}
/**
* 这个是我第一次写的时候的思路, 使用一个辅助栈来进行逆序输出, 不好, 时间复杂度O(N), 空间复杂度O(N)
*/
public String ReverseSentence(String str)
{
if(str == null || str.length() == 0)
return str ;
Stack<String> stack = new Stack<>() ;
int from = -1 ;
for(int i=0 ; i<str.length() ; i++)
{
if(str.charAt(i) == ' ')
{
if(from != -1)
{
stack.push(str.substring(from , i)) ;
from = -1 ;
}
stack.push(" ") ;
}
else if(from == -1)
{
from = i ;
}
}
if(from != -1)
stack.push(str.substring(from)) ;
StringBuilder sb = new StringBuilder(str.length()) ;
while (!stack.isEmpty())
{
sb.append(stack.pop()) ;
}
return sb.toString() ;
}
public static void main(String[] args)
{
ArrayList<String> list = new ArrayList<>() ;
list.add("i'm a studnet") ;
list.add("hello") ;
list.add(" i am a student ") ;
Iterator<String> it = list.iterator() ;
while (it.hasNext())
{
String str = it.next() ;
System.out.println("|" + new ReverseSetence().ReverseSentence_best(str)+"|");
}
}
}