Weekly Contest 406

日期 2024/07/14

這次第三題與第四題一樣，差別在於回傳的型態，我在做完第三題的時候直接複製貼上程式碼到第四題，導致當下找不到錯誤。結果只有做完三題。

• Lexicographically Smallest String After a Swap
• Delete Nodes From Linked List Present in Array
• Minimum Cost for Cutting Cake I
• Minimum Cost for Cutting Cake II

第一題

string getSmallestString(string s) {
    const int n = s.size();
    for(int i = 1; i < n; i++) {
        int x = s[i] -'0';
        int y = s[i - 1] - '0';
        if((x & 1) == (y & 1) && (x < y)) {
            swap(s[i], s[i - 1]);
            break;
        }
    }
    return s;
}

第二題

ListNode* modifiedList(vector<int>& nums, ListNode* head) {
    unordered_set<int> ss(nums.begin(), nums.end());
    vector<ListNode*> nn;
    ListNode* node = head;
    while(node) {
        if(ss.find(node->val) == ss.end()) {
            nn.push_back(node);
        }
        node = node->next;
    }

    if(nn.size() > 0) {
        head = nn[0];
        for(int i = 1; i < nn.size(); i++) {
            nn[i - 1]->next = nn[i];
        }
        nn[nn.size() - 1]->next = nullptr;
        return head;
    }else
        return nullptr;
}

第三題

int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
    priority_queue<int> pqh(horizontalCut.begin(), horizontalCut.end());
    priority_queue<int> pqv(verticalCut.begin(), verticalCut.end());
    int hcount = 1;
    int vcount = 1;

    int ret = 0;

    const int len = horizontalCut.size() + verticalCut.size();
    for(int i = 0; i < len; i++) {
        int h = 0;
        int v = 0;
        if(!pqh.empty()) {
            h = pqh.top();
        }

        if(!pqv.empty()) {
            v = pqv.top();
        }
        // cout << h << " " << v << endl;
        // cout << hcount << " " << vcount << endl;
        if(h > v) {
            ret += h * hcount;
            vcount++;
            pqh.pop();
        }else {
            ret += v * vcount;
            hcount++;
            pqv.pop();
        }
    }
    return ret;
}

第四題

using ll = long long;
long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
    priority_queue<int> pqh(horizontalCut.begin(), horizontalCut.end());
    priority_queue<int> pqv(verticalCut.begin(), verticalCut.end());
    ll hcount = 1;
    ll vcount = 1;

    ll ret = 0;

    const int len = horizontalCut.size() + verticalCut.size();
    for(int i = 0; i < len; i++) {
        ll h = 0;
        ll v = 0;
        if(!pqh.empty()) {
            h = pqh.top();
        }

        if(!pqv.empty()) {
            v = pqv.top();
        }

        if(h > v) {
            ret += h * hcount;
            vcount++;
            pqh.pop();
        }else{
            ret += v * vcount;
            hcount++;
            pqv.pop();
        }
    }
    return ret;
}