第一题：AC 给一个字符串，求最长的无重复字符的子串的长度
思路：直接模拟，用set判断是否重复，用两个指针 l, r 记录当前子串的区间，每次更新答案即可
代码：
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("a.txt", "r", stdin);
#endif
int n;
string s;
while(getline(cin, s)) {
set<unsigned char> tb;
if(s.size() == 0) {
cout << 0 << endl;
continue;
}
int ans = 1;
int l = 0;
int r = 0;
int n = s.size();
while(r < n) {
if(l >= r || tb.find(s[r]) == tb.end()) {
tb.insert(s[r++]);
} else {
tb.erase(s[l]);
l++;
}
ans = max(ans, r - l);
}
cout << ans << endl;
}
return 0;
}
第二题：AC 给一个长度文n的整数数组，其中有一个元素出现了超过n次，求出该元素
思路：直接计数，用cnt记录次数，val记录出现cnt次的元素，遍历时判断相等就++cnt, 不相等就--，
--cnt后如果 = 0，就更新元素，最后直接输出val即可
代码：
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("b.txt", "r", stdin);
#endif
int n = 0;
int x;
string s;
while(getline(cin, s)) {
stringstream ss(s);
vector<int> a;
while (ss >> x) a.push_back(x);
int val = a[0];
int cnt = 1;
for(int i = 1; i < a.size(); ++i) {
if(a[i] == val) ++cnt;
else {
--cnt;
if(cnt == 0) {val = a[i]; cnt = 1;}
}
}
cout << val << endl;
}
return 0;
}
第三题：AC 给一个整数序列，求出该序列中满足 a + b + c = 0 的元组的序列，每个答案一行
思路：这个题当然可以直接采取暴力检索，如果长度为n，时间复杂度为O(N^3) ，判断如果元素超过1000个就会超时，
所以考虑降维，复杂度降到O(N^2)，因为有 a + b + c = 0, 变成 a + b = -c, 也就是，只需要枚举 （a+b） 和 -c 即可，
先从小到达排序原数组，然后从第一个>= 0 位置（记为：r ）的-c开始往右枚举，在-c的左边(区间为：[0, r-1] )查找 a + b = -c的元组，
每次枚举r时，检索[0, r-1] 最多需要r次，所以最后总的时间复杂度O(N * (N-1) / 2)，一次AC, 耗时0ms
代码：
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0);
using pii = pair<int,int>;
const int maxn = 10005;
int a[maxn];
int n;
vector<pii> getSum(int l, int r, int val) {
vector<pii> ans;
while(l < r) {
if(a[l] + a[r] > val) r--;
else if(a[l] + a[r] < val) l++;
else {
ans.push_back({a[l], a[r]});
while(l < r && a[l] == a[l+1]) l++;
while(l < r && a[r] == a[r-1]) r--;
l++;
r--;
}
}
return ans;
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("c.txt", "r", stdin);
#endif
string s;
while(getline(cin, s)) {
stringstream ss(s);
n = 0;
int x;
while(ss >> x) a[n++] = x;
sort(a, a+n);
set<vector<int>> ans;
int r = 0;
while(r < n && a[r] < 0) ++r;
for(; r < n; ++r) {
vector<pii> segs = getSum(0, r-1, -a[r]);
if(segs.size() == 0) continue;
for(auto& p : segs) ans.insert({p.first, p.second, a[r]});
}
for(auto& v : ans) {
cout << v[0] << " " << v[1] << " " << v[2] << endl;
}
}
return 0;
} 
全部评论
(3) 回帖