題目一：翻轉(zhuǎn)單詞順序。
輸入一個英文句子矛绘，翻轉(zhuǎn)句子中單詞的順序耍休，但單詞內(nèi)字符的順序不變。為簡單起見货矮，標(biāo)點(diǎn)符號和普通字母一樣處理羊精。例如輸入字符串"I am a student."，則輸出"student. a am I"囚玫。
練習(xí)地址
https://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3
https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/
參考答案
public class Solution {
public String ReverseSentence(String str) {
if (str == null || str.length() == 0) {
return str;
}
char[] data = str.toCharArray();
// 翻轉(zhuǎn)整個句子
reverse(data, 0, data.length - 1);
// 翻轉(zhuǎn)句子中的每個單詞
int start = 0, end = 0;
while (start < data.length) {
if (data[start] == ' ') {
start++;
end++;
} else if (end == data.length || data[end] == ' ') {
reverse(data, start, end - 1);
start = ++end;
} else {
end++;
}
}
return new String(data);
}
private void reverse(char[] data, int start, int end) {
while (start < end) {
char temp = data[start];
data[start] = data[end];
data[end] = temp;
start++;
end--;
}
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(mn)喧锦。
- 空間復(fù)雜度：O(n)。
題目二：左旋轉(zhuǎn)字符串
字符串的左旋轉(zhuǎn)操作是把字符串前面的若干個字符轉(zhuǎn)移到字符串的尾部抓督。請定義一個函數(shù)實現(xiàn)字符串左旋轉(zhuǎn)操作的功能燃少。比如，輸入字符串"abcdefg"和數(shù)字2铃在，該函數(shù)將返回左旋轉(zhuǎn)兩位得到的結(jié)果"cdefgab"阵具。
練習(xí)地址
https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec
https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
參考答案
public class Solution {
public String LeftRotateString(String str, int n) {
if (str == null || str.length() == 0 || n < 1 || n >= str.length()) {
return str;
}
char[] data = str.toCharArray();
// 翻轉(zhuǎn)字符串的前面 n 個字符
reverse(data, 0, n - 1);
// 翻轉(zhuǎn)字符串的后面部分
reverse(data, n, data.length - 1);
// 翻轉(zhuǎn)整個字符串
reverse(data, 0, data.length - 1);
return new String(data);
}
private void reverse(char[] data, int start, int end) {
while (start < end) {
char temp = data[start];
data[start] = data[end];
data[end] = temp;
start++;
end--;
}
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n)。
- 空間復(fù)雜度：O(n)。
