Untitled
unknown
c_cpp
10 months ago
5.7 kB
8
Indexable
#include <iostream> #include <bits/stdc++.h> using namespace std; /* 1. 给一个num 按照位数交替求和 eg 32685 -> 3-2+6-8+5 = 4 */ int problem1(int num){ vector<int> least, sec_least; while (num) { if (least.size() == sec_least.size()) least.push_back(num % 10); else sec_least.push_back(num % 10); num /= 10; } int tmp_ans = accumulate(least.begin(), least.end(), 0) - accumulate(sec_least.begin(), sec_least.end(), 0); if (least.size() > sec_least.size()) return tmp_ans; else return -tmp_ans; } /* 2. 鸟在森林里寻找材料建造巢穴, input是一个array(表示材料所在位置以及数量)和bird所在位置 分别向左飞取一根树枝 然后向反方向飞再取一根树枝 直到取到100个树枝才能建好一个巢,返回建造过程(每次去材料的index) */ // assume wood[i] = {pos, amount} void helper(vector<vector<int>> &wood, vector<int> &ans, int x){ if (x < 0 || x >= wood.size()) return; wood[x][1]--; ans.push_back(x); return; } vector<int> problem2(vector<vector<int>> &wood, int init_pos){ sort(wood.begin(), wood.end()); int l = 0, r = 0; while (init_pos >= wood[r][0]){ r++; } l = r - 1; vector<int> ans; while (ans.size() < 100){ if(r < wood.size()){ if (wood[r][1] > 0) helper(wood, ans, r); else{ r++; helper(wood, ans, r); } } if(l >= 0){ if (wood[l][1] > 0) helper(wood, ans, l); else{ l--; helper(wood, ans, l); } } } return ans; } /* 3. 一个矩阵,塞满标识1-10000的气球,每个球上下左右四个球中只要有>=两个和自己数字一样 这几个相同数字的就全部爆掉。 等能爆的都爆掉后, 剩下的球会掉到最下面能放球的位置,返回最终矩阵,空格标0, 每次爆破完都会落下 */ int counter(vector<vector<int>> &mat, int i, int j){ int tmp = mat[i][j], cnt = 0; if (i > 0 && mat[i - 1][j] == tmp) cnt++; if (i + 1 < mat.size() && mat[i + 1][j] == tmp) cnt++; if (j > 0 && mat[i][j - 1] == tmp) cnt++; if (j + 1 < mat[0].size() && mat[i][j + 1] == tmp) cnt++; return cnt >= 2; } void DFS(vector<vector<int>> &mat, int r, int c){ int tmp = mat[r][c]; mat[r][c] = 0; int dir[4] = {0, 1, 0, -1}; for (int i = 0; i < 4; i++){ int newr = r + dir[i]; int newc = c + dir[(i + 1) % 4]; if(newr < 0 || newc < 0 || newr == mat.size() || newc == mat[0].size()) continue; if (tmp != 0 && mat[newr][newc] == tmp) DFS(mat, newr, newc); } return; } vector<vector<int>> problem3(vector<vector<int>> &mat){ int m = mat.size(), n = mat[0].size(); for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ if (mat[i][j] != 0 && counter(mat, i, j)) DFS(mat, i, j); } } for (int i = 0; i < n; i++){ int down = m - 1, up = 0; while (down > up){ while (down > up && mat[down][i] != 0){ down--; } while (down > up && mat[up][i] == 0){ up++; } if (down > up){ swap(mat[down][i], mat[up][i]); down--; up++; } } } return mat; } /*4.给你一个char array 只有[‘0’,‘0’,‘0’,‘0’,‘0’] 有两个operation L:找到最小位置的 0 改为 1 CI 找到第I个位置改成1 给你一个序列的operations让你输出结果 eg[‘0’,‘0’,‘0’,‘0’,‘0’] LLC3 ->[‘1’,‘1’,‘0’,‘1’,‘0’]*/ void problem4(string s, vector<char> & v){ int n = s.size(), vn = v.size(); queue<int> q; for (int i = 0; i < vn; i++){ if (v[i] == '0') q.push(i); } int i = 0; while (i < n){ if (s[i] == 'L'){ v[q.front()] = '1'; q.pop(); i++; } else{ i++; int tmp = 0; while (i < n && isdigit(s[i])){ tmp = tmp * 10 + s[i] - '0'; i++; } v[tmp] = '1'; } } return; } int main(){ cout << "Problem4:\n"; vector<char> input4 = {'0', '0', '0', '0', '0'}; string input4str = "LLC3"; problem4(input4str, input4); for (auto a : input4){ cout << a << ' '; } cout << '\n'; cout << "---------------------\n"; cout << "Problem1:\n"; cout << problem1(32685) << '\n'; cout << "---------------------\n"; cout << "Problem2:\n"; vector<vector<int>> wood = {{0, 10}, {2, 5}, {3, 80}, {5, 15}}; auto ans1 = problem2(wood, 1); for(int i = 0; i < 100; i++){ cout << ans1[i] << ' '; if(i%9 == 0) cout << '\n'; } cout << "---------------------\n"; cout << "Problem3:\n"; vector<vector<int>> mat = {{1, 2, 3, 4}, {5, 2, 3, 4}, {1, 2, 3, 4}, {1, 2, 2, 4}}; problem3(mat); for(int i = 0; i < mat.size(); i++){ for(int j = 0; j < mat[0].size(); j++){ cout << mat[i][j] << ' '; } cout << '\n'; } return 0; }
Editor is loading...
Leave a Comment