【刷題日記-字元串操作】

現在已将LeetCode刷題心得記錄github上，每一題都有我能夠想到的多種解法，歡迎star！github

  學習不易，看論文看的頭昏腦漲，就來刷兩題，神清氣爽，也順便做個記錄，友善以後查閱    

    No 6：ZigZag Conversion

    本題就是希望能夠對輸入的字元串在一個假想空間排列成鋸齒狀的形式，并且将新的形式逐行連接配接成目标字元串并輸出，輸入為原始字元串s，和鋸齒長度numRows；輸出修改後的字元串。

   本題隻要在紙上畫畫寫寫，就很容易找到原始下标 i 和其對應鋸齒行數pos的關系。

class Solution {
public:
    string convert(string s, int numRows) {
       	vector<vector<char>> t;
		vector<char> 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++近年用的不多，懶得查閱一些庫函數，是以實作的都是利用最基本的方式，感覺後續還是要惡補一下常用函數，會省下不少功夫。。。。。。這個方法是第一個寫的，但是跑出來141ms。。。打敗全國2.4%的使用者。。。。醉了。後來看了一下，主要展現在容器的構造以及最後字元的累加。由于c++中部落客還不清楚有沒有像java中stringBuffer這樣的操作用于高效修改字元串，是以做了一下小的修改。

class Solution {
public:
    string convert(string s, int numRows) {
       	vector<vector<char>> t;
		vector<char> 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;
    }
};
           

但是跑出來46ms。。隻打敗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;
    }
};
           

最後終于停留在39ms，打敗全國54%的使用者。。。總算是超越平均水準了。。。

準備按照題目内容進行專題分類，後續将不斷更新。。。