字节跳动25号笔试100%，100%，30%，70%代码
第一题：并查集 100%
//
// Created by Chaopeng Zhang on 2019-08-25.
//
#include <iostream>
using namespace std;
#include <vector>
class Solution {
public:
int findDouYouNum(vector <vector<int>> &M) {
if (!M.size())
return 0;
int n = M[0].size();
count = n;
id.resize(n);
sz.resize(n);
for (int i = 0; i < n; ++i) {
id[i] = i;
sz[i] = 1;
}
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (M[i][j] >= 3) {
Union(i, j);
}
}
}
return count;
}
int Find(int i) {
while (i != id[i])
i = id[i];
return i;
}
void Union(int i, int j) {
int p = Find(i);
int q = Find(j);
if (p == q)
return;
if (sz[p] < sz[q]) {
id[p] = q;
sz[q] += sz[p];
} else {
id[q] = p;
sz[p] += sz[q];
}
count--;
}
vector<int> id;
vector<int> sz;
int count;
};
int main() {
vector<vector<int>> input;
int n;
cin>>n;
for (int i = 0; i < n; ++i) {
vector<int> v;
for (int j = 0; j < n; ++j) {
int num;
cin>>num;
v.push_back(num);
}
input.push_back(v);
}
Solution s;
cout<<s.findDouYouNum(input);
} 第二题 100%
//
// Created by Chaopeng Zhang on 2019-08-25.
//
#include <iostream>
using namespace std;
const int mod = 1000000007;
long long d[1001] = {1};
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i += 2) {
for (int j = 0; j <= i - 2; j += 2) {
d[i] = (d[i] + d[j] * d[i - 2 - j] % mod) % mod;
}
}
cout << d[n] << endl;
return 0;
}
第三题 30%，后来优化了没时间提交
//
// Created by Chaopeng Zhang on 2019-08-25.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> solve(vector<vector<int>> &mat, int dir) {
if (dir == 1) {
Up(mat);
} else if (dir == 2) {
Down(mat);
} else if (dir == 3) {
Left(mat);
} else {
Right(mat);
}
return mat;
}
vector<int> merge(vector<int> line) {
vector<int> ans;
vector<int> postive;
for (int i = 0; i < line.size(); ++i) {
if (line[i] > 0)
postive.push_back(line[i]);
}
postive.push_back(0);
for (int j = 1; j < postive.size(); ++j) {
if (postive[j] == postive[j - 1]) {
ans.push_back(2 * postive[j - 1]);
j++;
} else {
ans.push_back(postive[j - 1]);
}
}
for (int k = ans.size(); k < 4; ++k) {
ans.push_back(0);
}
return ans;
}
void Up(vector<vector<int>> &mat) {
for (int i = 0; i < 4; ++i) {
moveUp(mat, i);
}
}
void Down(vector<vector<int>> &mat) {
for (int i = 0; i < 4; ++i) {
moveDown(mat, i);
}
}
void Left(vector<vector<int>> &mat) {
for (int i = 0; i < 4; ++i) {
moveLeft(mat, i);
}
}
void Right(vector<vector<int>> &mat) {
for (int i = 0; i < 4; ++i) {
moveRight(mat, i);
}
}
void moveUp(vector<vector<int>> &mat, int col) {
vector<int> v;
for (int i = 0; i < 4; ++i) {
v.push_back(mat[i][col]);
}
vector<int> ans = merge(v);
for (int j = 0; j < 4; ++j) {
mat[j][col] = ans[j];
}
}
void moveDown(vector<vector<int>> &mat, int col) {
vector<int> v;
for (int i = 3; i >= 0; --i) {
v.push_back(mat[i][col]);
}
vector<int> ans = merge(v);
for (int i = 3; i >= 0; --i) {
mat[i][col] = ans[3-i];
}
}
void moveLeft(vector<vector<int>> &mat, int row) {
vector<int> v;
for (int i = 0; i < 4; ++i) {
v.push_back(mat[row][i]);
}
vector<int> ans = merge(v);
for (int j = 0; j < 4; ++j) {
mat[row][j] = ans[j];
}
}
void moveRight(vector<vector<int>> &mat, int row) {
vector<int> v;
for (int i = 3; i >= 0; --i) {
v.push_back(mat[row][i]);
}
vector<int> ans = merge(v);
for (int i = 3; i >= 0; --i) {
mat[row][i] = ans[3-i];
}
}
};
int main() {
int dir;
cin >> dir;
vector<vector<int>> input;
for (int i = 0; i < 4; ++i) {
vector<int> v;
for (int j = 0; j < 4; ++j) {
int a;
cin >> a;
v.push_back(a);
}
input.push_back(v);
}
vector<vector<int>> ans;
Solution s;
ans = s.solve(input, dir);
for (auto i:ans) {
for (auto j:i) {
cout << j << " ";
}
cout << endl;
}
} 第四题，还是并查集，70%，UnionFind不知道咋改成LogN的复杂度
//
// Created by Chaopeng Zhang on 2019-08-25.
//
#include <iostream>
using namespace std;
#include <math.h>
#include <unordered_map>
#include <vector>
class Solution {
public:
int gcd(int i, int j) {
int min_num = min(i, j);
int max_num = max(i, j);
int temp;
while (min_num > 0) {
temp = max_num % min_num;
max_num = min_num;
min_num = temp;
}
return max_num;
}
int findCandy(vector<int> &M) {
if (!M.size())
return 0;
int n = M.size();
count = n;
id.resize(n);
sz.resize(n);
for (int i = 0; i < n; ++i) {
id[i] = i;
sz[i] = 1;
}
//n^2
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (gcd(M[i], M[j]) > 1) {
Union(i, j);
}
}
}
unordered_map<int, int> cnt;
int ans = INT32_MIN;
int id_num;
for (int k = 0; k < n; ++k) {
id_num = Find(k);
cnt[id_num] += 1;
ans = max(ans, cnt[id_num]);
}
return ans;
}
int Find(int i) {
while (i != id[i])
i = id[i];
return i;
}
void Union(int i, int j) {
int p = Find(i);
int q = Find(j);
if (p == q)
return;
if (sz[p] < sz[q]) {
id[p] = q;
sz[q] += sz[p];
} else {
id[q] = p;
sz[p] += sz[q];
}
count--;
}
vector<int> id;
vector<int> sz;
int count;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solution s;
int n;
cin>>n;
vector<int> v;
while(n)
{
int a;
cin>>a;
v.push_back(a);
n--;
}
cout<<s.findCandy(v);
} 
联想公司福利 666人发布
