站住，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
相关推荐
03-13 21:45
河北工程技术学院 嵌入式软件开发 点赞 评论 收藏
分享
查看15道真题和解析 牛客热帖
更多
正在热议
更多
# 这个offer值得去吗？ #
19222次浏览 170人参与
# 字节开奖 #
149018次浏览 665人参与
# 联宝杯大学生创新大赛，你的技术值得产业级答案 #
47367次浏览 513人参与
# 如果春招能重来，我会___ #
19981次浏览 213人参与
# 薪资爆料 #
421725次浏览 2223人参与
# 除了线上，还能去哪些地方投简历 #
10997次浏览 112人参与
# 刚工作的你，踩过哪些坑？ #
46496次浏览 295人参与
# HR问：你期望的薪资是多少？如何回答 #
99162次浏览 830人参与
# 大学四年该怎么过，才不算浪费时间？ #
23716次浏览 104人参与
# 一份好的简历长什么样？ #
41807次浏览 505人参与
# 你面试被问到过哪些不会的问题？ #
122280次浏览 1944人参与
# 今年形式下双非本找得到工作吗 #
328629次浏览 1774人参与
# 诺瓦星云求职进展汇总 #
258856次浏览 1743人参与
# 双非本科求职如何逆袭 #
1646111次浏览 13060人参与
# 你觉得实习能学到东西吗 #
154025次浏览 1493人参与
# 职场破防瞬间 #
381653次浏览 2847人参与
# 你被哪些公司挂了？ #
193110次浏览 1043人参与
# 实习最晚的一次下班是几点 #
35866次浏览 171人参与
# 字节求职进展汇总 #
1845568次浏览 15385人参与
# 26届校招投递进展 #
670158次浏览 3953人参与
# 双非应该如何逆袭？ #
584330次浏览 6376人参与