翻轉(zhuǎn)單詞順序

• 題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中的單詞順序，但是單詞內(nèi)的字符順序不變，例如：I am a software engineer -> engineer software a am I

方案一：空間換時(shí)間

• 空間換時(shí)間方法，還是如上案例中，I am a software engineer，分析如上：
  • 統(tǒng)計(jì)出字符串中空格位置，按空格拆分
  • 通過(guò)空格的順序逐個(gè)拆解原字符串
  • 將拆解后的字符串按照單詞從后面開始復(fù)制
  • 例如最后一個(gè)空格位置 15，那么第一個(gè)單詞的位置應(yīng)該是15+1 ~ str.length-1
  • 依次類推逐個(gè)向前復(fù)制
  • 如下圖所示
    
• 如上分析有如下代碼：

/*** 反轉(zhuǎn)字符串中單詞順序，I am a software engineer -> engineer software a am I* @author liaojiamin* @Date:Created in 16:59 2021/7/1*/ public class ReverStr {public static void main(String[] args) {String str = "I am a software engineer";char[] target = str.toCharArray();char[] result = reverMyStr(target);for (char c : result) {System.out.print(c);}}/*** 方案一：空間換時(shí)間方法，* 空間復(fù)雜度O(n)，時(shí)間復(fù)雜度O(n)* */public static char[] reverMyStr(char[] target){if(target == null || target.length <= 0){return target;}int[] isSpace = new int[target.length];int positionSpace = 0;char[] result = new char[target.length];int resultPosition = 0;for (int i = 0; i < target.length; i++) {if(target[i] == ' '){isSpace[positionSpace++] = i;}}int positionEnd = target.length -1;positionSpace--;for (int i = positionSpace; ; i--) {int start = 0;if(i>=0){start = isSpace[i] + 1;}result = splitCharArray(start, positionEnd, target, result, resultPosition);resultPosition += (positionEnd - start +1);if(start != 0){//最后一次不需要再添加空格result[resultPosition++]=' ';positionEnd = isSpace[i] -1;}if(start == 0){return result;}}}public static char[] splitCharArray(int start, int end, char[] target, char[] result, int position){for(int i=start; i <=end;i++){result[position++] = target[i];}return result;} }

• 方案一中其實(shí)就是模擬一個(gè)字符串拆分函數(shù)split，只是在拆分后在對(duì)具體的單詞進(jìn)行順序的變化，整體時(shí)間復(fù)雜度，第一次遍歷得出拆分點(diǎn)空格，第二次逐個(gè)對(duì)拆分后的字符進(jìn)行復(fù)制，所以時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)

方案二：多次翻轉(zhuǎn)

• 本題中需要得到單個(gè)單詞順序上的翻轉(zhuǎn)，但是實(shí)際字符是正向的，分析如下：
  • 翻轉(zhuǎn)字符串，得到一個(gè)完全翻轉(zhuǎn)的，此時(shí)目的在于，然后面的單詞位置能移動(dòng)到簽名，實(shí)現(xiàn)單詞順序的變化
  • 此時(shí)得到的是一個(gè)單詞，字母都是逆序的字符串
  • 統(tǒng)計(jì)現(xiàn)有字符串中空格，依據(jù)空格區(qū)分每個(gè)單詞
  • 分別對(duì)每個(gè)單詞字符串進(jìn)行單獨(dú)翻轉(zhuǎn)得到最終結(jié)果。
  • 如下圖：

• 經(jīng)如上分析有如下代碼：

/*** 反轉(zhuǎn)字符串中單詞順序，I am a software engineer -> engineer software a am I* @author liaojiamin* @Date:Created in 16:59 2021/7/1*/ public class ReverStr {public static void main(String[] args) {String str = "I am a software engineer";char[] target = str.toCharArray();char[] result_1 = reverTwice(target);for (char c : result_1) {System.out.print(c);}}/*** 方案二：反轉(zhuǎn)兩次* 先全部反轉(zhuǎn)字符，在逐個(gè)單詞顛倒* 時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O(1)* */public static char[] reverTwice(char[] target){if(target == null || target.length <= 0){return target;}target = reverAll(target, 0, target.length -1);int[] isSpace = new int[target.length];int positionSpace = 0;for (int i = 0; i < target.length; i++) {if(target[i] == ' '){isSpace[positionSpace++] = i;}}positionSpace--;int start = 0;for (int i = 0; ; i++) {int end = target.length -1;if(i <= positionSpace){end = isSpace[i] - 1;}target = reverAll(target, start, end);if(i <= positionSpace){start = isSpace[i] +1;}else {return target;}}}/*** 按指定位置反轉(zhuǎn)* */public static char[] reverAll(char[] target, int start, int end){while (start < end){char temp = target[start];target[start] = target[end];target[end] = temp;start++;end--;}return target;} }

變種題型

• 題目：定義字符串的左旋轉(zhuǎn)操作就是把字符串簽名的若干字符轉(zhuǎn)移到字符的尾部。請(qǐng)定義一個(gè)函數(shù)，實(shí)現(xiàn)字符串的左旋操作功能， 例如輸入字符串I am a software engineer 4 -> a software engineerI am

方案一：空間換時(shí)間

• 最直觀的方法，直接定義一個(gè)新的數(shù)組復(fù)制需要的段。分析如下：
  • 如上題案例中，只需要將指定前面的字符轉(zhuǎn)到最后，如果用字符串移動(dòng)每個(gè)字符都要操作 指定數(shù)子的次數(shù)
  • 如果定義新的數(shù)組，則只需要將指定階段復(fù)制過(guò)去
  • 如上指定位4，我們先將后面字符串 5~length-1 位置的字符復(fù)制到新數(shù)組開始位置
  • 然后將0~4 位置數(shù)組復(fù)制到新數(shù)組的后面
  • 得到的新數(shù)組就是我們需要的結(jié)果
  • 如下圖

• 如上分析有如下代碼

/*** 指定位置反轉(zhuǎn)字符串* 案例 I am a software engineer 4 -> a software engineerI am* @author liaojiamin* @Date:Created in 18:47 2021/7/1*/ public class ReverPositionStr {public static void main(String[] args) {char[] target = "I am a software engineer".toCharArray();char[] result = reverPosition(target, 4);for (char c : result) {System.out.print(c);}}/*** 方案一：空間換時(shí)間* 時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)* */public static char[] reverPosition(char[] target, int position){if(target == null || target.length <= 0 || target.length <= position){return target;}char[] result = new char[target.length];int positionResult = 0;for (int i = position; i < target.length; i++) {result[positionResult++]=target[i];}for(int i=0;i<position;i++){result[positionResult++] = target[i];}return result;} }

• 如上案例實(shí)現(xiàn)，遍歷一次數(shù)組即可完成復(fù)制，因此時(shí)間復(fù)雜度O(n)，空間復(fù)雜度顯然是O(n)

方案二：多次翻轉(zhuǎn)

• 依據(jù)第一題中的思路，有如下分析：
  • 既然需要翻轉(zhuǎn)指定位置，我們可以將本字符串看成是兩個(gè)單詞，
  • 本次單詞通過(guò)指定的位置進(jìn)行拆分，這樣理解的話就和第一題是一模一樣的
  • 我們依然多次翻轉(zhuǎn)，第一次全文翻轉(zhuǎn)，得到一個(gè)順序上是正確的字符
  • 第二次，依據(jù)指定位置4，此時(shí)的位置應(yīng)該是 length-1-4+1 ~length-1的位置翻轉(zhuǎn)
  • 第三次，翻轉(zhuǎn)0~length-1-4 的位置，得到我們需要的值

• 如上分析有如下代碼：

/*** 指定位置反轉(zhuǎn)字符串* 案例 I am a software engineer 4 -> a software engineerI am* @author liaojiamin* @Date:Created in 18:47 2021/7/1*/ public class ReverPositionStr {public static void main(String[] args) {char[] target = "I am a software engineer".toCharArray();char[] result_1 = reverPositionTwice(target, 4);for (char c : result_1) {System.out.print(c);}}/*** 方案二：反轉(zhuǎn)兩次* 時(shí)間復(fù)雜度O(n)** */public static char[] reverPositionTwice(char[] target, int position){if(target == null || target.length <= 0 || target.length <= position){return target;}target = reverAll(target, 0, target.length -1);target = reverAll(target, 0, target.length-1 - position);target = reverAll(target, target.length-1 - position + 1, target.length-1);return target;}/*** 按指定位置反轉(zhuǎn)* */public static char[] reverAll(char[] target, int start, int end){while (start < end){char temp = target[start];target[start] = target[end];target[end] = temp;start++;end--;}return target;} }

上一篇：數(shù)據(jù)結(jié)構(gòu)與算法–有序數(shù)組中找出和為s的兩個(gè)數(shù)字
下一篇：數(shù)據(jù)結(jié)構(gòu)與算法–判斷撲克牌是否順子

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法--翻转单词顺序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。