【ブラシ日記-文字列操作】

今すでにLeetCodeブラシの問題の心得をgithubの上で記録して、すべての問題はすべて私が考えることができる多種の解法があって、starを歓迎します!github
 
 
勉强が难しくて、论文を见て头がぼうっとして、2つの问题をこすりに来て、気持ちがさっぱりして、ついでに记录をして、后で调べやすいです
    No 6:ZigZag Conversion
この問題は、入力された文字列を仮想空間で鋸歯状に並べ、新しい形式を行ごとにターゲット文字列に接続して出力し、元の文字列sと鋸歯長numRowsとして入力することです.変更した文字列を出力します.
本題は紙に絵を描いて書くだけで、元の下付きiとその対応する鋸歯行数posの関係を簡単に見つけることができます.
 
    

class Solution {
public:
    string convert(string s, int numRows) {
       	vector> t;
		vector tp;
		while (!tp.empty()) tp.pop_back();

		for (int i = 0; i < numRows; i++)
		{
			t.push_back(tp);
		}

		if (numRows == 1)
		{
			for (int i = 0; i < s.size(); i++)
				t[0].push_back(s[i]);
		}
		else {
			for (int i = 0; i < s.size(); i++)
			{
				int cycle = 2 * numRows - 2;
				int res = i%cycle;
				if (res < numRows)
					t[res].push_back(s[i]);
				else
					t[cycle - res].push_back(s[i]);
			}
		}
		string ans;
		for (int i = 0; i < t.size(); i++)
		{
			for (int j = 0; j < t[i].size(); j++)
			{
				ans += t[i][j];
				cout << t[i][j];
			}
			cout << endl;
		}
		return ans;
    }
};

c++は近年あまり使われていないので、ライブラリ関数を調べるのがおっくうなので、最も基本的な方法を利用して実現しています.この方法は最初に書いたのですが、141 ms走って出てきました..全国のユーザーの2.4%を打ち負かす...酔った.後で見てみると、主に容器の構造と最後の文字の累積に現れています.c++のブロガーはjavaのstringBufferのような操作が文字列を効率的に修正するのに使われているかどうかまだ分からないので、小さな修正をしました.

class Solution {
public:
    string convert(string s, int numRows) {
       	vector> t;
		vector tp;
		while (!tp.empty()) tp.pop_back();

		for (int i = 0; i < numRows; i++)
		{
			t.push_back(tp);
		}

		if (numRows == 1)
		{
			for (int i = 0; i < s.size(); i++)
				t[0].push_back(s[i]);
		}
		else {
			for (int i = 0; i < s.size(); i++)
			{
				int cycle = 2 * numRows - 2;
				int res = i%cycle;
				if (res < numRows)
					t[res].push_back(s[i]);
				else
					t[cycle - res].push_back(s[i]);
			}
		}
		string ans=s;
		int p = 0;
		for (int i = 0; i < t.size(); i++)
		{
			for (int j = 0; j < t[i].size(); j++)
			{
				ans[p++]= t[i][j];
			}
		}
		return ans;
    }
};

でも46 ms出てきました.の24%のユーザーのみを打ち負かす...そして空間を利用して時間を変える方法を考えて、すべて配列します

class Solution {
public:
    string convert(string s, int numRows) {
       	char t[1000][1000];
		int len[1000] = { 0 };
		if (numRows == 1)
		{
			for (int i = 0; i < s.size(); i++)
				t[0][len[0]++]=s[i];
		}
		else {
			for (int i = 0; i < s.size(); i++)
			{
				int cycle = 2 * numRows - 2;
				int res = i%cycle;
				if (res < numRows)
					t[res][len[res]++]=s[i];
				else
					t[cycle - res][len[cycle-res]++]=s[i];
			}
		}
		string ans = s;
		int p = 0;
		for (int i = 0; i < 1000&&len[i]!=0; i++)
		{
			for (int j = 0; j < len[i]; j++)
			{
				ans[p++] = t[i][j];
			}
		}
		return ans;
    }
};

最後についに39 msにとどまり、全国の54%のユーザーを負かした.のなんとか平均を超えた...
 
テーマの内容によってテーマを分類するつもりで、後続は絶えず更新します.の