Untitled

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