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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
int T;
int n;
int a[N];
int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        sort(a, a + n, greater<int>());
        for (int i = 0; i < n; ++i) cout << a[i] << " ";
        cout << endl;
    }
    return 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:
    string largestNumber(vector<int>& cost, int target) {
        vector<int> f(target + 1, INT_MIN);
        f[0] = 0;
        for (auto c : cost)
            for (auto j = c; j <= target; ++j)
                f[j] = max(f[j], f[j - c] + 1);
        if (f[target] < 0) return "0";
        string ans;
        for (int i = 8, j = target; i >= 0; --i)
            for (int c = cost[i]; j >= c && f[j] == f[j - c] + 1; j -= c)
                ans += '1' + i;
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int guessNumber(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            int ans = guess(mid);
            if (ans == -1) r = mid - 1;
            else if (ans == 1) l = mid + 1;
            else return mid;
        }
        return r;
    }
};

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
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int minOperationsToFlip(string expression) {
        vector<pair<int, int>> stack_num;
        vector<int> stack_op;
        auto op_and = [](int x1, int y1, int x2, int y2) -> pair<int, int> {
            return {min({x1 + x2, x1 + y2, x2 + y1}), y1 + y2};
        };
        auto op_or = [](int x1, int y1, int x2, int y2) -> pair<int, int> {
            return {x1 + x2, min({x1 + y2, x2 + y1, x2 + y1, y1 + y2})};
        };
        auto calc = [&]() {
            if (stack_num.size() >= 2 && (stack_op.back() == '|' || stack_op.back() == '&')) {
                auto [x1, y1] = stack_num.back(); stack_num.pop_back();
                auto [x2, y2] = stack_num.back(); stack_num.pop_back();
                auto [x_and, y_and] = op_and(x1, y1, x2, y2);
                auto [x_or, y_or] = op_or(x1, y1, x2, y2);
                if (stack_op.back() == '&') {
                    stack_num.emplace_back(min(x_and, x_or + 1), min(y_and, y_or + 1));
                } else {
                    stack_num.emplace_back(min(x_or, x_and + 1), min(y_or, y_and + 1));
                }
                stack_op.pop_back();
            }
        };
        for (char c : expression) {
            if (c == '(' || c == '|' || c == '&') {
                stack_op.push_back(c);
            } else if (c == '0') {
                stack_num.emplace_back(0, 1);
                calc();
            } else if (c == '1') {
                stack_num.emplace_back(1, 0);
                calc();
            } else {
                assert(c == ')');
                stack_op.pop_back();
                calc();
            }
        }
        return max(stack_num[0].first, stack_num[0].second);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int firstBadVersion(int n) {  
        int l = 1, r = n;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        int x = target[0], y = target[1], z = target[2], a = 1, b = 1, c = 1;
        for (auto& t : triplets)
            if (t[0] <= x && t[1] <= y && t[2] <= z)
                a = max(a, t[0]), b = max(b, t[1]), c = max(c, t[2]);
        return a == x && b == y && c == z;
    }
};

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
const int N = 100000;
bool st[N];
class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        auto check = [&](int mid) {
            for (int i = 0; i < s.size(); ++i) st[i] = false;
            for (int i = 0; i < mid; ++i) st[removable[i]] = true;
            int i = 0, j = 0;
            while (i < s.size() && j < p.size()) {
                if (st[i]) {
                    ++i;
                    continue;
                }
                if (s[i] == p[j]) ++j;
                ++i;
            }
            return j == p.size();
        };
        int l = 0, r = removable.size();
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
};

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 makeEqual(vector<string>& words) {
        const int n = words.size();
        if (n == 1) return true;
        vector<int> cnt(26);
        for (auto& w : words) {
            for (auto c : w) {
                ++cnt[c - 'a'];
            }
        }
        for (int i = 0; i <= 25; ++i)
            if (cnt[i] && cnt[i] % n)
                return false;
        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
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    using LL = long long;
public:
    bool check(vector<vector<int>>& g, int a, int b, int c, int d) {
        LL sum = 0;
        for (int i = a; i <= c; ++i) {
            LL s = 0;
            for (int j = b; j <= d; ++j) s += g[i][j];
            if (sum && sum != s) return false;
            sum = s;
        }
        for (int i = b; i <= d; ++i) {
            LL s = 0;
            for (int j = a; j <= c; ++j) s += g[j][i];
            if (sum != s) return false;
        }
        LL s = 0;
        for (int i = a, j = b; i <= c; ++i, ++j)
            s += g[i][j];
        if (s != sum) return false;
        s = 0;
        for (int i = a, j = d; i <= c; ++i, --j)
            s+= g[i][j];
        return s == sum;
    }
    int largestMagicSquare(vector<vector<int>>& g) {
        const int n = g.size(), m = g[0].size();
        for (int k = min(n, m); k >= 2; --k) {
            for (int i = 0 ; i + k - 1 < n; ++i) {
                for (int j = 0; j + k - 1 < m; ++j) {
                    if (check(g, i, j, i + k - 1, j + k - 1))
                        return k;
                }
            }
        }
        return 1;
    }
};
0%