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

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".

分析; 此题是将一个正常的string序列用ZigZag的形式进行表示，zigzag在英文里是曲折的意思，即以锯齿状的形式将字符重新排列。此题如果很清楚这个ZigZag的形状的话是道容易的题，但是如果不知道可能就会吃亏。

这道题我大概提交了三次，因为刚开始不是很清楚这个锯齿到底是怎么一个形状，我以为没两个长列中间就只有一个元素，就如同上面的题目给出的那种形式，那么现在问题是，这个中间的一个元素位于第几行呢？ 我刚开始就默认是在第二行，提交了一次，错误。然后我根据测试用例的期望值认为这个元素在倒数第二行，又提交了一次，结果还是错误。最后无奈我到网上搜索了一下该形状到底如何，最后才表白每两个长列之间是一个对角线，构成一个正方形。如下图所示：

所以很容易发现下面的规律：

对于nRows大于1的话。

1) 对于第一行和倒数第一行，后一列的元素对应的原字符串中的位置是前一列的元素+(nRows-1)*2；

2) 对于中间的行(当行数大于2的时候)，如果当前列是偶数列(从0开始)，那么那是奇数列的位置+(nRows-1-i)*2.如对于第二行，

第1列的Index=1+(4-1-1)*2 = 5. 而偶数列是前一列的index + 2*当前行。

上面的规律稍加推导即可得出。

下面是代码：

string convert(string s, int nRows)
{
	string temp(s);
	if (nRows < 2)
		return temp;
	int i, step;
	int j = 0;
	int count;
	for (int row = 0; row < nRows; row++)
	{
		if (row == 0 || row == nRows - 1)
		{
			step = (nRows - 1) * 2;
			for (i = row; i < s.size(); i = i + step)
			{
				temp[j++] = s[i];
			}
		}
		else  // 对于从正数第二行到倒数第二行
		{
			count = 0;
			for (i = row; i < s.size(); i = i + step)
			{
				temp[j++] = s[i];
				if (++count & 0x01)
					step = row*2;   //偶数列
				else
					step = (nRows - 1 - row) * 2;  //奇数列
			}
		}
	}
	return temp;
}

Longest Substring Without Repeating Characters

这道题刚开始做的时候思路还是很清晰的，两个指针分别向后，然后将每一个字符和set中的元素进行比较，如果是没有出现过那么放入set并将长度加1.这种方法简单是比较简单，但是时空复杂度都比较高，其中时间复杂是o(n^2)，空间复杂度也有o(n)，最后提交的时候果然超出时间限制。

下面给出一种网上比较流行的用时间换空间的做法：

用一个数组hash_charc存储所有可能出现的字符在最近一次出现的位置。两个index用来控制遍历，其中一个i用来遍历所有的字符，cur用来

保存当前未测试的，有效的子串开始的位置。

如果当前的字符在这个cur之后没有出现过，计算一下dis看是否要更新这个最大值。

如果出现过了，那么，计算这两个相同的字符之间的距离看是否要更新最大距离值。同时更新cur为之前出现的字符的位置。

下面是用c++实现的程序。

    int lengthOfLongestSubstring(string s) {
    	int hash_char[256];//保存字符上一次出现的位置
    	memset(hash_char, -1, sizeof(hash_char));
    
    	int curr = -1, max = 0;  
    	for (int i = 0; i < s.size(); i++)
    	{
    		if (hash_char[s[i]] > curr)//如果当前字符在curr之后出现过，更新curr为上一次出现的位置
    			curr = hash_char[s[i]];
    		max = max > i - curr ? max : i - curr;  //注意这个步骤不管上面的if是否满足都会做。 
    		hash_char[s[i]] = i;
    	}
    	return max;
        }

LeetCode系列字符串操作(一)ZigZag输出，寻找最大不重复字串长度。

原文：http://blog.csdn.net/michael_kong_nju/article/details/44831243