笔试编程题
1:相邻邻居的数量
两个点在对角线上就是相邻的，看到这个题目想了两分钟，决定用最暴利的解法试一下，用类似于八皇后的方法表示对角线：
对角线的直线表示是y = x + bi 或者 y = -x + bi; 变换一下是y - x = bi; y + x = bi;
因此判断两个点在不在对角线，只需要判断两者的y - x; y + x是不是相等的；
笔试的时候暴力做的，过了73，n平方复杂度了，后面自己想了下用一个map存下来每个点的y + x和y - x就可以额O(n)做了；
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 1;
int a[N][2];
int n, res = 0;
int main()
{
cin >> n;
for(int i = 0; i < n ;i++) cin >> a[i][0] >> a[i][1];
/*
//暴力
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(a[i][0] + a[i][1] == a[j][0] + a[j][1] || a[i][1] - a[i][0] == a[j][1] - a[j][0])
res++;
*/
//用map优化
unordered_map<int, int> dict;
for(int i = 0; i < n; i++)
{
dict[a[i][1] + a[i][0]]++;
dict[a[i][1] - a[i][0]]++;
}
for(unordered_map<int, int>::iterator it = dict.begin(); it != dict.end(); it++)
if(it->second > 1) res += it->second;
cout << res << endl;
return 0;
}
2.分个字符串01的比例相等
笔试的时候用暴力的方法做的，做完后看到网上gcd的方法感觉更妙
后面参照gcd方法实现的：
#include <iostream>
#include <unordered_map>
using namespace std;
int n;
string s;
typedef pair<int, int> PII;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
cin >> n >> s;
int zeros = 0, ones = 0;
PII p;
unordered_map<PII, int> dict;
for(int i = 0; i < n; i++)
{
if(s[i] == '0') zeros++;
else ones++;
if(zeros == 0)
{
p = make_pair(1, 0);
dict[p] += 1;
}
else if(ones == 0)
{
p = make_pair(0, 1);
dict[p] += 1;
}
else
{
int gcd_ = gcd(zeros, ones);
p = make_pair(zeros / gcd_, ones / gcd_);
dict[p] += 1;
}
cout << dict[p] << " ";
}
puts("");
return 0;
}
自己笔试的时候做的：
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int n;
string s;
int splitString(string s, int len)
{
if(len == 1) return 1;
int cnt = 1;
vector<PII> vec(len, make_pair(0, 0));
if(s[0] == '0') vec[0].first++;
else vec[0].second++;
for(int i = 1; i < len; i++)
{
if(s[i] == '0')
{
vec[i].first = vec[i - 1].first + 1;
vec[i].second = vec[i - 1].second;
}
else{
vec[i].first = vec[i - 1].first;
vec[i].second = vec[i - 1].second + 1;
}
}
//for(int i = 0; i < len; i++) cout << vec[i].first << ": " << vec[i].second << endl;
for(int i = 0; i < len; i++)
{
int n1 = vec[i].first * (vec[len - 1].second - vec[i].second);
int n2 = vec[i].second * (vec[len - 1].first - vec[i].first);
if(n1 != n2) continue;
else
{
for(int j = i; j < len - 1; j = j + i + 1)
{
int tmp1 = vec[j].first * (vec[len - 1].second - vec[j].second);
int tmp2 = vec[j].second * (vec[len - 1].first - vec[j].first);
if(tmp1 != tmp2) break;
else cnt++;
}
break;
}
}
return cnt;
}
int main()
{
cin >> n >> s;
//string s = "010100001";
for(int i = 0; i < n; i++)
{
string tmp = s.substr(0, i + 1);
cout << splitString(tmp, i + 1) << " ";
}
puts("");
return 0;
}
全部评论
(2) 回帖