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 containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        const int n = nums.size();
        set<int> s;
        for (int i = 0; i < n; ++i) {
            // limit [nums[i] - t, nums[i] + t] within INT
            auto it = s.lower_bound(max(nums[i], INT_MIN + t) - t);
            if (it != s.end() && *it <= min(nums[i], INT_MAX - t) + t)
                return true;
            s.insert(nums[i]);
            if (i >= k)
                s.erase(nums[i - k]);
        }
        return false;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numDecodings(string s) {
        const int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] != '0')
                dp[i] += dp[i - 1];
            if (i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26))
                dp[i] += dp[i - 2];
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numDecodings(string s) {
        const int n = s.size();
        // a = dp[i - 2], b = dp[i - 1], c = dp[i]
        int a = 0, b = 1, c;
        for (int i = 1; i <= n; ++i) {
            c = 0;
            if (s[i - 1] != '0')
                c += b;
            if (i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26))
                c += a;
            tie(a, b) = {b, c};
        }
        return c;
    }
};

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 {
    unordered_map<int, int> m;
public:
    int combinationSum4(vector<int>& nums, int target) {
        if (target == 0) return 1;
        m[0] = 1;
        function<int(int)> dfs = [&](int target) {
            int ans = 0;
            for (const int& num : nums)
                if (target >= num) {
                    int t = target - num;
                    if (m.find(t) == m.end())
                        m[t] = dfs(t);
                    ans += m[t];
                }
            return ans;
        };
        return dfs(target);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        const int n = nums.size();
        vector<unsigned int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i)
            for (auto& num : nums)
                if (i >= num)
                    dp[i] += dp[i - num];
        return dp[target];
    }
};

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 Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        const int n = nums.size();
        sort(begin(nums), end(nums));
        vector<int> dp(n, 1);
        int maxVal = dp[0], maxSize = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j)
                if (nums[i] % nums[j] == 0)
                    dp[i] = max(dp[i], dp[j] + 1);
            if (dp[i] > maxSize) {
                maxSize = dp[i];
                maxVal = nums[i];
            }
        }
        if (maxSize == 1)
            return {nums[0]};
        vector<int> ans;
        for (int i = n - 1; maxSize > 0; --i)
            if (dp[i] == maxSize && maxVal % nums[i] == 0) {
                --maxSize;
                maxVal = nums[i];
                ans.emplace_back(nums[i]);
            }
        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
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        const int m = matrix.size(), n = matrix[0].size();
        int ans = INT_MIN;
        for (int i = 0; i < m; ++i) { // enumerate upper bound.
            vector<int> sum(n);
            for (int j = i; j < m; ++j) { // enumerate lower bound.
                for (int c = 0; c < n; ++c)
                    sum[c] += matrix[j][c]; // area sum of each column.
                // find the largest value that is
                // 1. smaller than k,
                // 2. from a continue subarray of `sum`.
                set<int> sumSet{0};
                int s = 0;
                for (int v : sum) {
                    s += v;
                    auto it = sumSet.lower_bound(s - k);
                    if (it != sumSet.end())
                        ans = max(ans, s - *it);
                    sumSet.insert(s);
                }
            }
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0, j = 0;
        for (int num : nums) {
            if (num != val)
                nums[i++] = num;
            ++j;
        }
        return i;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int n = nums.size(), mask = 0, target = (1 << maximumBit) - 1;
        vector<int> ans(n);
        for (int num : nums) {
            mask ^= num;
            ans[--n] = (mask ^ target);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
        int n = queries.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int x = queries[i][0], y = queries[i][1], r = queries[i][2];
            for (auto& point : points)
                if (pow(point[0] - x, 2) + pow(point[1] - y, 2) <= r * r)
                    ++ans[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 minOperations(vector<int>& nums) {
        int ans = 0, prev = INT_MIN;
        for (int num : nums) {
            if (num <= prev) {
                int next = prev + 1;
                ans += next - num;
                prev = next;
            } else {
                prev = num;   
            }
        }
        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
class Solution {
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        return max(rob(nums, 0, n - 1), rob(nums, 1, n));
    }
    int rob(vector<int>& nums, int start, int end) {
        int pre2 = nums[start], pre1 = max(nums[start], nums[start + 1]), tmp;
        for (int i = start + 2; i < end; ++i) {
            tmp = max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = tmp;
        }
        return max(pre1, pre2);
    }
};
0%