LeetCode 6. Z字形变换

题目描述

思路

把整个问题拆解为： 存储-取 的两个过程；

存储

通过观察我发现的是，当numRows为3时，两列之间的数字的数目为1；当numRows为4时，两列之间的数字的数目为2，以此类推。那么，可不可以将每一列都存起来（col），两列之间的数字也存起来（gap），最后要输出时再通过遍历的方式拼接出结果呢？

以题目中给的字符串PAYPALISHIRING为例子，将每一列（col）和它右边的两列之间的数字（gap）作为一组：

存储完为：

一个需要注意的问题

一个需要注意的问题是，有可能在遍历完输入的字符串的时候，没有来得及存储当前的子数组，这个时候可以通过引入一个遍历，在循环外补充最后一次的存储操作（详见代码）；

取

取首尾两行

那么，接下来，可以先取首行和尾行的字符串拼接成head和tail，因为首尾两行是不涉及两列之间的数据的，由上图就可以知道:

首尾两行也就是二维数组col中，每一个子数组的第一个元素即为首，最后一个元素即为尾；

取中间的行

如果要取中间的行，就会发现其实上面中，那样存储时，gap这个是错的，因为，在存储时，是按照原来字符串的字符顺序存储的，比如gap的第一个子数组['A', 'L']，但是，在得出结果时，是先遍历得到第二行的L，然后才是第三行的A。因此，在存储gap的时候，需要对每个子数组进行逆序操作，正确的存储结果应该为：

遍历出第二行的结果为：ALSIG， 第三行结果为: YAHR

---

代码

string charToStr(char c){ // 将char转成string, 需要引入 <sstream>头文件
    stringstream stream;
    stream << c;
    return stream.str();
}


string convert(string s, int numRows) {
    if (numRows == 1){
        return s;
    }

    int s_sz = s.size();

    if (s_sz == 0 || s_sz == 1)
        return s;

    ///////////////     存储的过程     ////////////////////


    int gap_num = numRows - 2;  // numRows:3，gap_num:1
                                // numRows:4，gap_num:2
    // 3 1 3 1 3 1 ;  每一个3代表了含有三个数据的数组，如[PAY] 
    vector<vector<char>> col; // 存储每一列的数据，如[PAY] [ALI] [HIR]
    vector<vector<char>> gap; // 存储列与列之间的数据，如[P] [S] [I]

    vector<char> tmp_col(numRows);
    vector<char> tmp_gap(gap_num);

    int flag = 0; // 有可能出现i==s_sz，但是没有存储对应的tmp_col和tmp_gap的情况

    for (int i = 0, j = 0, m = 0, n = 0; i < s_sz; ){ // j控制一维数组的下标， m控制列， n控制gap
        flag = 0;

        if (m != numRows){  
            tmp_col[m] = s[i];
            m ++;
            i++;


        }
        else{ // 列遍历完了

            if (n != gap_num){
                tmp_gap[n] = s[i];
                n++;
                i++;


            }
            else{ // m == numRows && n == gap_num
                flag = 1;

                col.push_back(tmp_col);
                tmp_col.clear();
                tmp_col.resize(numRows);

                // gap数据需要逆序一下再存入，因为输出的时候是按行从上到下输出的
                reverse(tmp_gap.begin(), tmp_gap.end());
                gap.push_back(tmp_gap);
                tmp_gap.clear();
                tmp_gap.resize(gap_num);

                m = 0;
                n = 0;
                j++;

            }
        }
    }

    if (flag == 0){ // 如果最后一次，没有存储tmp_col和tmp_gap
        col.push_back(tmp_col);

        reverse(tmp_gap.begin(), tmp_gap.end());
        gap.push_back(tmp_gap);
    }


    ///////////////     取字符的过程     ////////////////////

    // 空的部分为'\0'，不进行处理

    int set_num = s_sz / (numRows + gap_num); // 组数，不包括多余的
    if (s_sz % (numRows + gap_num) != 0)
        set_num += 1;

    //先取出首尾两行
    string head = "", tail = "";
    for (int i = 0; i < set_num; i++){
        if (col[i][0] != '\0'){
            head = head + charToStr(col[i][0]);
        }

        if (col[i][numRows - 1] != '\0'){
            tail = tail + charToStr(col[i][numRows - 1]);
        }
    }

    // 拼中间的
    string mid = "";
    for (int i = 1; i < numRows - 1; i++){ // i: 从1到numRows-2  每一个小数组的下标
        for (int j = 0; j < set_num; j++){ // j: 从0到set_num   组数
            if (col[j][i] != '\0'){
                mid = mid + col[j][i];
            }
            if (gap[j][i - 1] != '\0'){
                mid = mid + gap[j][i - 1];
            }
        }
    }

    string res = head + mid + tail;

    return res;
}