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:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> m;
        for (const auto& word : words)
            ++m[word];
        auto cmp = [&](const auto& a, const auto& b) {
            return a.first > b.first || (a.first == b.first && a.second < b.second);
        };
        priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(cmp)> q(cmp);
        for (const auto& [word, freq] : m) {
            q.emplace(freq, word);
            if (q.size() > k)
                q.pop();
        }
        vector<string> ans(k);
        for (int i = k - 1; i >= 0; --i) {
            ans[i] = q.top().second;
            q.pop();
        }
        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 countTriplets(vector<int>& arr) {
        const int n = arr.size();
        vector<int> dp(n + 1);
        for (int i = 0; i < n; ++i)
            dp[i + 1] = dp[i] ^ arr[i];
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                for (int k = j; k < n; ++k)
                    if (dp[i] == dp[k + 1])
                        ++ans;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        const int n = arr.size();
        vector<int> dp(n + 1);
        for (int i = 0; i < n; ++i)
            dp[i + 1] = dp[i] ^ arr[i];
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int k = i + 1; k < n; ++k)
                if (dp[i] == dp[k + 1])
                    ans += k - i;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        const int n = arr.size();
        vector<int> dp(n + 1);
        for (int i = 0; i < n; ++i)
            dp[i + 1] = dp[i] ^ arr[i];
        int ans = 0;
        unordered_map<int, int> freq, sum;
        for (int i = 0; i < n; ++i) {
            if (freq.find(dp[i + 1]) != freq.end())
                ans += freq[dp[i + 1]] * i - sum[dp[i + 1]];
            ++freq[dp[i]];
            sum[dp[i]] += i;
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        const int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        vector<int> ans;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                ans.emplace_back(dp[i][j] = matrix[i - 1][j - 1] ^ dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1]);
        sort(ans.begin(), ans.end(), greater<int>());
        return ans[k - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        const int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        vector<int> ans;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                ans.emplace_back(dp[i][j] = matrix[i - 1][j - 1] ^ dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1]);
        nth_element(ans.begin(), ans.begin() + k - 1, ans.end(), greater<int>());
        return ans[k - 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
28
29
30
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        this->x = x;
        this->y = y;
        preorder(root, nullptr, y);
        return prex != prey && dx == dy;
    }
private:
    int dx = -1;
    int dy = -1;
    int x;
    int y;
    TreeNode* prex;
    TreeNode* prey;
    void preorder(TreeNode* root, TreeNode* pre, int d) {
        if (root == nullptr) return;
        if (root->val == x) {
            prex = pre;
            dx = d;
        }
        if (root->val == y) {
            prey = pre;
            dy = d;
        }
        if (dx != -1 && dy != -1) return;
        preorder(root->left, root, d + 1);
        preorder(root->right, root, d + 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
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int ans = 0;
        for (int i = 30; i >= 0; --i) {
            unordered_set<int> seen;
            for (auto num : nums)
                seen.insert(num >> i);
            int next = (ans << 1) + 1;
            bool found = false;
            for (auto num : nums)
                if (seen.find(next ^ (num >> i)) != seen.end()) {
                    found = true;
                    break;
                }
            ans = found ? next : next - 1;
        }
        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
class Solution {
public:
    const int MOD = 1000000007;
    using LL = long long;
    int sumOfFlooredPairs(vector<int>& nums) {
        int upper = *max_element(nums.begin(), nums.end());
        vector<int> s(upper + 1);
        for (int x: nums) {
            ++s[x];
        }
        vector<int> pre(upper + 1);
        for (int i = 1; i <= upper; ++i) {
            s[i] += s[i - 1];
        }
        LL ans = 0;
        for (auto i : nums) {
            for (int j = 1; j * i <= upper; ++j) {
                int l = j * i, r = min((j + 1) * i - 1, upper);
                int sum = (LL) (s[r] - s[l - 1]) * j % MOD;
                ans = (ans + (LL) sum) % MOD;
            }
        }
        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
class Solution {
unordered_map<char, int> m = {
    {'I', 1},
    {'V', 5},
    {'X', 10},
    {'L', 50},
    {'C', 100},
    {'D', 500},
    {'M', 1000},
};
public:
    int romanToInt(string s) {
        const int n = s.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int v = m[s[i]];
            if (i < n - 1 && v < m[s[i + 1]]) ans -= v;
            else ans += v;
        }
        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
29
30
const pair<int, string> M[] = {
    {1000, "M"},
    {900, "CM"},
    {500, "D"},
    {400, "CD"},
    {100, "C"},
    {90, "XC"},
    {50, "L"},
    {40, "XL"},
    {10, "X"},
    {9, "IX"},
    {5, "V"},
    {4, "IV"},
    {1, "I"},
};
class Solution {
public:
    string intToRoman(int num) {
        string ans;
        for (const auto& [v, s] : M) {
            while (num >= v) {
                num -= v;
                ans += s;
            }
            if (num == 0)
                break;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
const string M[] = {"", "M", "MM", "MMM"};
const string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
const string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
const string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
class Solution {
public:
    string intToRoman(int num) {
        return M[num / 1000] + C[num % 1000 / 100] + X[num % 100 / 10] + I[num % 10];
    }
};

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 numWays(int steps, int arrLen) {
        const int MOD = 1000000007;
        int maxCol = min(steps / 2 + 1, arrLen);
        vector<vector<int>> dp(steps + 1, vector<int>(maxCol));
        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++i) {
            for (int j = 0; j < maxCol; ++j) {
                int &x = dp[i][j];
                x = dp[i - 1][j];
                if (j)
                    x = (x + dp[i - 1][j - 1]) % MOD;
                if (j < maxCol - 1)
                    x = (x + dp[i - 1][j + 1]) % MOD;
            }
        }
        return dp[steps][0]; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int MOD = 1000000007;
        int maxCol = min(steps / 2 + 1, arrLen);
        vector<vector<int>> dp(2, vector<int>(maxCol));
        int curr = 0, next;
        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++i) {
            next = 1 - curr;
            for (int j = 0; j < maxCol; ++j) {
                int &x = dp[next][j];
                x = dp[curr][j];
                if (j)
                    x = (x + dp[curr][j - 1]) % MOD;
                if (j < maxCol - 1)
                    x = (x + dp[curr][j + 1]) % MOD;
            }
            curr = next;
        }
        return dp[curr][0]; 
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        const int n = arr.size();
        vector<int> prefix(n + 1);
        int i = -1;
        while (++i < n) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        vector<int> ans(queries.size());
        i = 0;
        for (auto& q : queries)
            ans[i++] = prefix[q[1] + 1] ^ prefix[q[0]];
        return ans;
    }
};
0%