LEETCODE 344. Reverse String 解题思路分析

题目大意:

反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=344

解题思路分析:

这是一道简单题目,不过题目要求使用原地算法,这也就意味着我们不能使用额外的存储空间来辅助解题。对于本题,翻转字符串,实际上就是将数组中相对称的两位上的字符进行交换。解题时,我们定义左右两个指针,初始时,左指针指向0,右指针指向数组最后一位,当左指针小于右指针时保持循环,我们交换左右指针指向的两个字符,然后左指针加一,右指针减一,重复上述步骤直到循环结束。

另外,为了更加节省空间,我们在交换两个字符时可以使用位运算,这样可以省去创建额外变量的空间,之前的文章我们多次介绍过,交换两个字符的值可以通过以下异或运算的代码来实现:

a^=b;
b^=a;
a^=b;

// 普通写法:
int temp = a;
a = b;
b = temp;

实现代码:

public void reverseString(char[] s) {
    // 定义左右两个指针
    int left=0,right=s.length-1;
    while(left<right){
        // 交换两个指针指向的字符
        s[left]^=s[right];
        s[right]^=s[left];
        s[left]^=s[right];
        left++; // 左指针加一
        right--; // 右指针减一
    }
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 96.80% of Java online submissions for Reverse String.

Memory Usage: 43.3 MB, less than 99.41% of Java online submissions for Reverse String.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-344-reverse-string-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

LEETCODE 344. Reverse String 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 541. Reverse String II 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。