频道栏目
首页 > 考试 > 等级考试 > 其他 > 正文

笔试题43. LeetCode OJ (30)

2016-05-02 11:20:37      个评论    来源:admin-zou  
收藏   我要投稿
\

 

刷到这里的时候我感觉到了痛苦,我觉得这些题的难度在增加,就拿这个题来说吧,我折腾了一两天,最后还是借鉴了一下网友的思路才做出来的,困扰我的有以下几点。

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标签 试题
上一篇:LeetCode Gas Station
下一篇:hiho#1049 : 后序遍历( nyoj848 STBE)
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站