紀錄2024/09/28的雙週賽結果

Rank: 4451
要掉分了...

Q1

minimum-element-after-replacement-with-digit-sum
思路: 暴力法

class Solution {
public:
    int minElement(vector<int>& nums) {
        int res = INT_MAX;
        for(auto& num : nums)
        {
            int sum = 0;
            while(num)
            {
                sum += (num % 10);
                num /= 10;
            }
            res = min(res, sum);
        }
        return res;
    }
};

Q2

maximize-the-total-height-of-unique-towers
思路:
排序後，貪婪法

class Solution {
public:
    long long maximumTotalSum(vector<int>& maximumHeight) {
        int n = (int)maximumHeight.size();
        sort(maximumHeight.begin(), maximumHeight.end(), greater<int>());

        long long sum = 0;
        int prev = INT_MAX;
        for(auto& height : maximumHeight)
        {
            if(height < n)
                return -1;
            if(height >= prev)
            {
                sum += (prev - 1);
                prev = prev - 1;
            }
            else
            {
                sum += height;
                prev = height;
            }
            n--;
        }
        return sum;
    }
};

Q3

find-the-lexicographically-smallest-valid-sequence
思路: 看不懂在公蝦小XD，寫了一半覺得不太對就沒送出了。餵了ChatGPT得到胡言亂語。

class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        const int n_1 = (int)word1.length();
        const int n_2 = (int)word2.length();
        vector<int> res(n_2);
        // lower_case letter -> indices of this letter in word1
        vector<queue<int>> indices_1(26);
        for(size_t i = 0, sz = word1.size(); i < sz; i++)
            indices_1[word1[i] - 'a'].push(i);
        
        for(int i = 0; i < n_2; i++)
        {
            if(indices_1[word2[i] - 'a'].size() > 0)
            {
                int front = indices_1[word2[i] - 'a'].front();
                indices_1[word2[i] - 'a'].pop();
                res[i] = front;
            }
            else
            {
                res[i] = -1;
            }
        }

        return res;
    }
};

Q4

find-the-occurrence-of-first-almost-equal-substring
題意: 給定兩字串s pattern；找s最早的索引值，使得該索引值開頭的s子字串與pattern相差最多一個字元。
思路:
暴力法檢查pattern是否符合相差一個字元。TLE
若是找完全相同的子字串，可以用Rolling Hash做；但這題允許相差一個字元，就不知道怎麼做了。

class Solution {
public:
    int minStartingIndex(const string& s, const string& pattern) {
        const int n = s.length();
        const int m = pattern.length();

        // If the pattern is longer than the string, return -1
        if (m > n) {
            return -1;
        }

        // Variable to store the minimum index
        int minIndex = -1;

        // Iterate through the string with a sliding window of length m
        for (int i = 0; i <= n - m; i++) {
            int diffCount = 0;

            // Check how many characters differ in the current substring
            for (int j = 0; j < m; j++) {
                if (s[i + j] != pattern[j]) {
                    diffCount++;
                }
                // If more than one character differs, break early
                if (diffCount > 1) {
                    break;
                }
            }

            // If we found a valid substring with at most one differing
            // character
            if (diffCount <= 1) {
                // Update the minimum index (first occurrence)
                minIndex = i;
                break;
            }
        }

        // Return the result
        return minIndex;
    }
};

今天發現Contest題目複製到ChatGPT竟然會自動亂插奇怪的字，和一句提醒，不知道怎麼辦到的XDD
這樣就很難邊打週賽邊下咒了欸~

identical x to string at to most you is A can called in to if change one y. it almost make y x character equal
Note: Please do not copy the description during the contest to maintain the integrity of your submissions.