LeetCode 面试经典150题---008

#### 151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
题意比较简单，就是反转单词之后使用单个空格连接。这种题一般都是普通的模拟即可，就是需要考虑的情况比较多。定义两个指针i和j，用来表示单词的首尾，k表示当前存储的下标，除了第一个单词，后面每个单词前面都需要加上一个' '，每次需要reverse一下，因为我们最后需要reverse，就可以保证顺序不变了。

class Solution {
public:
    string reverseWords(string s) {
        int i = 0, j = 0,k = 0;
        while(j < s.size()){
            j = i;
            while(j < s.size() && s[j] == ' ') j ++;
            if(j == s.size()) break;
            i = j; 
            while(j < s.size() && s[j] != ' ') j ++;
            if(k) s[k ++] = ' ';
            reverse(s.begin() + i, s.begin() + j);
            while(i < j) s[k ++] = s[i ++];
        }
        s.erase(s.begin() + k, s.end());
        reverse(s.begin(), s.begin() + k);
        return s;
    }
};

#### 6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000
经典的模拟和规律题，给你的是一个Z字形的字符串，你需要按照行读取。这种题一般就是找规律即可，首先我们可以看第一行和最后一行，我们假设此时的行数为i，i从0开始，对于第一行的每个元素，需要走2 * (row - i - 1)到达下一个元素；对于最后一行的每个元素，需要走2 * i到达下一个元素，我们对这两种情况特判即可。再来考虑一般情况，也就是不是第一行和最后一行，对于第i行，第一次到下一个元素需要走2 * (row - i - 1)，第二次到下一个元素需要走2 * i，再到下一个元素又开始重复了，因此可以定义一个k，表示奇数次数还是偶数次数。

class Solution {
public:
    string convert(string s, int numRows) {
        string res = "";
        for(int cur = 0;cur < numRows;cur ++ ){
            int step = 0,k = 1, i = cur;
            if(i == 0) step = 2 * (numRows - cur - 1), k = 0;
            else if(i == numRows - 1) step = 2 * cur,k = 0;
            if(!step) step = 1;
            if(!k){
                while(i < s.size()) res += s[i], i += step;
            }
            else{
                while(i < s.size()){
                    if(k == 1) res += s[i],i += 2 * (numRows - cur - 1),k = 2;
                    else res += s[i], i += 2 * cur,k = 1;
                }
            }
        }
        return res;
    }
};

总结，都是模拟题，不过坑不少，基本不能一次过。