"Coding Interview Guide" -- 翻转字符串

题目

  给定一个字符类型的数组chas,请在单词间做逆序调整。只要做到单词顺序逆序即可,对空格的位置没有特别要求

  举例,如果把chas看作字符串为"dog loves pig",调整成"pig loves dog";如果把chas看作字符串为"I'm a student.",调整成"student. a I'm"

 

要求

  如果chas长度为N,要求时间复杂度为O(N),空间复杂度为O(1)

 

分析

  首先将整个单词序列逆序,逆序后再将每个单词逆序,即可将单词顺序逆序。如"dog loves pig",首先将整个单词序列逆序得到"gip sevol god",然后将每个单词逆序,得到"pig loves dog"。整个过程都实在元字符数组的基础上完成的,所以空间复杂的为O(1),全程总共只遍历了整个字符数组两次,所以时间复杂度为O(N)  

 1 public void rotateWord(char[] chas)
 2 {
 3     if(chas == null || chas.length == 0)
 4     {
 5         return;
 6     }
 7 
 8     reverse(chas, 0, chas.length -1);      // 先将整个单词序列逆序
 9     int left = -1;         // left跟踪单词的左边界
10     int right = -1;        // right跟踪单词的右边界
11     for(int i = 0; i < chas.length; i++)
12     {
13       if(chas[i] != ' ')
14       {
15           left = i == 0 || chas[i-1] == ' ' ? i : left;    
16           right = i == chas.length || chas[i+1] == ' ' ? i : right;
17       }
18       if(left != -1 && right != -1)         
19       {
20           reverse(chas, left, right);        // 然后将单个单词逆序
21           left = -1;
22           right = -1;
23       }
24 
25     }
26 }
27                 
28             
29 public void reverse(char[] chas, int start, int end)
30 {
31     char temp;
32         
33     while(start < end)
34     {
35       temp = chas[start];
36       chas[start] = chas[end];
37       chas[end] = temp;
38       start++;
39         end--;
40     }        
41 }
42 
43     

 

来源:左程云老师《程序员代码面试指南》

上一篇:JavaGuide计算机网络面试要点 自我检测 (面试向)


下一篇:e.MMC PCB Design Guide