Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int size = flowerbed.size(), i = 0, cnt = 0;
        while (i < size) {
            if (flowerbed[i]) {
                ++i;
            } else if ((i == 0 || !flowerbed[i - 1]) && (i == size - 1 || !flowerbed[i + 1])) {
                flowerbed[i] = 1;
                ++cnt;
            }
            if (cnt >= n) return true;
            ++i;
        }
        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
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });
        const int n = intervals.size();
        int right = intervals[0][1];
        int remains = 1;
        for (int i = 1; i < n; ++i)
            if (intervals[i][0] >= right) {
                ++remains;
                right = intervals[i][1];
            }
        return n - remains;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int n = intervals.length;
        int right = intervals[0][1];
        int remains = 1;
        for (int i = 1; i < n; ++i)
            if (intervals[i][0] >= right) {
                ++remains;
                right = intervals[i][1];
            }
        return n - remains;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals: return 0
        intervals.sort(key = lambda x: x[1])
        n = len(intervals)
        right = intervals[0][1]
        remains = 1
        for i in range(1, n):
            if intervals[i][0] >= right:
                remains += 1
                right = intervals[i][1]
        return n - remains

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for (int s : stones)
            q.push(s);
        while (q.size() > 1) {
            int y = q.top(); q.pop();
            int x = q.top(); q.pop();
            if (y > x)
                q.push(y - x);
        }
        return q.empty() ? 0 : q.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        for (int stone : stones)
            q.offer(stone);
        while (q.size() > 1) {
            int y = q.poll();
            int x = q.poll();
            if (y > x) {
                q.offer(y - x);
            }
        }
        return q.isEmpty() ? 0 : q.poll();
    }
}
1
2
3
4
5
6
7
8
9
10
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        q = [-stone for stone in stones]
        heapq.heapify(q)
        while len(q) > 1:
            y, x = heapq.heappop(q), heapq.heappop(q)
            if x != y:
                heapq.heappush(q, y - x)
        if q: return -q[0]
        return 0

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int patches = 0;
        long long x = 1;
        int length = nums.size(), index = 0;
        while (x <= n) {
            if (index < length && nums[index] <= x) {
                x += nums[index];
                index++;
            } else {
                x <<= 1;
                patches++;
            }
        }
        return patches;
    }
};

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
28
29
30
31
32
33
34
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        if (2 * k > prices.length) {
            int ans = 0;
            for (int i = 1; i < prices.length; i++) {
                ans += Math.max(prices[i] - prices[i - 1], 0);
            }
            return ans;
        }
        int[][] dp = new int[2][2 * k + 1];
        for (int i = 0; i < 2 * k + 1; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j <= 2 * k; j += 2) {
                dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], j - 1 >= 0? dp[(i - 1) % 2][j - 1] + prices[i] - prices[i - 1] : 0);
            }
            for (int j = 1; j <= 2 * k -1; j += 2) {
                int profit = prices[i] - prices[i - 1];
                dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j] + profit, dp[(i - 1) % 2][j - 1]);
                if (j >= 2) {
                    dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - 2] + profit);
                }
            }
        }
        int r = (prices.length - 1) % 2;
        int ans = 0;
        for (int i = 0; i < 2 * k + 1; i++) {
            ans = Math.max(ans, dp[r][i]);
        }
        return ans;
    }
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0};
        for (int i = 0; i < s.size(); ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
};

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
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        const int rows = matrix.size();
        if (rows == 0) return 0;
        const int cols = matrix[0].size();
        vector<vector<int>> left(rows, vector<int>(cols, 0));
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (matrix[r][c] == '1')
                    left[r][c] = (c == 0 ? 0 : left[r][c - 1]) + 1;
        int ans = 0;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (matrix[r][c] == '1') {
                    int width = left[r][c];
                    int area = width;
                    for (int k = r - 1; k >= 0; --k) {
                        width = min(width, left[k][c]);
                        area = max(area, width * (r - k + 1));
                    }
                    ans = max(ans, area);
                }
        return ans;
    }
};
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
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        const int rows = matrix.size();
        if (rows == 0) return 0;
        const int cols = matrix[0].size();
        vector<vector<int>> left(rows, vector<int>(cols, 0));
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                if (matrix[r][c] == '1')
                    left[r][c] = (c == 0 ? 0 : left[r][c - 1]) + 1;
        int ans = 0;
        for (int c = 0; c < cols; ++c) {
            vector<int> up(rows, 0), down(rows, 0);
            stack<int> s;
            for (int r = 0; r < rows; ++r) {
                while (!s.empty() && left[s.top()][c] >= left[r][c])
                    s.pop();
                up[r] = s.empty() ? -1 : s.top();
                s.push(r);
            }
            s = stack<int>();
            for (int r = rows - 1; r >= 0; --r) {
                while (!s.empty() && left[s.top()][c] >= left[r][c])
                    s.pop();
                down[r] = s.empty() ? rows : s.top();
                s.push(r);
            }
            for (int r = 0; r < rows; ++r) {
                int height = down[r] - up[r] - 1;
                ans = max(ans, height * left[r][c]);
            }
        }
        return ans;
    }
};

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) return 0;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        stack<int> s;
        s.push(0);
        int ans = 0;
        for (int i = 1; i < heights.size(); ++i) {
            while (heights[i] < heights[s.top()]) {
                int h = heights[s.top()]; s.pop();
                int w = i - s.top() - 1;
                ans = max(ans, h * w);
            }
            s.push(i);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int ans = 0, i = 0, j = 0;
        while (i < g.size() && j < s.size()) {
            if (s[j] >= g[i]) {
                ++i;
                ++ans;
            }
            ++j;
        }
        return ans;
    }
};

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 candy(vector<int>& ratings) {
        const int n = ratings.size();
        vector<int> left(n);
        for (int i = 0; i < n; ++i)
            if (i > 0 && ratings[i] > ratings[i - 1])
                left[i] = left[i - 1] + 1;
            else
                left[i] = 1;
        int right = 0, ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (i < n - 1 && ratings[i] > ratings[i + 1])
                ++right;
            else
                right = 1;
            ans += max(left[i], right);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int candy(vector<int>& ratings) {
        const int n = ratings.size();
        int ans = 1, inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; ++i)
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ans += pre;
                inc = pre;
            } else {
                ++dec;
                if (dec == inc) ++dec;
                ans += dec;
                pre = 1;
            }
        return ans;
    }
};
0%