- 題目：
- 解題思路：
- Python代碼
- Java代碼
- C++代碼
- 復雜度分析
題目：
Write a function that reverses a string. The input string is given as an array of characters s.
寫一個反轉字串的函式，輸入字串以字符陣列的形式給出，
Example 1:
Input: s = [“h”,“e”,“l”,“l”,“o”]
Output: [“o”,“l”,“l”,“e”,“h”]
示例 1：
輸入：[“h”,“e”,“l”,“l”,“o”]
輸出：[“o”,“l”,“l”,“e”,“h”]
Example 2:
Input: s = [“H”,“a”,“n”,“n”,“a”,“h”]
Output: [“h”,“a”,“n”,“n”,“a”,“H”]
示例 2：
輸入：[“H”,“a”,“n”,“n”,“a”,“h”]
輸出：[“h”,“a”,“n”,“n”,“a”,“H”]
Constraints:
1 <= s.length <=
1
0
5
10^5
105
s[i] is a printable ascii character.
提示:
1 <= s.length <=
1
0
5
10^5
105
s[i] 是可列印的ASCII字符.
Follow up:
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
進階：
不要為其他陣列分配額外的空間，為此，必須使用O(1)額外記憶體就地修改輸入陣列，
解題思路：
方法：雙指標
觀察給出的示例，得出當n為字符陣列長度時s[i]的字符與s[n-1-i]的字符互換了，我們定義left指向字符陣列的第一個元素，right指向字符陣列的最后一個元素，當left<right時：s[left]和s[right]進行交換且left右移一位、right左移一位，當left>=right時，結束回傳字符陣列，
Python代碼
class Solution:
def reverseString(self, s: List[str]) -> None:
left, right = 0, len(s) - 1
while(left < right):
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
Java代碼
class Solution {
public void reverseString(char[] s) {
int n = s.length;
for (int left = 0, right = n - 1; left < right; ++left, --right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
}
}
}
C++代碼
class Solution {
public:
void reverseString(vector<char>& s) {
int n = s.size();
for (int left = 0, right = n - 1; left < right; ++left, --right) {
swap(s[left], s[right]);
}
}
};
復雜度分析
時間復雜度：O(N)，其中 n為字符陣列的長度，進行了 n/2次的交換，
空間復雜度：O(1)，只需常數空間存放若干變數，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/295629.html
標籤：java
下一篇：如何解決服務之間的通信問題？