当前位置 : 首页 » 文章分类 :  开发  »  LeetCode.344.Reverse String

LeetCode.344.Reverse String


题目描述

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = “hello”, return “olleh”.


解题过程

很简单的字符串逆转,没想到竟然没能一次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数组的确是最快的。
还有个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代码


上一篇 java.util.Collections

下一篇 LeetCode-已做题目索引

阅读
545
阅读预计3分钟
创建日期 2018-01-02
修改日期 2018-01-11
类别
百度推荐