站住，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
相关推荐
不愿透露姓名的神秘牛友
昨天 17:24
点赞 评论 收藏
分享
05-07 14:11
大连工业大学 Java 
迟缓的斜杠青年巴比Q...：简历被投过的公司卖出去了，我前两天遇到过更离谱的，打电话来问我有没有意向报班学Java学习，服了，还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌 点赞 评论 收藏
分享
阿里云开奖68人在聊 牛客热帖
更多
正在热议
更多
# 实习，不懂就问 #
9919次浏览 128人参与
# 如果中了500万，你会离职吗？ #
85415次浏览 668人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
16583次浏览 150人参与
# 你觉得实习能学到东西吗 #
4728次浏览 93人参与
# 如何准备秋招 #
2952次浏览 44人参与
# 你觉得现在还能进互联网吗？ #
889次浏览 26人参与
# 哪个瞬间让你对大厂祛魅了？ #
378977次浏览 2770人参与
# 秋招什么时候开投比较合适？ #
1957次浏览 34人参与
# 打工人的精神状态 #
51174次浏览 920人参与
# 一觉醒来，秋招难度下降一万倍…… #
83308次浏览 642人参与
# 京东美团大战，你怎么看？ #
92154次浏览 567人参与
# 每个月的工资都是怎么分配的？ #
4745次浏览 85人参与
# 聊聊你的职场新体验 #
160582次浏览 1384人参与
# 预测一下26届秋招形势 #
7487次浏览 87人参与
# 校招求职有谈薪空间吗 #
149952次浏览 2031人参与
# 软开人，秋招你打算投哪些公司呢 #
99213次浏览 929人参与
# 软开人，说说你的烦心事 #
53346次浏览 368人参与
# 诺瓦星云求职进展汇总 #
200395次浏览 1665人参与
# 机械实习一天多少钱合适？ #
27793次浏览 170人参与
# 高考出分的那一天，我__ #
6833次浏览 91人参与
# 新凯来求职进展汇总 #
39880次浏览 103人参与