# Untitled

unknown
c_cpp
23 days ago
5.7 kB
4
Indexable
Never
```#include <iostream>
#include <bits/stdc++.h>

using namespace std;
/*
1.

*/
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所在位置

*/

// 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的气球，每个球上下左右四个球中只要有>=两个和自己数字一样

*/
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

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