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:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size() + 1;
        int total = 0;
        for (int i = 1; i <= n; ++i)
            total ^= i;
        int odd = 0;
        for (int i = 1; i < n - 1; i += 2)
            odd ^= encoded[i];
        vector<int> perm(n);
        perm[0] = total ^ odd;
        for (int i = 1; i < n; ++i)
            perm[i] = perm[i - 1] ^ encoded[i - 1];
        return perm;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> seq1, seq2;
        dfs(root1, seq1);
        dfs(root2, seq2);
        return seq1 == seq2;
    }
    void dfs(TreeNode* root, vector<int>& seq) {
        if (root) {
            if (root->left == nullptr && root->right == nullptr) {
                seq.emplace_back(root->val);
            } else {
                dfs(root->left, seq);
                dfs(root->right, seq);
            }
        }
    }
};

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:
    int maxSumMinProduct(vector<int>& nums) {
        const int n = nums.size();
        vector<long long> sum(n + 1);
        for (int i = 0; i < n; ++i)
            sum[i + 1] = sum[i] + nums[i];
        vector<int> pre(n), next(n);
        pre[0] = -1;
        for (int i = 1; i < n; ++i) {
            int j = i - 1;
            while (j >= 0 && nums[j] >= nums[i])
                j = pre[j];
            pre[i] = j;
        }
        next[n - 1] = n;
        for (int i = n - 2; i >= 0; --i) {
            int j = i + 1;
            while (j < n && nums[j] >= nums[i])
                j = next[j];
            next[i] = j;
        }
        long long ans = 0;
        for (int i = 0; i < n; ++i)
            ans = max(ans, nums[i] * (sum[next[i]] - sum[pre[i] + 1]));
        return ans % static_cast<int> (1e9 + 7);
    }
};

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
class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        sort(jobs.begin(), jobs.end());
        int l = jobs[0], r = accumulate(jobs.begin(), jobs.end(), 0);
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(jobs, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
    bool check(vector<int>& jobs, int k, int limit) {
        vector<int> workloads(k);
        return backtrack(jobs, workloads, 0, limit);
    }
    bool backtrack(vector<int>& jobs, vector<int>& workloads, int idx, int limit){
        if (idx == jobs.size()) {
            return true;
        }
        int curr = jobs[idx];
        for (auto& workload : workloads) {
            workload += curr;
            if (workload <= limit && backtrack(jobs, workloads, idx + 1, limit)) {
                return true;
            }
            workload -= curr;
            if (workload == 0 || workload + curr == limit) {
                break;
            }
        }
        return false;
    }
};
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 minimumTimeRequired(vector<int>& jobs, int k) {
        int n = jobs.size(), sz = 1 << n;
        vector<int> sum(sz);
        for (int i = 1; i < sz; i++) {
            int x = __builtin_ctz(i), y = i - (1 << x);
            sum[i] = sum[y] + jobs[x];
        }
        vector<vector<int>> f(k, vector<int>(sz));
        f[0] = vector<int>(sum.begin(), sum.end());
        for (int i = 1; i < k; i++) {
            for (int j = 0; j < sz; j++) {
                int minn = INT_MAX;
                for (int x = j; x; x = (x - 1) & j) {
                    minn = min(minn, max(f[i - 1][j - x], sum[x]));
                }
                f[i][j] = minn;
            }
        }
        return f[k - 1][sz - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n = jobs.size(), sz = 1 << n;
        vector<int> s(sz);
        for (int i = 1; i < sz; ++i) {
            int x = __builtin_ctz(i), y = i - (1 << x);
            s[i] = s[y] + jobs[x];
        }
        vector<int> f(s.begin(), s.end());
        for (int i = 1; i < k; ++i) {
            for (int j = sz - 1; j >= 0; --j) {
                int minn = INT_MAX;
                for (int x = j; x; x = (x - 1) & j) {
                    minn = min(minn, max(f[j - x], s[x]));
                }
                f[j] = minn;
            }
        }
        return f[sz - 1];
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int xorOperation(int n, int start) {
        int pre = start, ans = start;
        for (int i = 1 ; i < n; ++i) {
            pre += 2;
            ans ^= pre;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int sumXor(int x) {
        if (x % 4 == 0) return x;
        if (x % 4 == 1) return 1;
        if (x % 4 == 2) return x + 1;
        return 0;
    }
    int xorOperation(int n, int start) {
        int s = start >> 1, e = n & start & 1;
        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ret << 1 | e;
    }
};

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:
    int deleteAndEarn(vector<int>& nums) {
        const int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> dp;
        sort(nums.begin(), nums.end());
        int i = 0, j, curr;
        while (i < n) {
            curr = nums[i];
            j = i + 1;
            while (j < n && nums[i] == nums[j])
                ++j;
            int curr = (j - i) * nums[i];
            if (!dp.empty()) {
                if (nums[i] != nums[i - 1] + 1)
                    curr += dp.back();
                else if (dp.size() == 1)
                    curr = max(dp.back(), curr);
                else
                    curr = max(dp.back(), curr + dp[dp.size() - 2]);
            }
            dp.emplace_back(curr);
            i = j;
        }
        return dp.back();
    }
};
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
class Solution {
private:
    int rob(vector<int> &nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int a = nums[0], b = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            int temp = b;
            b = max(a + nums[i], b);
            a = temp;
        }
        return b;
    }
public:
    int deleteAndEarn(vector<int> &nums) {
        int n = nums.size(), ans = 0;
        sort(nums.begin(), nums.end());
        vector<int> sum = {nums[0]};
        for (int i = 1; i < n; ++i) {
            int val = nums[i];
            if (val == nums[i - 1]) {
                sum.back() += val;
            } else if (val == nums[i - 1] + 1) {
                sum.push_back(val);
            } else {
                ans += rob(sum);
                sum = {val};
            }
        }
        ans += rob(sum);
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        const int n = encoded.size();
        vector<int> ans(n + 1);
        ans[0] = first;
        for (int i = 0; i < n; ++i) {
            ans[i + 1] = ans[i] ^ encoded[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 reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < INT_MIN / 10 || rev > INT_MAX / 10)
                return 0;
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int h[10], t, cnt = 0;
int main() {
    for (int i = 0; i < 10; ++i)
        cin >> h[i];
    cin >> t;
    t += 30;
    for (int i = 0; i < 10; ++i)
        if (h[i] <= t)
            ++cnt;
    cout << cnt << endl;
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int l, m, u, v, tree[10001] = {0}, cnt = 0;
int main() {
    cin >> l >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v;
        while (u <= v)
            tree[u++] = 1;
    }
    for (int i = 0; i <= l; ++i)
        if (tree[i] == 0)
            ++cnt;
    cout << cnt << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int l, m, cnt = 0;
int main() {
    cin >> l >> m;
    vector<vector<int>> v(m, vector<int>(2));
    for (int i = 0; i < m; ++i)
        cin >> v[i][0] >> v[i][1];
    sort(begin(v), end(v));
    int i = 0, j = 0;
    while (j < m) {
        if (i <= v[j][1]) {
            i = max(i, v[j][0]);
            cnt += v[j][1] - i + 1;
            i = v[j][1] + 1;
        }
        ++j;
    }
    cout << l + 1 - cnt << endl;
    return 0;
}
0%