[算法练习]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".

 

程序代码：

#include <gtest/gtest.h>

using namespace std;

string convert(string s, int numRows)

{

    if (s.empty() || (numRows < 2))

    {

        return s;

    }

    string result;

    int length = s.length();

    char* data = new char[length*numRows];

    memset(data,0,length * numRows);

    int delta = 0;

    int offset = 0;

    int flag = 1;

    for (int i= 0; i<length; ++i)

    {

        data[offset + delta * length] = s[i];

        if ( (delta+flag) >= numRows)

        {

            flag = -1;

        }

        else if ((delta+flag) < 0)

        {

            flag = 1;

        }

        delta += flag;

        if (flag == -1)

        {

            offset ++;

        }

    }

    for (int i=0; i<numRows; ++i)

    {

        for (int j=0; j < length; ++j)

        {

            if (data[j+i*length])

                result += data[j+i*length];

        }

    }

    delete data;

    return result;

}

TEST(Pratices, tZigZagConversion)

{

    // ''=> ''

    // ABCDEFG 3 => A   E  => AEBDFCG

    //              B D F

    //              C   G

    ASSERT_EQ(convert("",1),"");

    ASSERT_EQ(convert("ABCDEFG",1),"ABCDEFG");

}