LeetCode_6: ZigZag Conversion

# 引言

题目链接：https://leetcode.com/problems/zigzag-conversion/description/

# 题目大意

给出一个字符串, 和一个指定行数, 将字符串纵向按照z字形排列(指定行数为z字形大小)

• Example

s = "PAYPALISHIRING", numRows = 3

Output: "PAHNAPLSIIGYIR"

# 题解

# 一句话题解

一个规律题, 按照Z字形排列图, 逐行扫描, 推断每一行下一个出现字母的索引的位置即可。

具体规律见图

复杂度O(n)

# AC代码

c++版本

class Solution
{
  public:
    string convert(string s, int numRows)
    {
        int len = s.length();
        if (len <= 1 || len <= numRows || numRows <= 1)
        {
            return s;
        }
        char rStr[len + 1];
        memset(rStr, '\0', sizeof(rStr));
        for (int i = 0, j = 0; i < numRows; ++i)
        {
            int k = i;
            // 逐行扫描
            if (0 == i || numRows - 1 == i)
            {
                while (k < len)
                {
                    rStr[j++] = s[k];
                    k += (numRows - 1) * 2;
                }
            }
            else
            {
                while (k < len)
                {
                    rStr[j++] = s[k];
                    int h = k + (numRows - i - 1) * 2;
                    if (h < len)
                    {
                        rStr[j++] = s[h];
                    }
                    k += (numRows - 1) * 2;
                }
            }
        }
        return string(rStr);
    }
};

go版本

func convert(s string, numRows int) string {
    lens := len(s)
	if lens <= 1 || lens <= numRows || numRows <= 1 {
		return s
	}
	rStr := make([]byte, lens)
	index := 0
	for i := 0; i < numRows; i = i + 1 {
		k := i
		if  0 == i || numRows - 1 == i {
			for k < lens {
				rStr[index] = s[k]
				index = index + 1
				k = k + (numRows - 1) * 2
			}
		} else {
			for k < lens {
				rStr[index] = s[k]
				index = index + 1
				h := k + (numRows - i - 1) * 2
				if h < lens {
					rStr[index] = s[h]
					index = index + 1
				}
				k = k + (numRows - 1) * 2
			}
		}
	}
	return string(rStr)
}