leetcode
leetcode 301 ~ 350
反转字符串

反转字符串

难度:

标签:

题目描述

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

 

示例 1:

输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

输入:s = ["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

 

提示:

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符

代码结果

运行时间: 18 ms, 内存: 21.1 MB


/**
 * This implementation utilizes Java Streams to reverse an array of characters.
 * However, since streams are not directly suitable for in-place modification,
 * we first convert the character array to a List, reverse the List, and then convert it back.
 * Note: This method uses extra space due to conversion between List and array.
 */
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
 
public class Solution {
    public void reverseString(char[] s) {
        // Convert array to list
        List<Character> list = Arrays.asList(toCharacterArray(s));
        // Reverse the list
        Collections.reverse(list);
        // Convert list back to array
        for (int i = 0; i < list.size(); i++) {
            s[i] = list.get(i);
        }
    }
 
    private Character[] toCharacterArray(char[] s) {
        Character[] charObjectArray = new Character[s.length];
        for (int i = 0; i < s.length; i++) {
            charObjectArray[i] = s[i];
        }
        return charObjectArray;
    }
}

解释

方法:

这个题解采用了双指针的思路。定义两个指针分别指向字符串的起点和终点,然后不断交换两个指针指向的字符,同时将两个指针向中间移动,直到两个指针相遇。这样就实现了反转字符串的目的。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么选择使用双指针方法来解决字符串反转的问题?有没有其他可能的方法?
双指针方法用于字符串反转问题因为它能够高效地在原地(不使用额外空间)完成操作,是时间复杂度为O(n)和空间复杂度为O(1)的解决方案。此外,存在其他方法如使用栈,每次迭代将字符放入栈中,然后再将其弹出到一个新的字符串中,但这需要额外的空间;还可以简单地使用字符串或列表的内置函数(例如Python中的`reversed`或切片`s[::-1]`),但这些通常不满足原地修改的要求。
🦆
在双指针方法中,使用负索引`-i-1`来访问数组的尾部元素是如何工作的?具体是怎样计算出对应的索引位置?
在Python中,负索引用于从列表的末尾开始访问元素。索引`-i-1`的计算方式是,`-1`是列表中最后一个元素的索引,`-i-1`则表示从最后一个元素开始向左移动`i`个位置。例如,在列表`['a', 'b', 'c', 'd']`中,索引`-1`对应元素`'d'`,`-2`对应`'c'`,依此类推。这种索引方式简化了对列表尾部的访问,使代码更简洁易读。
🦆
双指针交换字符的过程中,是否需要担心出现越界错误?如果需要,如何确保在交换过程中不会发生越界?
在双指针方法中,通过精确计算循环条件`i < len(s)//2`确保不会出现越界错误。这个条件确保了指针`i`始终指向数组的前半部分,而`-i-1`始终有效地指向对应的后半部分元素。因此,在索引有效的范围内操作,避免了越界的风险。
🦆
这种原地反转的方法是否适用于所有类型的字符数组,包括包含特殊字符或Unicode字符的数组?
这种原地反转的方法适用于所有类型的字符数组,包括包含特殊字符或Unicode字符的数组。在Python中,字符串实际上是Unicode字符序列,而列表则可以容纳任意类型的对象。因此,无论字符数组包含的是ASCII字符、扩展的Latin字符、汉字、表情符号等Unicode字符,双指针方法都能有效工作,并且不影响字符的内部表示。

相关问题

反转字符串中的元音字母

给你一个字符串 s ,仅反转字符串中的所有元音字母,并返回结果字符串。

元音字母包括 'a''e''i''o''u',且可能以大小写两种形式出现不止一次。

 

示例 1:

输入:s = "hello"
输出:"holle"

示例 2:

输入:s = "leetcode"
输出:"leotcede"

 

提示:

  • 1 <= s.length <= 3 * 105
  • s可打印的 ASCII 字符组成

反转字符串 II

给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个,则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

 

示例 1:

输入:s = "abcdefg", k = 2
输出:"bacdfeg"

示例 2:

输入:s = "abcd", k = 2
输出:"bacd"

 

提示:

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104