第一题，并查集 100% // // Created by Chaopeng

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); }

牛客热帖