讨论/题目交流/🏆 第 168 场力扣周赛/
🏆 第 168 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 统计位数为偶数的数字
4 分 - 划分数组为连续数字的集合
6 分 - 子串的最大出现次数
7 分 - 你能从盒子里获得的最大糖果数

展开讨论

题解

统计位数为偶数的数字

转成字符串算size就好了。

int findNumbers(vector<int>& nums) 
{
	int ans = 0;
	for (auto n : nums)
	{
		string str = to_string(n);
		ans += ((str.size() % 2) == 0);
	}
	return ans;
}

划分数组为连续数字的集合

  1. 把数字全都丢到map里,统计数量。
  2. 遍历map。
  3. 取map中最靠前,计数不为0的数字作为开始。
  4. 那么这个数字后面连续k个数字必须都有。
  5. 对后续数字的记录-1。
  6. 如果map里的记录没有,或者计数已经为0了,就可以return false了。
bool isPossibleDivide(vector<int>& nums, int k) 
{
	map<int, int> cnts;
	for (auto n : nums) cnts[n]++;

	for (auto it = cnts.begin(); it != cnts.end(); it++)
	{
		while (it->second != 0)
		{
			int _first = it->first;
			it->second--;
			for (int i = 1; i < k; i++)
			{
				int t = _first + i;
				if (cnts.count(t) == 0) return false;
				if (cnts[t]-- == 0) return false;
			}
		}
	}
	return true;
}

子串的最大出现次数

思路不混乱,但写法边界控制有问题,调整了好几次逻辑才对。

  1. 使用vector<int> chars(26, 0);记录字母使用情况。
  2. 配合上面,使用int curLetters = 0;记录不同字母的个数。
  3. 使用string curStr = "";记录minSize - 1长度的字符串。
  4. 遍历时,更新curStr,以及其字母使用情况。
  5. 然后复制出临时变量,对从minSize到maxSize的字符串判断。(后来发现并不需要考虑maxSize())
  6. 符合条件的加入到unordered_map<string, int> cnts;统计个数。
  7. 使用int ans = 0;记录最大值。
int maxFreq(string s, int maxLetters, int minSize, int maxSize) 
{
	int ans = 0;
	unordered_map<string, int> cnts;
	vector<int> chars(26, 0);
	int curLetters = 0;
	string curStr = "";

	for (size_t i = 0; i < s.size(); i++)
	{
		curStr += s[i];
		curLetters += (chars[s[i] - 'a']++ == 0);
		if (curStr.size() < minSize) continue;

		if (curLetters <= maxLetters)
		{
			cnts[curStr]++;
			ans = max(ans, cnts[curStr]);
		}

		curLetters -= (--chars[curStr[0] - 'a'] == 0);
		curStr.erase(curStr.begin());
	}

	return ans;
}

你能从盒子里获得的最大糖果数

  1. 按照题意模拟即可
  2. 使用vector<int> haveStatus(status.size(), 0);表示已经拿到手的盒子。
  3. 使用vector<int> keyStatus(status.size(), 0);表示已经取得的钥匙。
  4. 然后就从拿到手的盒子遍历,判断是否打开的,或者有钥匙。
    41. 如果能打开,执行打开操作。
    42. 拿糖果
    43. 拿盒子
    44. 拿钥匙
  5. 一直到没有盒子可以打开为止。
vector<int> getHaveBoxes(vector<int>& haveStatus)
{
	vector<int> ret;
	for (auto i = 0; i < haveStatus.size(); i++)
	{
		if (haveStatus[i] == 1)
		{
			ret.push_back(i);
		}
	}
	return ret;
}

int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) 
{
	vector<int> haveStatus(status.size(), 0);
	for (auto n : initialBoxes) haveStatus[n] = 1;
	vector<int> keyStatus(status.size(), 0);

	int ans = 0;

	bool flag = true;
	while (flag)
	{
		flag = false;

		auto have = getHaveBoxes(haveStatus);
		if (have.empty()) break;

		for (auto i : have)
		{
			if (status[i] == 1 || keyStatus[i] == 1)
			{
				flag = true;
				haveStatus[i] = 2;

				ans += candies[i];
				for (auto k : keys[i])
				{
					keyStatus[k] = 1;
				}
				for (auto c : containedBoxes[i])
				{
					haveStatus[c] = 1;
				}
			}
		}
	}
	return ans;
}

个人总结

被第三题折磨死了,错了好几次。
边界问题搞不清楚,还是经验太少。

第四题意外的简单,没先做第四题遗憾了。

又是一周只提交两道题,说好的保三争四,这几周表现都有点一言难尽。

再接再厉。
大家一起加油。

2
展开全部 16 讨论