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

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

image.png

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

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

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

第二题目测很多假算法都能AC, 应该加入以下两个测试用例:
3
[1,0,-1]
[-1,-1,-1]

3
[-1, 2, 1]
[-1, -1, -1]

这两个用例都应该返回false

另外,顺便提一下,标程是错的。如下图:
image.png

8

为什么我越来越菜了 OwQ

7

我就是个废物.....

5

日期之间隔几天

思路

  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

除了第二题没读懂,其他的还算简单~
昨晚和今天的,都偏数学~
第一题就是调库, (datetime-datetime).days
第三题:遍历到开平方,逐个比较, 已经有的跳过.
第四题:能被3整除的数,它的各个位数+起来肯定也能被3整除,
被3除的余数只有 1, 2.
排序,翻转下就好.

1

第二题的测试用例。
5
[1,3,-1,-1,-1]
[-1,2,4,-1,-1]
这个测试结果为什么期望结果是true呢。。
0
1 -1
3 2 -1 4
-1 -1 -1 -1

是我没看懂题是什么意思么。。

大佬们,求个第三题思路,想了想除了暴力法没啥思路。

<=O(2N)为什么也会超时?help help
class Solution:
def closestDivisors(self, num: int) -> List[int]:
def find_factors(number):
low = int(math.sqrt(number))
high = low
product = low * high
while low >= 0 and high <= num and product != number:
if product > number:
low -= 1
product = product-high
elif product < number:
high += 1
product = product + low
return [low, high]

    num1 = find_factors(num + 1)
    num2 = find_factors(num + 2)
    return num1 if abs(num1[0] - num1[1]) < abs(num2[0] - num2[1]) else num2

第四个题目「形成三的最大倍数」,我直接倒序排序,然后dfs,后面大的测试用例就超时了,求大佬指导怎么优化,或者有什么巧妙的思想解决这个题啊?

小学学的2200不算闰年我能说我忘了吗?