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
18
19
20
21
22
23
class Solution {
public:
    int minCut(string s) {
        const int n = s.size();
        // if s[i~j] is palindrome.
        vector<vector<bool>> valid(n, vector<bool>(n, true));
        // dp[i] = min cuts of s[0~i].
        vector<int> dp(n, n);
        for (int l = 2; l <= n; ++l)
            for (int left = 0, right = left + l - 1; right < n; ++left, ++right)
                valid[left][right] = s[left] == s[right] && valid[left + 1][right - 1];
        for (int right = 0; right < n; ++right) {
            if (valid[0][right]) {
                dp[right] = 0;
                continue;
            }
            for (int left = 0; left < right; ++left)
                if (valid[left + 1][right])
                    dp[right] = min(dp[right], dp[left] + 1);
        }
        return dp[n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minCut(string s) {
        const int n = s.size();
        // dp[i] = min cuts of s[0~i].
        vector<int> dp(n, n);
        for (int m = 0; m < n; ++m) // enumerate middle points.
            for (int d = 0; d <= 1; ++d) // odd and even length palindrome.
                for (int i = m, j = m + d; i >= 0 && j < n && s[i] == s[j]; --i, ++j)
                    dp[j] = min(dp[j], (i ? (dp[i - 1] + 1) : 0));
        return dp[n - 1];
    }
};

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:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        function<void(int, vector<string>&)> dfs = [&](int pos, vector<string>& cur) {
            if (pos == s.size()) {
                ans.push_back(cur);
                return;
            }
            for (int i = pos; i < s.size(); ++i) {
                if (!isPalindrome(s, pos, i)) continue;
                cur.push_back(s.substr(pos, i - pos + 1));
                dfs(i + 1, cur);
                cur.pop_back();
            }
        };
        vector<string> cur;
        dfs(0, cur);
        return ans;
    }
private:
    bool isPalindrome(string s, int i, int j) {
        while (i < j)
            if (s[i++] != s[j--]) return false;
        return true;
    }
};
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
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;

        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        for (int right = 0; right < s.size(); ++right)
            for (int left = 0; left <= right; ++left)
                if (s[left] == s[right] && (right - left <= 2 || dp[left + 1][right - 1]))
                    dp[left][right] = true;

        function<void(int, vector<string>&)> dfs = [&](int pos, vector<string>& cur) {
            if (pos == s.size()) {
                ans.push_back(cur);
                return;
            }
            for (int i = pos; i < s.size(); ++i) {
                if (!dp[pos][i]) continue;
                cur.push_back(s.substr(pos, i - pos + 1));
                dfs(i + 1, cur);
                cur.pop_back();
            }
        };

        vector<string> cur;
        dfs(0, cur);
        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
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;

        vector<vector<int>> dp(s.size(), vector<int>(s.size()));
        function<int(int, int)> isPalindrome = [&](int left, int right) {
            if (dp[left][right]) // 0 unsearched, 1 is palindrome, -1 is not palindrome.
                return dp[left][right];
            if (left >= right)
                return dp[left][right] = 1;
            return dp[left][right] = (s[left] == s[right] ? isPalindrome(left + 1, right - 1) : -1);
        };

        function<void(int, vector<string>&)> dfs = [&](int pos, vector<string>& cur) {
            if (pos == s.size()) {
                ans.push_back(cur);
                return;
            }
            for (int i = pos; i < s.size(); ++i)
                if (isPalindrome(pos, i) == 1) {
                    cur.push_back(s.substr(pos, i - pos + 1));
                    dfs(i + 1, cur);
                    cur.pop_back();
                }
        };

        vector<string> cur;
        dfs(0, cur);
        return ans;
    }
};

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:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack<int> stk;
        vector<int> ans(n, -1);
        for (int i = 0; i < n * 2 - 1; ++i) {
            int idx = i % n;
            while (!stk.empty() && nums[stk.top()] < nums[idx]) {
                ans[stk.top()] = nums[idx];
                stk.pop();
            }
            stk.push(idx);
        }
        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
22
23
24
25
26
27
28
class MyQueue {
private:
    stack<int> inStack, outStack;
    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }
public:
    MyQueue() {}
    void push(int x) {
        inStack.push(x);
    }
    int pop() {
        if (outStack.empty()) in2out();
        int x = outStack.top();
        outStack.pop();
        return x;
    }
    int peek() {
        if (outStack.empty()) in2out();
        return outStack.top();
    }
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

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 lengthOfLIS(vector<int>& nums) {
        vector<int> dp{nums[0]};
        for (int i = 1; i < nums.size(); ++i) {
            int num = nums[i];
            if (num > dp.back()) {
                dp.emplace_back(num);
            } else {
                auto it = lower_bound(dp.begin(), dp.end(), num);
                *it = num;
            }
        }
        return dp.size();
    }
};

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 maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) return 0;
        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
        vector<int> dp{envelopes[0][1]};
        for (int i = 1; i < envelopes.size(); ++i) {
            int num = envelopes[i][1];
            if (num > dp.back()) {
                dp.emplace_back(num);
            } else {
                auto it = lower_bound(dp.begin(), dp.end(), num);
                *it = num;
            }
        }
        return dp.size();
    }
};

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 {
private:
    int countOnes(int n) {
        int ones = 0;
        while (n) {
            n &= (n - 1);
            ++ones;
        }
        return ones;
    }
public:
    vector<int> countBits(int num) {
        vector<int> ans(num + 1);
        for (int i = 0; i <= num; ++i)
            ans[i] = countOnes(i);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> dp(num + 1);
        int highBit = 0;
        for (int i = 1; i <= num; ++i) {
            if ((i & (i - 1)) == 0)
                highBit = i;
            dp[i] = dp[i - highBit] + 1;
        }
        return dp;
    }
};
1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> dp(num + 1);
        for (int i = 1; i <= num; ++i)
            dp[i] = dp[i >> 1] + (i & 1);
        return dp;
    }
};
1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> dp(num + 1);
        for (int i = 1; i <= num; ++i)
            dp[i] = dp[i & (i - 1)] + 1;
        return dp;
    }
};

Reference: 比特位计数 - 比特位计数 - 力扣（LeetCode）

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumMatrix {
private:
    vector<vector<int>> dp;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int R = matrix.size(); if (R == 0) return;
        int C = matrix[0].size(); if (C == 0) return;
        dp = vector<vector<int>>(R + 1, vector<int>(C + 1, 0));
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class NumArray {
private:
    vector<int> sums;
public:
    NumArray(vector<int>& nums) {
        int sum = 0;
        for (int num : nums)
            sums.emplace_back(sum += num);
    }
    int sumRange(int i, int j) {
        return i == 0 ? sums[j] : sums[j] - sums[i - 1];
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isMonotonic(vector<int> &A) {
        int n = A.size();
        bool inc = true, dec = true;
        for (int i = 0; i < n - 1; ++i) {
            if (A[i] > A[i + 1]) inc = false;
            if (A[i] < A[i + 1]) dec = false;
        }
        return inc || dec;
    }
};
0%