LeetCode

问题：

6. Z字形变换

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

分析：

A 仿真方法

直接模拟整个过程，首先根据字符串大小和行数确定整体所在的行和列，初始化为某一个用不到的字符，比如#，然后按照给定的规则，即Z字型填充，填充完成后每行的结果剔除掉占位符#，重组为最终结果即可。

其中：

1.行数numRows，则2*numRows-1为一个周期，行号上先向下递增，到numRows后向上递减，列号上前面numRows个相同，后面递增

2.每个周期为一组，则groupsize=2*numRows-1,groupwidth=1 + numRows - 2

B 数学方法

按照数字写下了后可以发下如下规律：

0				8				16				24
1			7	9			15	17			23	26
2		6		10		14		18		22		27		31
3	5			11	13			19	21			28	30
4				12				20				29

1.行与行之间没有影响关系，比如上表中，5在4的右上方和正上方没有区别

2.对于行数numRows，第一行都是坐标为2*（numRows-1）的整数倍，即假设用vector<string> tmp 存储临时的每一行数据，则对于所有的j%(2*numRows-1)==0,s[j]在tmp[0]中

3.类似的，如果余数±m，则在tmp[m]中，比如对于7和9，对8求模可以视为±1，都在tmp[1]中。

4.简化一下，numRows行，对于str中的第i个元素，则满足：

如果mod1=i%(2*numRows-2)<=numrows-1,则在tmp[mod1]行

否则在tmp[2*numRows-2-mod1]行

AC Code：

class Solution {

public:

	string convert(string s, int numRows) {

        if (numRows == 1)

		{

			return s;

		}

		string ret = "";

		int length = s.size();

		int col = GetColumn(length,numRows);

		//char chars[][] = new char[numRows][col];

		string initstr = "";

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

		{

			initstr += "#";

		}

		vector<string> tmp(numRows,initstr);

		int groupsize = 2 * numRows - 2; //一组的个数，一整列整列减去2

		int groupwidth = 1 + numRows - 2; //本身一列，去掉头尾各占一列

		if (s.size() <= groupsize)

		{

			FileGroup(tmp, s, 0);

		}

		else

		{

			string tmpstr = "";

			int index = 0;

			int rolnum = 0;

			while (true)  //每次取一组处理

			{

				if (index+ groupsize >= s.size())

				{

					tmpstr = s.substr(index, s.size() - index);

					FileGroup(tmp, tmpstr, rolnum);

					break;

				}

				tmpstr = s.substr(index, groupsize);

				FileGroup(tmp, tmpstr, rolnum);

				index += groupsize;

				rolnum += groupwidth;

			}

		}

		for (int i = 0; i < tmp.size(); i++)

		{

			ret += GenerateStrs(tmp[i]);

		}

		return ret;

	}

	string GenerateStrs(string str)

	{

		string ret = "";

		for (int i = 0; i < str.size(); i++)

		{

			if (str[i] != '#')

			{

				ret += str[i];

			}

		}

		return ret;

	}

	void FileGroup(vector<string>& data, string str, int begin)

	{

		int linenum = 0;

		int rowlinumber = begin;

		int direction = 1;

		for (int i = 0; i < str.size(); i++)

		{

			if (direction == 1)

			{

				data[linenum][rowlinumber] = str[i];

				linenum += direction;

			}

			else

			{

				data[linenum][rowlinumber] = str[i];

				linenum += direction;

				rowlinumber++;

			}

			if (linenum == data.size() - 1)

			{

				direction = -1;

			}

		}

	}

	int GetColumn(int size, int rows)

	{

		int ret = 1;

		if (size <= rows)

		{

			ret = 1;

			return ret;

		}

		int groupsize = 2 * rows - 2; //一组的个数，一整列整列减去2

		int groupwidth = 1 + rows - 2; //本身一列，去掉头尾各占一列

		if (size <= groupsize)

		{

			ret = groupwidth - (groupsize - size);

			return ret;

		}

		ret = size / groupsize * groupwidth + GetColumn(size%groupsize, rows);

		return ret;

	}

};

class Solution {

public:

string convert(string s, int numRows) {

		if (numRows == 1)

		{

			return s;

		}

		string ret = "";

		vector<string> tmp(numRows);

		for (int i = 0; i < s.size(); i++) //以2*（numRows-1）+1为周期

		{

			if (i % (2*numRows-2 )<=(numRows-1) ) //向下

			{

				tmp[i % (2 * numRows -2)] +=s[i];

			}

			else //向上

			{

				tmp[2*numRows-2- i % (2 * numRows -2)] += s[i];

			}

		}

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

		{

			ret += tmp[i];

		}

		return ret;

	}

};

其他：

1.难得回来早一点，https://my.youdias.xin/tools/chooser.html 上随机决定做一道LeetCode，就按顺序做了这个，看到题目的第一反应就是模拟过程来处理，写code的过程中感觉到应该是有规律的，完成仿真过程后提交，战胜18.59%，实现数学方法，战胜68.61%，计算机思维是把双刃剑，如果想要提高效率，还是得用脑子。

2.用时最短的code

static const auto io_sync_off = []()

{

    // turn off sync

    std::ios::sync_with_stdio(false);

    // untie in/out streams

    std::cin.tie(nullptr);

    return nullptr;

}();

class Solution {

public:

    string convert(string s, int numRows) {

        if(numRows == 1) return s;

        int size = (numRows<<1) - 2;

        char res[s.size()+1];

        int index = 0;

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

            for(int j = i; j < s.size(); j += size){

                res[index++] = s[j];

                int tmp = j + size - (i<<1);

                //j是前一个黑色元素在原数组中的下标,i是画成之字形时的行数

                if(i > 0 && i < numRows-1 && tmp <s.size()){

                    res[index++] = s[tmp];

                }

            }

        }

        res[s.size()] = '\0';

        return res;

    }

};

巴特西

LeetCode_6

最新文章

热门文章