解析:计算机考研 986 题目解析
题目:
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]
解题思路:
这道题要求我们原地修改输入的字符数组,将其反转。我们可以使用双指针的方法来实现。具体步骤如下:
1. 初始化两个指针,一个指向字符数组的开头,一个指向结尾。
2. 不断交换两个指针所指的字符,然后向中间移动,直到两个指针相遇。
这种方法不需要额外的空间,只需要 O(1) 的额外空间,符合题目要求。
Python 代码实现:
```python
def reverseString(s):
left, right = 0, len(s) 1
while left < right:
s[left], s[right] = s[right], s[left]
left = 1
right = 1
测试样例
s1 = ["h","e","l","l","o"]
reverseString(s1)
print(s1) 输出: ["o","l","l","e","h"]
s2 = ["H","a","n","n","a","h"]
reverseString(s2)
print(s2) 输出: ["h","a","n","n","a","H"]
```
这段代码中,我们定义了一个`reverseString`函数来实现字符串反转。通过双指针方法,我们原地修改了输入的字符数组,使其达到了题目要求。
****
这道题目考察了对数组操作和双指针技巧的掌握程度。通过使用双指针,我们可以在不使用额外空间的情况下,原地修改输入的字符数组,实现字符串的反转。