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

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

image.png

4 分 - 日期之间隔几天
5 分 - 验证二叉树
5 分 - 最接近的因数
6 分 - 形成三的最大倍数

关联内容:🏆 全新「周赛评分算法」最终方案

展开讨论
力扣 (LeetCode)发起于 2020-02-23
最近编辑于 2020-02-23

日期之间隔几天

思路

  1. 调库

答题

void parseDate(string &date, int& y, int& m, int& d)
{
	stringstream ss;
	while (date.find("-") != string::npos)
	{
		date = date.replace(date.find("-"), 1, " ");
	}
	ss << date;
	ss >> y >> m >> d;
}

tm setDate(int& y, int& m, int& d)
{
	tm ret;
	ret.tm_year = y - 1900;
	ret.tm_mon = m - 1;
	ret.tm_mday = d;
	ret.tm_hour = ret.tm_min = ret.tm_sec = 0;
	return ret;
}

int daysBetweenDates(string date1, string date2)
{
	int y, m, d;
	parseDate(date1, y, m, d);
	tm t1 = setDate(y, m, d);
	parseDate(date2, y, m, d);
	tm t2 = setDate(y, m, d);

	time_t tt1 = mktime(&t1);
	time_t tt2 = mktime(&t2);
	return abs(tt2 - tt1) / (24 * 60 * 60);
}

验证二叉树

思路

  1. 找出 root 节点
  2. bfs 验证

答题

bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) 
{
	vector<int> inDegree(n, 0);
	for (int i = 0; i < leftChild.size(); i++)
	{
		if (leftChild[i] != -1)
		{
			inDegree[leftChild[i]]++;
		}
		if (rightChild[i] != -1)
		{
			inDegree[rightChild[i]]++;
		}
	}
	int root = -1;
	for (int i = 0; i < inDegree.size(); i++)
	{
		if (inDegree[i] != 0) continue;
		if (root != -1) return false;
		root = i;
	}
	if (root == -1) return false;

	vector<int> vi(n, 0);
	queue<int> que;
	que.push(root);
	vi[root] = 1;

	while (!que.empty())
	{
		auto q = que.front();
		que.pop();

		if (leftChild[q] != -1)
		{
			if (vi[leftChild[q]] == 1) return false;
			que.push(leftChild[q]);
			vi[leftChild[q]] = 1;
		}
		if (rightChild[q] != -1)
		{
			if (vi[rightChild[q]] == 1) return false;
			que.push(rightChild[q]);
			vi[rightChild[q]] = 1;
		}
	}
	return all_of(vi.begin(), vi.end(), [](const int& a) { return a == 1; });
}

补充用例

Input: n = 3, leftChild = [1,0,-1], rightChild = [-1,-1,-1]
Output: false

Input: n = 3, leftChild = [-1,2,1], rightChild = [-1,-1,-1]
Output: false

最接近的因数

思路

  1. 开根号,然后递减遍历,找到答案
  2. 比较两个答案,返回

答题

vector<int> getClose(int num)
{
    for (int a = pow(num, 0.5) + 1; a >= 1; a--)
    {
        int b = num / a;
        if (a * b == num) return { a, b };
    }
    return {};
}

vector<int> closestDivisors(int num) 
{
    auto a = getClose(num + 1);
    auto b = getClose(num + 2);
    if (a.empty()) return b;
    if (b.empty()) return a;
    return abs(a[0] - a[1]) <= abs(b[0] - b[1]) ? a : b;
}

形成三的最大倍数

思路

  1. 各个位数相加的和,是三的倍数,那么这个数一定是三的倍数
  2. 如果和取模为 1 ,可以减去一个最小的取模为 1 的数字(1 4 7),或者两个取模为 2 的数字(2 5 8)
  3. 如果和取模为 2 ,与上面相反,减去一个最小的取模为 2 的数字,或者两个最小的取模为 1 的数字
  4. 减一个数字相当于减了一位,为了使数字最大,当然是先优先减一个数字,从小到大。如果不行,再减两个数字
  5. 使用一个 vector<int> cnt(10, 0) 或者 cnt[10] 来把各个数字个数记录,方便减数
  6. 减数之后就按照数字从大到小依次添加进去即可
  7. 注意全 0 的数字只返回一个 0

答题

bool deleteNum(vector<int>& cnt, int n)
{
	for (int i = n; i <= 9; i += 3)
	{
		if (cnt[i] != 0)
		{
			cnt[i]--;
			return true;
		}
	}
	return false;
}

string largestMultipleOfThree(vector<int>& digits) 
{
	vector<int> cnt(10, 0);
	int sum = 0;
	for (auto& d : digits)
	{
		sum += d;
		cnt[d]++;
	}

	if (cnt[0] == digits.size()) return "0";
	if (sum % 3 != 0)
	{
		int a = sum % 3;
		int b = 3 - a;
		if (!deleteNum(cnt, a))
		{
			deleteNum(cnt, b);
			deleteNum(cnt, b);
		}
	}

	string ans;
	for (int i = cnt.size() - 1; i < cnt.size(); i--)
	{
		while (cnt[i]-- != 0)
		{
			ans += to_string(i);
		}
	}
	return ans;
}

致谢

这次周赛真的有点蛋疼
T1 看着麻烦心态就有点崩
T2 感觉良好通过了,事后却发现是错的逻辑
T3 感觉不出是个 T3
T4 带着 bug 就通过了

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

我的leetcode

2
展开全部 19 讨论