[leetcode_6]ZigZag Conversion

这个题真心坑爹！！！
题意过于简单！
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.
问题根本没交代清楚。我开始以为的格式是：
X X X X
X X X X X X
…
就是第一行是一个字母中间三个空格，第二行是一个字母中间一个空格。
依次类推，我也真够会歪歪的：认为奇数行的字母数是X 偶数行的字母数是 2x-1
按照这个思路写了份代码满心欢喜的提交：
142 / 1158 test cases passed.
过了142组数据。。。呵呵呵呵呵然后 ABCD 2说我WA?
我各种看不懂，最后实在没辙，去看网上别人对题意的理解。
我擦！！！原来是说：
1 7
2 6 8
3 5 9
4
要搞成折线图。。。。。然后横着输出。。。唉。。。。╮(╯▽╰)╭。
然后呢。。。我就做呀做，用二维数组来存，变个向没有的地方放空格。。。呵呵呵。。。各种RE啊，在一些小数据上RE???不科学啊~~~后来我一想，可能是大数据RE只是刚运行到小数据而已。
最后就开始扩展，二维数组到10000*10000世界就安静了，暴了。。。
肿么办。我曾经一度不想做这个题了。
归根到底还是自己太水了。。。。
后来再一想，要么用一种数学放方法计算输出顺序，要么就是压缩空间，嘿嘿嘿，我选择了后者，我不存map的二维数组了。
我存的是每个字母的x y 和val这样空间大大压缩了。
一次AC，呵呵呵呵呵呵呵~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1、需要特殊判定一行的情况~
2、偷了懒，快排用的库里面的。
附上代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


#include <algorithm>

using namespace std;

struct Node {
    int x;
    int y;
    char val;
}p[10000];

int cmp(Node a,Node b) {
    if(a.x == b.x) {
        return a.y < b.y;
    } else {
        return a.x < b.x;
    }
}

class Solution {
public:
    string convert(string s, int nRows) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int x = 0;
        int y = 0;
        int direction = 0;
        if(nRows == 1) return s;
        for(int i = 0; i < s.length(); i++) {
            p[i].x = x;
            p[i].y = y;
            p[i].val = s[i];
            if(direction == 0) {
                x++;
                if(x >= nRows) {
                    x--;
                    direction = 1;
                    x--;
                    y++;
                }
            } else {
                x--;
                y++;
                if(x < 0) {
                    x++;
                    y--;
                    direction = 0;
                    x++;
                }
            }
        }
        sort(p, p + s.length(), cmp);
        for(int i = 0; i < s.length(); i++) {
            s[i] = p[i].val;
        }
        return s;
    }
};