練習運用How to: Work at Google - Example Coding/Engineering interview 摘要的技巧處理字串反轉問題。
寫下問題
A:Build a function to reverse the given string. e.g. input:Hello output:olleH input:Show me the money output:yenom eht em wohS
提出問題
Q:字串的長度?
A:很長,超過一萬字的長度。
Q:字串會是空字串或是null嗎?
A:不會是null,可能會是空字串。
Q:有無記憶體限制?
A:假設沒有記體體限制。
Q:所以輸出的結果也是字串?
A:是,但必須是順序顛倒過來的。
先想到的解法
先想到的是直接用函式庫提供的方法。
Main.java
package com.abc.demo;
public class Main {
public static void main(String[] arges) {
System.out.println(reverse("Hello")); // olleH
System.out.println(reverse("Show me the money")); // yenom eht em wohS
}
public static String reverse(String str) {
return new StringBuilder(str).reverse().toString();
}
}
當然不能用函式庫,所以直覺是建立另一個字元陣列,然後從原字串最後一個字開始依序塞到新的陣列。
Main.java
package com.abc.demo;
public class Main {
public static void main(String[] arges) {
System.out.println(reverse("Hello")); // olleH
System.out.println(reverse("Show me the money")); // yenom eht em wohS
}
public static String reverse(String str) {
char[] chars = new char[str.length()]; // 建立一個與輸入字串同長度的字元陣列 O(n)
for (int i = str.length() - 1; i >= 0; i--) { // 遍歷字串,從最後開始走 O(n)
chars[(str.length() - 1) - i] = str.charAt(i); // 放到新的字元陣列 O(1)
}
return new String(chars); // O(1)
}
}
時間及空間複雜度
一個迴圈,大小為輸入字串的長度,時間複雜度為O(n),為線性(linear)。
建立一個同輸入字串長度的陣列,空間複雜度為O(n)。
更加解
將字串前後對稱位置兩兩直接對調。
┌───────────────┐
│ ┌───────┐ │
▼ ▼ ▼ ▼
┌───┬───┬───┬───┬───┐
│ H │ e │ l │ l │ o │
└───┴───┴───┴───┴───┘
不考慮str.toCharArray()
函式內部複雜度的情況。建立一個暫存交換字元用的變數tmp
時間O(1),空間O(1);使用輸入字串長度的一半跑回圈做頭尾字元交換為O(n/2),不過計算複雜度去除乘數仍為O(n)。
Main.java
public class Main {
public static void main(String[] arges) {
System.out.println(reverse("Hello")); // olleH
System.out.println(reverse("Show me the money")); // yenom eht em wohS
}
public static String reverse(String str) {
char[] chars = str.toCharArray(); // 取得字串的字元陣列
char tmp; // 建立一個字元變數用來作待會頭尾字元交換時的暫存空間
for (int i = 0; i < chars.length/2; i++) { // 迴圈輸入字串的一半長度即可
tmp = chars[i]; // 將第一個字元放到暫存變數
chars[i] = chars[(chars.length - 1) - i]; // 將最後一個字元放到第一個索引
chars[(chars.length - 1) - i] = tmp; // 將暫存變數的字元放到最後的索引。
}
return new String(chars); // 將字元陣列轉為字串
}
}
沒有留言:
張貼留言