9.8 字节跳动 2.6 / 4

前两题 A了 第三题调不动了 第四题 60%

第一题 机器人排队

单调栈即可

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
    int n, ind = 0;
    cin >> n;
    vector<int> arr(n);
    vector<int> cnt(n, 0);
    stack<int> sta;
    for(int i=0; i<n; i++){
        cin >> arr[i];
        while(!sta.empty() && arr[i] > arr[sta.top()]) 
            sta.pop();
        if(!sta.empty()) cnt[sta.top()]++;
        sta.push(i);
    }
    for(int i=1; i<n; i++)
        if(cnt[i] > cnt[ind]) ind = i;
    cout << arr[ind] << endl;
    return 0;
}

第二题 倒水

BFS

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

struct Node {
    int wat[3], step;
    Node(int a, int b, int c, int d) {
        wat[0] = a, wat[1] = b, wat[2] = c, step = d;
    };
};

int hashCode(Node n) {
    return 10000 * n.wat[0] + 100 * n.wat[1] + n.wat[2];
}

int main() {
    int wat[3], tar;
    cin >> wat[0] >> wat[1] >> wat[2] >> tar;
    if(tar > wat[0] + wat[1] + wat[2]) {
        cout << -1 << endl;
        return 0;
    }
    queue<Node> que;
    que.push(Node(0, 0, 0, 0));
    unordered_set<int> hashSet;
    hashSet.insert(0);
    while(!que.empty()) {
        Node cur = que.front();
        que.pop();
        if(cur.wat[0] == tar || cur.wat[1] == tar || cur.wat[2] == tar) {
            cout << cur.step << endl;
            return 0;
        }
        // 直接倒满或倒空
        for(int i=0; i<3; i++) {
            Node tem = cur;
            tem.wat[i] = 0;
            tem.step++;
            if(hashSet.find(hashCode(tem)) == hashSet.end()) {
                hashSet.insert(hashCode(tem));
                que.push(tem);
            }
            tem.wat[i] = wat[i];
            if(hashSet.find(hashCode(tem)) == hashSet.end()) {
                hashSet.insert(hashCode(tem));
                que.push(tem);
            }
        }
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++) {
                if(i == j || cur.wat[i] == 0 || cur.wat[j] == wat[j]) continue;
                Node tem = cur;
                tem.step++;
                int canPour = wat[j] - tem.wat[j];
                if(tem.wat[i] >= canPour) {
                    tem.wat[j] = wat[j];
                    tem.wat[i] -= canPour;
                } else {
                    tem.wat[j] += tem.wat[i];
                    tem.wat[i] = 0;
                }
                if(hashSet.find(hashCode(tem)) == hashSet.end()) {
                    hashSet.insert(hashCode(tem));
                    que.push(tem);
                }
            }
    }
    cout << -1 << endl;
    return 0;
}

第三题 小Q的方块

#include <iostream>
#include <vector>
using namespace std;

int getRes(vector<char> &arr, int l, int r) {
    if(l > r) return 0;
    if(l == r && arr[l-1] != '<' && arr[l-1] != '>') return arr[l-1] - '0';
    vector<char> tem;
    for(int i=l-1; i<r; i++)
        tem.push_back(arr[i]);
    int flag = 1;
    int ind = 0, len = r - l + 1, res = 0;
    while(ind >= 0 && ind < len) {
        if(tem[ind] == '<') {
            if(ind-1 >= 0 && tem[ind-1] == '<' || tem[ind-1] == '>')
                len--, tem.erase(tem.begin() + ind);
            ind--, flag = -1;
        } else if(tem[ind] == '>') {
            if(ind+1 < len && tem[ind+1] == '<' || tem[ind+1] == '>') 
                len--, tem.erase(tem.begin() + ind);
            ind++, flag = 1;
        } else {
            res += tem[ind] - '0';
            if(tem[ind] == '0')
                len--, tem.erase(tem.begin() + ind);
            else tem[ind]--;
            ind += flag;
        }
        //for(auto &it:tem) cout<< it<< ' '; cout << endl;
    }
    return res;
}

int main() {
    int n, m, q, l, r;
    cin >> n >> m >> q;
    vector<char> arr(n);
    for(int i=0; i<n; i++)
        cin >> arr[i];
    for(int i=0; i<q; i++) {
        cin >> l >> r;
        int res = getRes(arr, l, r);
        cout << res << endl;
    }
    return 0;
}

第四题 字符串解码

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    string str;
    cin >> str;
    set<string> res;
    char ch = 'A' + str[0] - '0' - 1;
    res.insert(string(1, ch));

    for(int j=1; j<str.size(); j++) {
        set<string> temp;
        for(auto tem:res) {
            if(str[j] != '0') {
                ch = str[j] - '0' + 'A' - 1;
                temp.insert(tem + string(1, ch));
            }
            if(str[j-1] == '1' || (str[j-1] == '2' && str[j] < '7')) {
                ch = 'A' + (str[j-1]-'0') * 10 + str[j] - '0' - 1;
                tem.pop_back();
                temp.insert(tem + string(1, ch));
            }
        }
        swap(temp, res);
    }
    for(auto &it:res)
        cout << it << endl;
    return 0;
}