Leetcode_14 天算法入门_day4

为什么第四天的主题还是 two pointers，有点腻了。

腻了也还是要肝😐

344. Reverse String

Analysis

这个题可太常见了。

Code

method 1

/* method 1: use a array to copy */
class Solution {
public:
    void reverseString(vector<char>& s) {
        vector<char> ret;
        for(int i = s.size() - 1; i >= 0; i--) {
            ret.push_back(s[i]);
        }
        s = ret;
    }
};

method 2

/* method 2: just exchange the elements */
class Solution {
public:
    void reverseString(vector<char>& s) {
        int size = s.size();
        for(int i = 0; i < size / 2; i++) {
            char tmp = s[size - i - 1];
            s[size - i - 1] = s[i];
            s[i] = tmp;
        }
    }
};
/* also can write like this */
class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while(left < right) {
            swap(s[left++], s[right--]);
        }
    }
};

557. Reverse Words in a String III

Analysis

这个题稍微复杂一点，要将每个单词反转，但不能改变单词的绝对位置。
反转单词的任务就交给上个题得到的 reverse 函数了，剩下要解决的问题就是如何找到单词了。不过，与其说是找单词，不如说是找空格，只要找到第一个不是空格的字符，然后在找到下一个空格字符，那么这中间的内容就是单词了。

Code

reverse 函数就不写了，直接吃现成的。

class Solution {
public:
    string reverseWords(string s) {
        int len = s.length();
        for(int i = 0; i < len; i++) {
            if(s[i] != ' ') {
                int j;
                for(j = i + 1; j < len; j++) {
                    if(s[j] == ' ') break;
                }
                reverse(s.begin() + i, s.begin() + j);
                i = j;
            }
        }
        return s;
    }
};

Summary

今天给的是两道简单题，都比较简单。第二个题目稍微难一点点，而且第一个题得到的东西可以直接在第二个题目里面用到，这种安排很不错。如果直接做第二个题，说不定会想到其他地方去。
PS：第二个题，用栈也能做。

---