讨论/题目交流/🏆 第 154 场力扣中秋周赛/
🏆 第 154 场力扣中秋周赛

力扣的扣友们中秋快乐🥮,欢迎前来参加本场周赛,小伙伴们可以在这里交流分享参赛心得以及体验。

image.png

展开讨论
力扣 (LeetCode)发起于 2019-09-15
最近编辑于 2019-09-15
共 10 个讨论

第一次在这里传视频,因为文件大小限制,不是特别清晰。高清版可以访问 YouTube
https://www.youtube.com/watch?v=j9Qmkdr9nz4

12

我真菜、、、第四题看都没来得及看

/*
5189. “气球” 的最大数量
*/
int maxNumberOfBalloons(string text) {
    int count[5];
    for (int i = 0; i < 5; i++) {
	    count[i] = 0;
    }
	for (char i : text) {
		switch (i) {
		case 'a':
			count[0]++;
			break;
		case 'b':
			count[1]++;
			break;
		case 'l':
			count[2]++;
			break;
		case 'o':
			count[3]++;
			break;
		case 'n':
			count[4]++;
			break;
		default:
			break;
		}
	}
	count[2] /= 2;
	count[3] /= 2;
	int res = INT_MAX;
	for (int i = 0; i < 5; i++) {
		res = min(res, count[i]);
	}
	return res;
}
/*
5190. 反转每对括号间的子串
*/
string reverseParentheses(string s) {
	stack<char> myStack;
	for (char i : s) {
		if (i == ')') {
			string temp = "";
			while (myStack.top() != '(') {
				temp = temp + myStack.top();
				myStack.pop();
			}
			myStack.pop();
			for (char j : temp) {
				myStack.push(j);
			}
		}
		else {
			myStack.push(i);
		}
	}
	string res = "";
	while (!myStack.empty()) {
		res = res + myStack.top();
		myStack.pop();
	}
	reverse(res.begin(), res.end());
	return res;
}
/*
5191. K 次串联后最大子数组之和
*/
int kConcatenationMaxSum(vector<int>& arr, int k) {
	int len = arr.size();
	int sum = 0;
	int sum2 = 0;
	int res = INT_MIN;
	for (int i = 0; i < len * 2; i++) {
		if (i < len)sum += arr[i];
		sum2 += arr[i % len];
		res = max(res, sum2);
		if (sum2 < 1) {
			sum2 = 0;
			continue;
		}
	}
	if (sum > 0) {			
		for (int i = 2; i < k; i++) {
			res += sum;
			res %= 1000000007;
		}
	}
	return res < 0 ? 0 : res;
}
3

第四题这是我写的也能过,我看都用tarjan算法,我这个算法对吗,是不是数据太弱才过的?
class Solution {
public:
vector<int> graph[100001];
int used[100001]={0};
unordered_set<int> ss;
unordered_set<int> cur;
int indegree[100001]={0};

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    for(auto c:connections)
    {
        graph[c[0]].push_back(c[1]);
        graph[c[1]].push_back(c[0]);
        indegree[c[0]]++;
        indegree[c[1]]++;
    }
    int i;
    for(i=0;i<n;++i)if(indegree[i]==1)cur.insert(i);
    vector<vector<int>> res;
    while(!cur.empty())
    {
        ss.clear();
        for(auto it=cur.begin();it!=cur.end();++it)
        {
            int t=*it;
            used[t]=1;
            for(auto adj:graph[t])if(!used[adj])
            {
                res.push_back({t,adj});
                indegree[adj]--;
                if(indegree[adj]==1)ss.insert(adj);
            }
        }
        cur=ss;
    }
    return res;
}

};

1

这场周赛第四题,用拓扑排序做法是错的,因为数据量不够充分导致错误代码也能通过,为何不刷新一下排名?印象中国际版竞赛过程中只提供部分数据,然后比赛结束后几分钟会用所有数据重新跑一下代码,同时重新计算排名,大家也能在规定时间内review各自代码并提供数据hack代码,这种特性为何不继承?

1

法克,第三题明明做出来了,漏了一个取模,我还纳闷为啥这个结果。看题不仔细从初中到现在从未改变:D

来分享一下第四题做法

哦,对不起,我第四题贴得模板,告退!(手动狗头

分享我写的周赛题解,「第 154 场周赛」题解

对python不友好,TLE经常换成C++写就过了

4

题目四 用java的 估计全超时了。
请问有用java过第四题的吗?

2

好久不玩,第四题求割边模板题都不会了,,,

2