Shawn's Blog

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        int n = nums.size();
        // get the count of subarrays that has at most k distinct integers.
        function<int(int)> atMostDistinct = [&](int k) {
            int res = 0;
            vector<int> freq(n + 1); // given "1 <= nums[i] <= nums.length".
            // cnt is the count of distinct integers within [left, right].
            for (int left = 0, right = 0, cnt = 0; right < n; ++right) {
                if (++freq[nums[right]] == 1) ++cnt;
                while (cnt > k)
                    if (--freq[nums[left++]] == 0) --cnt;
                // add the count of new subarrays that ends with nums[right].
                res += right - left + 1;
            }
            return res;
        };
        return atMostDistinct(k) - atMostDistinct(k - 1);
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        int preSign = 0, left = 0, right = 1, ans = 1;
        while (right < n) {
            int sign = arr[right] - arr[right - 1];
            if (sign == 0) {
                ans = max(ans, right - left);
                left = right;
            } else if ((sign > 0 && preSign > 0) || (sign < 0 && preSign < 0)) {
                ans = max(ans, right - left);
                left = right - 1;
            }
            preSign = sign;
            ++right;
        }
        return max(ans, right - left);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        int up = 1, down = 1, ans = 1;
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i + 1] > arr[i]) {
                up = down + 1;
                down = 1;
            } else if (arr[i + 1] < arr[i]) {
                down = up + 1;
                up = 1;
            } else {
                up = down = 1;
            }
            ans = max(ans, max(up, down));
        }
        return ans;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        const int n = cardPoints.size();
        int windowSize = n - k;
        int currWindowSum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);
        int sum = currWindowSum, minWindowSum = currWindowSum;
        for (int i = windowSize; i < n; ++i) {
            sum += cardPoints[i];
            currWindowSum += cardPoints[i] - cardPoints[i - windowSize];
            minWindowSum = min(minWindowSum, currWindowSum);
        }
        return sum - minWindowSum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        const int n = cardPoints.size();
        // take 'i' card(s) from left (and 'k - i' card(s) from right),
        // how many points could we get. i = 0 at first.
        int dp = accumulate(cardPoints.rbegin(), cardPoints.rbegin() + k, 0);
        int maxPoints = dp, idxDiff = n - k;
        for (int i = 0; i < k; ++i) {
            dp = dp + cardPoints[i] - cardPoints[i + idxDiff];
            maxPoints = max(maxPoints, dp);
        }
        return maxPoints;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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;
    }
};
0%