LeetCode
今天依旧是一道简单难度的题目, 腾讯校招精选的 50 题简单难度部分即将完结, 继续加油吧
题目
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路
这道题在此前是返回字符数组, 但现在换成了原地修改, 无返回值. 这使得高级函数的使用都被限制住了, 如果可以返回字符数组, 那么在 Python 中可以直接用return s[::-1] 这条语句即可实现反转, 在 Java 等高级语言中也有 reverse() 这样的函数.
现在题目修改之后, 思路被限定了, 你需要使用两个指针来进行数据交换. 遍历半个数组, 依次交换两个数即可.
遗憾的是, LeetCode 在这道题的解答排名上尚未舍弃之前允许返回值的解答, 我无法判断这种解法是否最优, 如有更优解法, 欢迎留言告知.
如下图所示, 排名靠前的解答并不符合现在的题目
示意
实现
尽管我已经尽量优化语句, 如在 Python 中使用这样 s[i], s[j] = s[j], s[i] 的数据交换方式而不是借由中间变量交换以节省时间, 但仍然消耗了 196 ms的时间, 而实际上算法的时间复杂度仅有O(n/2)
C语言
void reverseString(char* s, int sSize) {
int temp;
for(int i=0; i<sSize/2; i++){
temp = s[i];
s[i] = s[sSize-i-1];
s[sSize-i-1] = temp;
}
}
Python
class Solution:
def reverseString(self, s):
"""
:type s: List[str]
:rtype: void Do not return anything, modify s in-place instead.
"""
j = len(s)-1
for i in range(int(len(s)/2)):
s[i], s[j] = s[j], s[i]
j -= 1
i += 1
