頻道欄目
首頁 > 資訊 > 其他 > 正文

筆試題43. LeetCode OJ (30)

16-05-02        來源:[db:作者]  
收藏   我要投稿

 

刷到這里的時候我感覺到了痛苦,我覺得這些題的難度在增加,就拿這個題來說吧,我折騰了一兩天,最后還是借鑒了一下網友的思路才做出來的,困擾我的有以下幾點。

1.這英文單詞雖懂,可是題目卻還是沒有理解,問了很多人他們也不知道,其中還問了一個過了專八的人,她的回答是專業性太強,不理解,很多網友說的也不清楚,很容易誤導人的

2.所學的知識有些不夠,或者說有些東西用的不熟練,比如這道題的map,因為使用不熟練,所以寫的代碼太繁瑣

所以我在這里再次將這個題做一下說明吧,理解了題目的意思以后,其實就容易許多,所以我先把題目意思好好的所以下吧。

這道題的意思是給你一個字符串 S 和一串單詞 words,在S里面找出相應的下標,下標滿足 :

(1) 所有單詞都在S中出現,且出現的次數和words中的次數一致

(2). 不能重復出現,這種情況的意思是,相同單詞不能出現多了,出現多次不符合要求。

(3).另外一點是我將上面的例子改成:

string s = "foothebarbarfooman";

vector words = { "foo", "bar" };

像這種情況下,若按題目表面意思來說,應該也是返回 [0,9] ,但是實際上返回的是9,因為words中的單詞中間出現了干擾部分,比如前面的 foo和bar之間有the的干擾,而后面的bar和foo是連續的,所以符合要求。 請看原文中的最后一句話 “and without any intervening characters”這句話意思是沒有任何中間的元素,所以最終意思是:words中出現的單詞順序可以以任何次序出現在S中,但是必須連續,而且各個單詞只出現一次至此,相信大家理解題目意思了吧。

代碼如下:

 

class Solution 
{ 
public: 	
	vector findSubstring(string s, vector& words) 
	{ 
		vector ret;
		ret.clear();
		map Map;
		map temp;
		Map.clear();
		temp.clear();
		int slen = s.size();
		int wlen = words.size();
		if (slen == 0 || wlen == 0)
		{	return ret;	}
		
		int perlen = words[0].size();
		if ( wlen * perlen > slen)
		{	return ret;	}

		for (int i = 0; i < wlen; ++i)
		{
			Map[words[i]]++;
		}

		for (int i = 0; i + perlen*wlen-1 < slen; ++i)
		{
			int j = i;
			temp.clear();
			while (j <= i + wlen*perlen - 1)
			{
				temp[s.substr(j, perlen)]++;
				if (Map[s.substr(j, perlen)] < temp[s.substr(j, perlen)])
				{//
					break;
				}
				else
				{
					j += perlen;
				}
				if (j>i + wlen*perlen - 1)
				{
					ret.push_back(i);
				}
			}
		}
		return ret;
	} 
};
測試結果如下:

 

相關TAG標簽
上一篇:臺積電:絕大多數7nm客戶都會轉向6nm_IT新聞_博客園
下一篇:最后一頁
相關文章
圖文推薦

關于我們 | 聯系我們 | 廣告服務 | 投資合作 | 版權申明 | 在線幫助 | 網站地圖 | 作品發布 | Vip技術培訓 | 舉報中心

版權所有: 紅黑聯盟--致力于做實用的IT技術學習網站

美女MM131爽爽爽毛片