LeetCodeシリーズの文字列操作(一)ZigZag出力は、最大文字列の長さを繰り返さないことを探します.

http://blog.csdn.net/michael_コーニング.nju/articale/detail/44831243
ZigZag Coversion
 
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:  "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) ショルダーリターン  "PAHNAPLSIIGYIR".
分析するこの問題は正常なstringシーケンスをZigZagという形で表しています.zigzagzingは英語ではジグザグという意味です.つまりジグザグの形で文字を並べ直します.この問題はこのジグザグの形がはっきりしていれば易しい問題ですが、知らないと損をするかもしれません.
この問題は大体三回提出しましたが、最初はこののこぎりの形がよく分かりませんでした.二つの長い列の中に一つの元素しかないと思っています.上のテーマのような形をしていますが、問題はこの中間の元素は何番目の行にありますか?最初から黙認していたのは二行目で、一度提出しました.エラーです.そして、テストケースの期待値によって、この元素は最後から二番目の行にあると思います.もう一度提出しました.結果はやはり間違っています.最後に仕方なくネットでこの形を調べてみましたが、最後に二つの長い列の間に対角線があり、正方形が形成されていることを告白しました.下図のように:

だから次の法則を発見しやすいです.
nRowsに対して1より大きいと.
1)最初の行と最後の行の要素に対応する元の文字列の位置は前の列の要素+(nRows-1)*2である.
2)中間の行(ライン数が2より大きい場合)について、現在の列が偶数列(0から開始)である場合、奇数列の位置＋(nRows-1-i)＊2である.
1列目のIndex=1+(4-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 Charcters
 
Given a string、find the length of the longest substring without repeating characters.For example、the longest substring without repeting letters for“abcabbbbbbbbbbbbbb”is“abc”、wthelength the 3.Follis.
この問題は最初に作った時は考えがはっきりしています.二つの指針はそれぞれ後ろに回って、それぞれの文字とセットの中の要素を比較します.出現していないなら、セットに入れて長さを1に加えます.この方法は簡単ですが、時空の複雑さは比較的に高くて、その中の時間は複雑ですo(n^2)で、空間の複雑さもo(n)があります.最後に提出する時はやはり時間の制限を超えます.
インターネットで流行っている時間を空間に変える方法を以下に示します.
1つの配列でhash shucharcは、最近出現する可能性のあるすべての文字の位置を記憶しています.2つのindexは、エルゴードを制御するために使用され、そのうちの1つはすべての文字を巡回するために使用され、curは使用されます.
現在テストされていない、有効なサブストリングの開始位置を保存します.
現在の文字がこのcurの後に現れなかったら、disを計算してこの最大値を更新します.
もし現れたら、この2つの同じ文字の間の距離を計算します.最大距離値を更新するかどうかを確認してください.同時に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;
        }