Shawn's Blog

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int n = nums.size(), cnt = 1;
        for (int i = 0; i <= n - 2; ++i) {
            if (nums[i] > nums[i + 1]) {
                if (cnt-- == 0) return false;
                if (i == 0) nums[i] = INT_MIN;
                // else if (nums[i - 1] <= nums[i + 1]) nums[i] = nums[i - 1];
                // else nums[i + 1] = nums[i];
                else if (nums[i - 1] > nums[i + 1]) nums[i + 1] = nums[i];
            }
        }
        return true;
    }
};

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        const int n = s.size();
        int left = 0, right = 0, cost = 0, ans = 0;
        while (right < n) {
            cost += abs(s[right] - t[right]);
            ++right;
            if (cost <= maxCost) {
                ans = max(ans, right - left);
            } else {
                while (cost > maxCost && left < right) {
                    cost -= abs(s[left] - t[left]);
                    ++left;
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.begin() + k, 0);
        int maxSum = sum;
        for (int i = k; i < nums.size(); ++i) {
            sum += (nums[i] - nums[i - k]);
            maxSum = max(maxSum, sum);
        }
        return 1.0 * maxSum / k;
    }
};

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        vector<double> medians;
        unordered_map<int, int> hash_table; // deleted element -> frequency.
        priority_queue<int> lo;
        priority_queue<int, vector<int>, greater<int>> hi;
        int i = 0;
        while (i < k)
            lo.push(nums[i++]);
        for (int j = 0; j < k / 2; j++) {
            hi.push(lo.top());
            lo.pop();
        }

        while (true) {
            medians.push_back(k & 1 ? lo.top() : ((double) lo.top() + (double) hi.top()) * 0.5);
            if (i >= nums.size())
                break;
            int out_num = nums[i - k],
                in_num = nums[i++],
                balance = 0;
            
            balance += (out_num <= lo.top() ? -1 : 1);
            hash_table[out_num]++;

            if (!lo.empty() && in_num <= lo.top()) {
                balance++;
                lo.push(in_num);
            } else {
                balance--;
                hi.push(in_num);
            }

            if (balance < 0) {
                lo.push(hi.top());
                hi.pop();
                balance++;
            }
            if (balance > 0) {
                hi.push(lo.top());
                lo.pop();
                balance--;a
            }

            while (hash_table[lo.top()]) {
                hash_table[lo.top()]--;
                lo.pop();
            }
            while (!hi.empty() && hash_table[hi.top()]) {
                hash_table[hi.top()]--;
                hi.pop();
            }
        }
        return medians;
    }
};

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size(), left = 0, right = 0, maxCnt = 0;
        vector<int> freq(26);
        while (right < n) {
            maxCnt = max(maxCnt, ++freq[s[right++] - 'A']);
            if (right - left > maxCnt + k) {
                --freq[s[left++] - 'A'];
            }
        }
        return right - left;
    }
};

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        int sumA = accumulate(A.begin(), A.end(), 0);
        int sumB = accumulate(B.begin(), B.end(), 0);
        int delta = (sumA - sumB) / 2;
        unordered_set<int> rec(A.begin(), A.end());
        vector<int> ans;
        for (auto& y : B) {
            int x = y + delta;
            if (rec.count(x)) {
                ans = vector<int>{x, y};
                break;
            }
        }
        return ans;
    }
};

class UF {
public:
    vector<int> f;
    vector<int> size;
    int n;
    int setCount; // count of current connected components
    UF(int _n): n(_n), setCount(_n), f(_n), size(_n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    bool _union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        if (size[x] < size[y])
            swap(x, y);
        f[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};
class Solution {
public:
    bool check(const string &a, const string &b, int len) {
        int num = 0;
        for (int i = 0; i < len; i++)
            if (a[i] != b[i])
                if (++num > 2) return false;
        return true;
    }
    int numSimilarGroups(vector<string> &strs) {
        const int n = strs.size(), m = strs[0].length();
        UF uf(n);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                if (uf.connected(i, j)) continue;
                if (check(strs[i], strs[j], m))
                    uf._union(i, j);
            }
        return uf.setCount;
    }
};