Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size() - 1, ans = 0;
        for (int i = 0; i < n; ++i) 
            ans += max(0, prices[i + 1] - prices[i]);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cash = 0, hold = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            cash = max(cash, hold + prices[i]);
            hold = max(hold, cash - prices[i]);
        }
        return cash;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price = INT_MAX, max_profit = 0;
        for (int price : prices) {
            max_profit = max(max_profit, price - min_price);
            min_price = min(min_price, price);
        }
        return max_profit;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        for (int i = 1; i < n; ++i) {
            triangle[i][0] += triangle[i - 1][0];
            triangle[i][i] += triangle[i - 1][i - 1];
            for (int j = 1; j < i; ++j)
                triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
        }
        return *min_element(triangle[n - 1].begin(), triangle[n - 1].end());
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);
        for (int row = 0; row < numRows; ++row) {
            ans[row].resize(row + 1);
            ans[row][0] = ans[row][row] = 1;
            for (int col = 1; col < row; ++col)
                ans[row][col] = ans[row - 1][col - 1] + ans[row - 1][col];
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i)
            row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;
        return row;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int>> q;
    int k;
public:
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (auto& x: nums)
            add(x);
    }
    int add(int val) {
        q.push(val);
        if (q.size() > k)
            q.pop();
        return q.top();
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string minWindow(string s, string t) {
        int n1 = s.size(), n2 = t.size();
        if (n1 < n2) return "";
        vector<int> freq(128);
        for (char c : t)
            freq[c]++;
        int left = 0, right = 0, minWinLen = INT_MAX, head = 0;
        while (right < n1) {
            if (freq[s[right++]]-- > 0)
                --n2; // char in t.
            while (n2 == 0) { // valid window.
                if (right - left < minWinLen)
                    minWinLen = right - (head = left); // get min window length.
                if (freq[s[left++]]++ == 0)
                    n2++;
            }
        }
        return minWinLen == INT_MAX ? "" : s.substr(head, minWinLen);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MedianFinder {
private:
    vector<int> data;
public:
    MedianFinder() {
    }
    void addNum(int num) {
        if (data.empty())
            data.emplace_back(num);
        else
            data.insert(lower_bound(data.begin(), data.end(), num), num);
    }
    double findMedian() {
        int n = data.size();
        return n & 1 ? data[n / 2] : (data[n / 2 - 1] + data[n / 2]) * 0.5;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MedianFinder {
private:
    priority_queue<int> lo; // max heap
    priority_queue<int, vector<int>, greater<int>> hi; // min heap
public:
    MedianFinder() {
    }
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top());
        lo.pop();
        if (lo.size() < hi.size()) {
            lo.push(hi.top());
            hi.pop();
        }
    }
    double findMedian() {
        return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
    }
};
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
class MedianFinder {
private:
    multiset<int> data;
    multiset<int>::iterator lo, hi;
public:
    MedianFinder(): lo(data.end()), hi(data.end()) {
    }
    void addNum(int num) {
        const int n = data.size();
        data.insert(num);
        if (!n) { // the 1st element.
            lo = hi = data.begin();
        } else if (n & 1) { // odd size before.
            if (num < *lo) --lo;
            else ++hi;
        } else { // even size before.
            if (num > *lo && num < *hi) {
                ++lo;
                --hi;
            } else if (num >= *hi) ++lo;
            else lo = --hi;
        }
    }
    double findMedian() {
        return (*lo + *hi) * 0.5;
    }
};

Posted on Edited 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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        const int n1 = s1.size(), n2 = s2.size();
        if (n1 > n2) return false;
        vector<int> freq(26), winFreq(26);
        int cnt = 0, winCnt = 0;
        for (char c : s1)
            if (freq[c - 'a']++ == 0)
                ++cnt;
        int left = 0, right = 0;
        while (right < n2) {
            int idx = s2[right++] - 'a';
            if (freq[idx] > 0)
                if (++winFreq[idx] == freq[idx])
                    ++winCnt;
            while (winCnt == cnt) {
                if (right - left == n1) return true;
                idx = s2[left++] - 'a';
                if (freq[idx] > 0)
                    if (--winFreq[idx] < freq[idx])
                        --winCnt;
            }
        }
        return false;
    }
};

Posted on Edited 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);
    }
};
0%