图片 1Screenshot
from 2016-02-29 10:41:32.png

Given an input string, reverse the string word by word. A word is
defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the
words are always separated by a single space.
For example,
Given s = “the sky is blue”,
return “blue is sky the”.
Could you do it in-place without allocating extra space?

图片 2

这道题有In place and non In place两种做法。in
place的做法是,先把所有单词逐一翻转,再最后翻转整个句子(151由于空格,需要extra
check)

Given an input string, reverse the string word by word.

My code:

思路:
要求是否可以不需要额外空间,即只在原来的char数组上操作。
首先可以把整个char数组反转,然后再对每个单词进行反转。
反转可以用一个函数reverse实现。
找每个需要反转的单词可以通过双指针结合游标的方式实现。

My code:

In place:

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

public class Solution { public void reverseWords { if (s == null || s.length == 0) return; int begin = s.length - 1; int end = s.length - 1; while (end >= 0) { char curr = s[end]; if (begin == end) { if (curr == ' ') { end--; begin--; } else { end--; } } else { if (curr == ' ') { reverse(s, end + 1, begin); end--; begin = end; } else { end--; } } } if (begin >= 0) { reverse(s, 0, begin); } reverse(s, 0, s.length - 1); } private void reverse(char[] s, int begin, int end) { if (s == null || s.length == 0 || begin > end) return; while (begin < end) { char temp = s[begin]; s[begin] = s[end]; s[end] = temp; end--; begin++; } return; }}
public void reverseWords(char[] str) {
    if (str == null || str.length == 0) {
        return;
    }

    reverse(str, 0, str.length - 1);

    //寻找单词的双指针,i是游标
    int wordStart = 0, wordEnd = 0;
    for (int i = 0; i < str.length; i++) {
        if (str[i] != ' ') {
            wordEnd = i;
        }
        if (str[wordStart] == ' ' && str[i] != ' ') {
            wordStart = i;
        }
        if (str[i] == ' ' || i == str.length - 1) {
            if (str[wordStart] != ' ' && str[wordEnd] != ' ') {
                reverse(str, wordStart, wordEnd);
                wordStart = wordEnd = i + 1;
            }
        }
    }
}

private void reverse(char[] str, int start, int end) {
    while (start < end) {
        char tmp = str[start];
        str[start++] = str[end];
        str[end--] = tmp;
    }
}
public class Solution { public String reverseWords { if (s == null) return null; else if (s.length return s; int i = s.length() - 1; int temp = i; String reverse = ""; while (i >= 0) { if ((i + 1 < s.length && s.charAt == ' ' && s.charAt != ' ') reverse += s.substring(i + 1, temp + 1) + " "; else if ((s.charAt != ' ' && i + 1 < s.length && s.charAt == ' ') temp = i; i--; } if (s.charAt != ' ') reverse += s.substring(0, temp + 1); if (s.charAt != ' ' && reverse.charAt(reverse.length == ' ') return reverse.substring(0, reverse.length; return reverse; } public static void main(String[] args) { Solution test = new Solution(); System.out.println(test.reverseWords; }}
class Solution {
public:
    void reverseWords(string &s) {
        if(s.empty()) return;
        int left = 0;
        for(int i=0; i<=s.length(); i++){
            if(i == s.length() || s[i] == ' '){
                myReverse(s, left, i-1);
                left = i+1;
            }
        }
        reverse(s.begin(), s.end());
    }

    void myReverse(string &s, int start, int end){
        while(start < end){
            swap(s[start], s[end]);
            start++; end--;
        }
    }
};
public String reverseWords(String s) {
    if (s == null || s.length() <= 1) {
        return s;
    }

    String res = "";
    String[] words = s.trim().split(" +");
    for (int i = words.length - 1; i >= 0; i--) {
        res += words[i] + " ";
    }

    return res.trim();
}

之前做过类似的题目,但是用了额外空间。

My test result:

In place with character array:

希望这周有好运。

图片 3Paste_Image.png

class Solution {
public:

    void reverse_util(vector<char>& str, int left, int right) {
        reverse(str.begin() + left, str.begin() + right);
    }

    void reverseWords(vector<char>& str) {
        if(str.empty()) {
            return;
        }

        int left = 0;
        for(int i=0; i<=str.size(); i++) {
            if(i == str.size() || str[i] == ' '){
                reverse_util(str, left, i);
                left = i+1;
            }
        }
        reverse(str.begin(), str.end());
    }
};

Anyway, Good luck, Richardo!

这道题目好奇怪。我就遍历了一次数组。。。跑的时间这么慢。写的我心情很糟糕了。题目本身没什么难度。

With extra memory:

My code:

**总结: String**

class Solution {
public:
    void reverseWords(string &s) {
        if(s.empty()) return;
        int cur_len = 0;
        string ret = "";
        for(int i=s.length()-1; i>=0; i--){
            if(s[i] == ' '){
                if(cur_len == 0) continue;
                else{
                    string word = s.substr(i+1, cur_len);
                    ret += word;
                    ret += ' ';
                    cur_len = 0;
                }
            }else{
                cur_len++;
            }
        }
        if(cur_len > 0) ret += s.substr(0, cur_len);
        s = ret;
        while(s.length() > 1 && s[0] == ' ') s.erase(0, 1);
        while(s.back() == ' ') s.pop_back();
    }
};
public class Solution { public void reverseWords { if (s == null || s.length == 0) { return; } reverse(s, 0, s.length - 1); int begin = 0; for (int i = 0; i < s.length; i++) { if (s[i] == ' ') { reverse(s, begin, i - 1); begin = i + 1; } } reverse(s, begin, s.length - 1); } private void reverse(char[] s, int begin, int end) { int i = begin; int j = end; while  { char temp = s[i]; s[i] = s[j]; s[j] = temp; i++; j--; } }}

Anyway, Good luck, Richardo!

不知道为什么之前代码写的那么复杂,是做 rotate array
转而过来做这道题目的。

My code:

还有,一些私有方法, private,其实不需要有太多的input check.public method
should check if input is valid or not

public class Solution { public String reverseWords { if (s == null || s.length { return s; } char[] c = s.toCharArray(); reverse(c, 0, c.length - 1); int begin = 0; int end = 0; while (end < c.length) { if (c[end] == ' ') { if (begin == end) { begin++; end++; } else { reverse(c, begin, end - 1); begin = end + 1; end = begin; } } else { end++; } } if (begin < c.length) { reverse(c, begin, c.length - 1); } StringBuilder ret = new StringBuilder(); int i = 0; while (i < c.length) { if (c[i] != ' ') { ret.append; i++; } else { if (ret.length { i++; continue; } ret.append; while (i < c.length && c[i] == ' ') { i++; } } } if (ret.length() > 0 && ret.charAt(ret.length == ' ') ret.deleteCharAt(ret.length; return ret.toString(); } private void reverse(char[] c, int i, int j) { int begin = i; int end = j; while (begin < end) { char temp = c[begin]; c[begin] = c[end]; c[end] = temp; begin++; end--; } }}

Anyway, Good luck, Richardo! — 09/12/2016

思路很明显,就是reverse但是 corner case
很多。我为了完全不用Java自带的高级方法,所有东西都是通过数组实现。其实
leading and trailing spaces 可以用 string.trim()
消除。但是又得新生成一个string,效率低。

所以,最后得判断下,末尾是否有 空格, 如果有,那么删除之。

Anyway, Good luck, Richardo! — 09/12/2016

My code:

public class Solution { public String reverseWords { if (s == null || s.length { return s; } StringBuilder sb = new StringBuilder(); for (int start = s.length() - 1; start >= 0; start--) { char curr = s.charAt; if (curr == ' ') { continue; } int end = start; while (start >= 0 && s.charAt != ' ') { start--; } sb.append(s.substring(start + 1, end + 1) + " "); } return sb.toString; }}

reference:

还是选择用一些更加简单地方法来做,避免面试的时候写出bug

Anyway,Good luck, Richardo! — 09/25/2016

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图