关注
第一题,并查集 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
相关推荐


深信服
| 校招
| 14个岗位
点赞 评论 收藏
分享
02-01 19:48
门头沟学院 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
- 1... 985计算机老学长掏心窝子:当年我踩过的坑,希望你们能绕开3.6W
- 2... 想要在大厂生存必须要学会提效6123
- 3... 腾讯实习基地-ieg-Level Infinite-一面5378
- 4... 字节飞书后端面试5144
- 5... 腾讯-后台开发-腾讯hr部门 一面4501
- 6... 实习入职第一天,应该做点啥❓4373
- 7... 2.17校招&实习招聘信息汇总4326
- 8... 重生归来,鼠鼠接手北区业务,这一次......4103
- 9... 实习第二天,被老员工欺负了3685
- 10... 【已挂】影石Insta360|嵌入式软件|日常实习一面3096
正在热议
更多
# 读研or工作,哪个性价比更高? #
24655次浏览 333人参与
# 如果重来一次你还会读研吗 #
154721次浏览 1701人参与
# 科大讯飞求职进展汇总 #
258966次浏览 2595人参与
# 秋招感动瞬间 #
11021次浏览 103人参与
# 阿里巴巴创始人马云回国 #
14268次浏览 87人参与
# 职场新人生存指南 #
195889次浏览 5398人参与
# 你最满意的offer薪资是哪家公司? #
11968次浏览 109人参与
# 长光卫星求职进展汇总 #
27606次浏览 184人参与
# 文科生还参加今年的春招吗 #
3439次浏览 29人参与
# 追觅科技求职进展汇总 #
8551次浏览 58人参与
# 选择和努力,哪个更重要? #
42375次浏览 472人参与
# 招聘要求与实际实习内容不符怎么办 #
41645次浏览 469人参与
# 打工人的工作餐日常 #
24756次浏览 221人参与
# 机械制造岗投递时间线 #
19332次浏览 324人参与
# 小红书求职进展汇总 #
40472次浏览 346人参与
# 影石Insta360求职进展汇总 #
107733次浏览 969人参与
# 如果再来一次,你还会学硬件吗 #
102857次浏览 1236人参与
# 机械人选offer,最看重什么? #
68633次浏览 433人参与
# 机械人怎么评价今年的华为 #
180373次浏览 1485人参与
# 滴!实习打卡 #
554972次浏览 6010人参与