站住，Offer
2019-08-25 21:55 腾讯_Ailab_算法工程师
关注
第一题，并查集 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%， 合并那里是N^2的，不知道咋优化成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);
}
查看原帖
点赞 4
相关推荐
10-29 12:14
武汉大学 运营 
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 2025年终总结 #
171085次浏览 2884人参与
# 找工作，行业重要还是岗位重要？ #
85174次浏览 1685人参与
# 职场上哪些行为很加分？ #
306557次浏览 3448人参与
# 大家每天通勤多久？ #
69493次浏览 440人参与
# 你面试体验感最差/最好的公司 #
16569次浏览 268人参与
# 实习的内耗时刻 #
210894次浏览 1537人参与
# 一人说一个提前实习的好处 #
9953次浏览 197人参与
# 今年你最想重开的一场面试是？ #
3746次浏览 66人参与
# 互联网行业现在还值得去吗 #
46848次浏览 351人参与
# 秋招落幕，你是He or Be #
10645次浏览 217人参与
# 面试吐槽bot #
164946次浏览 814人参与
# 实习没事做是福还是祸？ #
16131次浏览 245人参与
# 重来一次，你会对开始求职的自己说 #
5754次浏览 143人参与
# 反问环节如何提问 #
126335次浏览 2663人参与
# 礼物开箱Plog #
619次浏览 21人参与
# 团建是“福利”还是是 “渡劫” #
6867次浏览 146人参与
# 工作中听到最受打击的一句话 #
6151次浏览 108人参与
# 我的第一份实习怎么找的 #
208474次浏览 1827人参与
# 比亚迪工作体验 #
74421次浏览 281人参与
# 大厂VS公务员你怎么选 #
74437次浏览 681人参与