Weekly Contest 395

日期：2024/04/28

我想這就是平常寫 LeetCode 跟寫 Contest 的差異，今天第二題就是想好解題思路之後一直覺得這是錯的導致沒打完程式碼，

$O(n^3)$ 時間複雜度讓我想太久。
寫程式題目一定是先求有，再去思考好的解答。另外，題目用 Constraints 去推測時間複雜度是可以幫助作答。

這次只有做出第一題，其他題目就是要想一下或是花點時間就可以解出來了。

真是太崩潰爛泥了

• Find the Integer Added to Array I
• Find the Integer Added to Array II
• Minimum Array End
• Find the Median of the Uniqueness Array

第二題

class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        const int m = nums1.size();
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
        
        int ret = INT_MAX;
        for(int i = 0; i < m; i++) {
            for(int j = i - 1; j >= 0; j--) {
                int x = sum1 - nums1[i] - nums1[j];
                int y = sum2 - x;
                bool c1 = abs(y) % (m - 2) == 0;
                if(c1 && check(nums1, nums2, i, j)) {
                    int z = abs(y) / (m - 2);
                    if(y < 0)
                        ret = min(-z, ret);
                    else
                        ret = min(z, ret);
                }
                    
            }
        }
        
        return ret;
    }

    bool check(vector<int>& nums1, vector<int>& nums2, int ignore_i, int ignore_j) {
        const int n = nums1.size();
        bool diff_found = false;
        int diff;

        int i = 0;
        int j = 0;
        while(i < n) {
            if(i == ignore_i || i == ignore_j) {
                i++;
                continue;
            }

            if(!diff_found) {
                diff_found = true;
                diff = nums2[j] - nums1[i];
            }else{
                int d = nums2[j] - nums1[i];
                if(d != diff)
                    return false;
            }
            
            i++;
            j++;
        }

        return true;
    }
};

第三題

class Solution {
public:
    long long minEnd(int n, int x) {
        long long ans = x;
        for(int i = 0; i < n - 1; i++) {
            ans = (ans + 1) | x;
        }
        return ans;
    }
};