LeetCode 6_ZigZag Conversion

今日はもう一つ書きます.これはleetcodeの6番目の問題で、難易度はeasyで、問題は深いアルゴリズムを使っていませんが、細かいことを考えなければなりません.一度に正しいことをするのは難しいですか.私は修正して半日で検証に合格しました.
原題は以下の通りです.
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" .
タイトルは長いですが、英語のレベルがよければ、理解するのは難しくありません.いわゆる鋸歯変換です.入力した文字列を鋸歯の形に並べて、特定の順序で新しい文字列を読み出します.この問題の例を通して理解しやすいはずなので、あまり口を酸っぱくしません.
はっきり言って、この問題は法則を探す問題を考察して、あなたが鋸歯行列の中の各行の中のアルファベットの元の文字列の中の下のマークの関係を見つけるだけでいいです.たとえば,問題で挙げた例では,1行目のPは0番目の要素であり,Aは(0+4)番目,Hは(0+4+4)番目である.の2行目になるとAは1番目、Pは(1+2)番目、Lは(1+2+2)番目..
皆さんが辛抱強く、この法則は簡単にまとめることができます.nRowsが大きいとき、いくつかの行がスキップするたびに異なり、行数と関係があることに注意してください.これはよく観察してください.しかし、さまざまなレベルの読者に適応するために、私はここで法則を大まかにまとめました.
のこぎり行列:
(1)各行の開始要素の下付き文字は行数に等しい.
(2)最初の行と最後の行がスキップする距離は2*numRows-2(maxSpaceとする).に等しい.
(3)第r行がスキップするたびに異なる距離は,それぞれmaxSpace−2*rと2*rである(両者の加算はmaxSpaceであり,maxSpaceは周期的性質の数である).
もう一度言って、これらの法則は辛抱強く、簡単にまとめられます.しかし、ルールをコードに変換すると、開始位置や終了位置に問題があることがわかります.これらの細部では間違いやすいので、油断しないで、あまり言わないで、自分のコードを直接見てみましょう.

<span style="font-size:14px;"><span style="font-size:18px;">class Solution {
public:
    string convert(string s, int numRows) {
		int len=s.size();
		if(len<=numRows || numRows==1) return s;
        int maxSpace=2*numRows-2;
		string result;
		for(int row=0;row!=numRows;++row)
		{
			for(int j=row;j-2*row<len;j+=maxSpace)
			{
				if(row!=0 && row!=numRows-1 && j>maxSpace)
				{
					result.push_back(s[j-2*row]);
				}
				if(j<len)
				result.push_back(s[j]);
			}
		}
		return result;
    }
};</span></span>

このコードは初めて书かれたもので、具体的にはその言叶の意味は何も言わないで、中には多くの「パッチ」が见えて、プログラムの运行时间は20 msで、C++プログラムの中で比较的に良くて、しかし最も良いのとまだ差があります.最初はプログラムに書かれた判断が多すぎて時間がもったいないと思っていたので、コードを再整理してみましたが、次のようになりました.

<span style="font-size:14px;"><span style="font-size:18px;">class Solution {
public:
    string convert(string s, int numRows) {
		int len=s.size();
		if(len<=numRows || numRows==1) return s;
        int maxSpace=2*numRows-2;
		string result;
		for(int i=0;i<len;i+=maxSpace)
			result.push_back(s[i]);
		for(int row=1;row!=numRows-1;++row)
		{
			result.push_back(s[row]);
			for(int j=row+maxSpace-2*row;j<len;j=j+maxSpace-2*row)
			{
				result.push_back(s[j]);
				j+=2*row;
				if(j<len)
				result.push_back(s[j]);
			}
		}
		for(int i=numRows-1;i<len;i+=maxSpace)
			result.push_back(s[i]);
		return result;
    }
};</span></span>

整理したコードは少しきれいになりましたが、残念ながら実行時間は変わりません.まだ20 msです.私はVSの最適化能力を過小評価しているようで、上下の2つのコードの最適化結果は大同小異で、現在流行している言葉で言えば、最適化は何もありません.
問題はどこですか.大神さんはもう見たかもしれませんが、実はプログラムの肝心なところは最内層サイクルの4つの言葉で、プログラムの実行時間を決めるのはこの4つの言葉です(実行が一番多いからです)、この4つの言葉には何か問題がありますか?このようにまだ理解していない場合は、あなたが知らないか、考えていない可能性があります:push_back()操作の実行メカニズム.定義したstringオブジェクトは、下付きの額を直接使用できないことを知っています.まだ「位置」がないので、push_を使用します.back().しかし,このメカニズムは従来のシーケンステーブルコンテナと同様に空間連続性の問題であるという欠点がある.stingオブジェクトの空間はpush_にあるのでback()の過程で「動的割り当て」が行われ、空間が連続しなければならないことが要求されるため、空間が足りない場合の全体的な複製問題に関連し、また割り当て空間自体にも時間がかかるため、時間はこの場所で浪費される.それがわかったらやりやすいので、resultにreserve()を付けましょう.result定義の後にresultを付けましょう.reserve(len);空間割り当てを一度に完了させ、プログラムを実行すると、発見時間が16 msに短縮され、最高レベルに達しました!
また、プログラムにはまだエッジ状况の特殊な処理の応用があります.ここではあまり言いません.今日も大神のコードを贴り付けません.私たちはもう大神と同じレベルなので、ほほほ
自分で作るように勧めたほうがいいです.プログラムの細部は多いです.