Weekly Contest 407

日期 2024/07/21
這次做滿第三題，第三題似曾相識，好像在與 LeetCode 某題內容相同。
第四題來不及看，難度約為 Medium+

• Number of Bit Changes to Make Two Integers Equal
• Vowels Game in a String
• Maximum Number of Operations to Move Ones to the End
• Minimum Operations to Make Array Equal to Target

第一題

int minChanges(int n, int k) {
    int ret = 0;
    for(int i = 0; i < 32; i++) {
        int x = n & (1 << i);
        x = !!x;
        int y = k & (1 << i);
        y = !!y;
        if(x == 0 && y == 1)
            return -1;

        if(x == 1 && y == 0)
            ret++;
    }
    return ret;
}

第二題

這題卡我太久，實際上 Alice 只要有任意一個母音就能贏。

bool doesAliceWin(string s) {
    stack<int> ss;
    int count = 0;
    for (int i = 0; i < s.size(); i++) {
        bool is_v = s[i] == 'i' || s[i] == 'a' || s[i] == 'e' ||
                    s[i] == 'o' || s[i] == 'u';
        count += is_v;
        if (count & 1)
            ss.push(i);
    }

    if (count == 0)
        return false;

    return true;
}

第三題

int maxOperations(string s) {
    const int n = s.size();
    int ret = 0;
    int i = 0;
    int count_one = 0;
    while (i < n) {
        if (s[i] == '1') {
            int j = i;
            for(; j < n; j++) {
                if(s[j] == '0')
                    break;
                count_one++;
            }

            for(; j < n; j++) {
                if(s[j] == '1')
                    break;
            }
            if(j != n || s[j - 1] == '0')
                ret += count_one;
            i = j;
        }else
            i++;
    }
    return ret;
}

第四題

參考討論區解答

long long minimumOperations(vector<int>& nums, vector<int>& target) {
    const int n = nums.size();
    using ll = long long;
    ll incr = 0;
    ll decr = 0;
    ll ret = 0;
    for(int i = 0; i < n; i++) {
        ll diff = target[i] - nums[i];
        if(diff > 0) {
            if(incr < diff)
                ret += diff - incr;
            incr = diff;
            decr = 0;
        }else if(diff < 0) {
            ll abs_diff = abs(diff);
            if(decr < abs_diff)
                ret += abs_diff - decr;
            decr = abs_diff;
            incr = 0;
        }else{
            incr = 0;
            decr = 0;
        }
    }
    return ret;
}

後來有更簡易的寫法，其中這題跟 LeetCode 1526 類似

long long minimumOperations(vector<int>& nums, vector<int>& target) {
    const int n = target.size();
    using ll = long long;
    ll pre = 0;
    ll ret = 0;
    for(int i = 0; i < n; i++) {
        ll diff = target[i] - nums[i] - pre;
        ret += max(diff, 0LL);
        pre = target[i] - nums[i];
    }
    return ret + max(-pre, 0LL);
}