美文网首页
344. 反转字符串

344. 反转字符串

作者: 一角钱技术 | 来源:发表于2020-08-25 08:51 被阅读0次

    344. 反转字符串

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

    算法思路:双指针法

    双指针法是使用两个指针,一个左指针 left,右指针 right,开始工作时 left 指向首元素,right 指向尾元素。交换两个指针指向的元素,并向中间移动,直到两个指针相遇。

    • 将 left 指向首元素,right 指向尾元素。
    • 当left<right:
      • 交换 s[left] 和 s[right]。
      • left++
      • right++

    参考代码:

    class Solution {
        public void reverseString(char[] s) {
            int left  = 0;
            int right = s.length - 1;
            while (left < right) {
                char temp = s[left];
                s[left] = s[right];
                s[right] = temp;
                left++; 
                right--;
            }
        }
    }
    

    复杂度分析

    • 时间复杂度:O(N)。执行了 N/2 次的交换。
    • 空间复杂度:O(1),只使用了常数级空间。
    部分图片来源于网络,版权归原作者,侵删。
    

    以上谢谢大家,求赞求赞求赞!

    💗 大佬们随手关注下我的wx公众号【一角钱小助手】和 掘金专栏【一角钱】 更多题解干货等你来~~

    相关文章

      网友评论

          本文标题:344. 反转字符串

          本文链接:https://www.haomeiwen.com/subject/qpaijktx.html