当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.344.Reverse String 反转字符串

LeetCode.344.Reverse String 反转字符串

题目描述

344 Reverse String
https://leetcode-cn.com/problems/reverse-string/
https://leetcode.com/problems/reverse-string/description/

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

解题过程

新字符串存储

很简单的字符串逆转,没想到竟然没能一次AC。
我第一次用的方法是挨个字符遍历然后倒序累加到新字符串中:

public String reverseString1(String s) {
    String result="";
    for(int i=0; i<s.length(); i++){
        result = s.charAt(i) + result;
    }
    return result;
}

结果最后一个测试用例不通过,超时,如下:
Time Limit Exceeded
475 / 476 test cases passed.

Massorete
Lon
a mallee
Vig
...
Falun
a r... 42490 more chars

是一个4万多字符的超长字符串,然后优化。

原地逆置

改为先转为char数组,然后首尾交换:

//char swap
public String reverseString(String s){
    char[] charStr = s.toCharArray();
    int length = s.length();
    for(int i=0; i<length/2; i++){
        char temp = charStr[i];
        charStr[i] = charStr[length-1-i];
        charStr[length-1-i] = temp;
    }
    String result = new String(charStr);
    return result;
}

提交通过了。

前后双指针

别人提交的其他不错的解法
看到一个3ms的,也是转为char数组然后交换,但比我的高端,使用首尾两个指针,代码比较漂亮:

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

        return new String(c);
    }
}

看看最快的2ms的代码:

class Solution {
    public String reverseString(String s) {
        char[] charArray = s.toCharArray();
        char[] charArray_2 = new char[charArray.length];
        for (int i = 0; i < charArray.length; i++) {
            charArray_2[charArray_2.length-i-1] = charArray[i];
        }
        return new String(charArray_2);
    }
}

看来用char数组的确是最快的。

Collections.reverse()

还有个43ms的,用java集合操作提供的reverse方法:

public class Solution {
    public String reverseString(String s) {
        List<String> list =  Arrays.asList(s.split(""));
        Collections.reverse(list);

        return String.join("",list);
    }
}

最后还用了Stringjoin方法,是java8中新增的方法,高端!我觉得这个很好啊,有现成的干嘛不用,一开始我也想用来着,只不过没找到reverse()方法在哪个类中,所以还顺便学习了一下java.util.Collections类的用法。

不过后来知道,直接用StringBuffer类或StringBuilder类的reverse()方法即可,所以最简洁的代码如下:

class Solution {
    public String reverseString(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

也只用了4ms而已。


GitHub代码

algorithms/leetcode/leetcode/_344_ReverseString.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_344_ReverseString.java


上一篇 LeetCode.657.Robot Return to Origin 机器人能否返回原点

下一篇 LeetCode

阅读
评论
635
阅读预计3分钟
创建日期 2018-01-02
修改日期 2018-01-11
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论