自学内容网 自学内容网
自学内容网 > 正文

LeetCode 第419场周赛个人题解

🕗 发布于 2024-10-14 14:37 leetcode  算法  职场和发展  

3318. 计算子数组的 x-sum I

原题链接

3318. 计算子数组的 x-sum I

思路分析

见Q4

AC代码

using i64 = long long;
constexpr int N = 2E5 + 2;
constexpr int inf32 = 1E9 + 7;

struct Tree{
    std::pair<int, int> val;
    i64 sum = 0;
    int sz = 1;
    Tree *ch[2] = {nullptr, nullptr}, *p = nullptr;
    Tree(int val = 0, int cnt = 0) {
        this->val = {cnt, val};
        sum = 1LL * val * cnt;
    }
}pool[N];

int tot = 0;

Tree *newNode(int val = 0, int cnt = 0) {
    Tree *res = &pool[tot ++];
    *res = Tree(val, cnt);
    return res;
}

int pos(Tree *t) {
    return t->p->ch[1] == t;
}

int size(Tree *t) {
    return t ? t->sz : 0;
}

i64 sum(Tree *t) {
    return t ? t->sum : 0;
}

void pull(Tree *t) {
    assert(t);
    t->sz = size(t->ch[0]) + size(t->ch[1]) + 1;
    t->sum = sum(t->ch[0]) + sum(t->ch[1]) + 1LL * t->val.second * t->val.first;
}

void rotate(Tree *t) {
    Tree *q = t->p;
    int x = !pos(t);
    q->ch[!x] = t->ch[x];
    if (t->ch[x]) t->ch[x]->p = q;
    t->p = q->p;
    if (q->p) q->p->ch[pos(q)] = t;
    t->ch[x] = q;
    q->p = t;
    pull(q);
    pull(t);
}

void splay(Tree *&root, Tree *x, Tree *k) {
    while (x->p != k) {
        Tree *y = x->p, *z = y->p;
        if (z != k)
            pos(y) ^ pos(x) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (!k) root = x;
}

void insert(Tree *&root, Tree *v) {
    if (!root) {
        // assert(false);  // 永远不会走这个逻辑
        root = v;
        return;
    }
    Tree *x = root, *p = nullptr;
    while (x) {
        p = x;
        x = x->ch[x->val < v->val];
    }
    p->ch[p->val < v->val] = v;
    v->p = p;
    splay(root, v, nullptr);
}

void getv(Tree *&root, const std::pair<int, int> &val) {
    Tree *res = nullptr, *t = root;
    while (t) {
        if (t->val >= val) res = t, t = t->ch[0];
        else t = t->ch[1];
    }
    splay(root, res, nullptr);
}

Tree *findpre(Tree *&root, const std::pair<int, int> &val) {
    getv(root, val);
    if (root->val < val) return root;
    Tree *t = root->ch[0];
    while (t->ch[1])
        t = t->ch[1];
    return t;
}

Tree *findNext(Tree *&root, const std::pair<int, int> &val) {
    getv(root, val);
    if (root->val > val) return root;
    Tree *t = root->ch[1];
    while (t->ch[0])
        t = t->ch[0];
    return t;
}

void erase(Tree *&root, const std::pair<int, int> &val) {
    Tree *l = findpre(root, val);
    Tree *r = findNext(root, val);
    splay(root, l, nullptr), splay(root, r, l);
    r->ch[0] = nullptr;
    pull(r), pull(l);
}

Tree *findKth(Tree *t, int k) {
    while (true) {
        if (size(t->ch[0]) >= k)
            t = t->ch[0];
        else if(size(t->ch[0]) + 1 < k)
            k -= size(t->ch[0]) + 1, t = t->ch[1];
        else
            return t;
    }
}

void dfs(Tree *t) {
    if (!t) return;
    dfs(t->ch[0]);
    std::cout << t->val.first << ':' << t->val.second << ' ';;
    dfs(t->ch[1]);
}

class Solution {
public:
    std::vector<int> findXSum(std::vector<int>& nums, int k, int x) {
        int n = nums.size();
        tot = 0;
        Tree *L = newNode(0, -inf32), *R = newNode(0, inf32);
        Tree *root = L;
        insert(root, R);

        std::vector<int> res;
        std::unordered_map<int, int> cnt;

        for (int i = 0; i < n; ++ i) {
            if (cnt[nums[i]]) {
                erase(root, std::pair(cnt[nums[i]], nums[i]));
            }
            insert(root, newNode(nums[i], ++ cnt[nums[i]]));
            if (i >= k) {
                erase(root, std::pair(cnt[nums[i - k]] --, nums[i - k]));
            
            if (cnt[nums[i - k]]) {
                insert(root, newNode(nums[i - k], cnt[nums[i - k]]));
            }
            }
            if (i + 1 >= k) {
                if (size(root) <= x + 2) {
                    res.push_back(sum(root));
                }
                else {
                    auto it = findKth(root, size(root) - x - 1);
                    splay(root, L, nullptr);
                    splay(root, it, nullptr);
                    res.push_back(sum(root->ch[1]));
                }
            }
        }
        return res;
    }
};

3319. 第 K 大的完美二叉子树的大小

原题链接

3319. 第 K 大的完美二叉子树的大小

思路分析

dfs入门题

显然答案就是最大满二叉子树树的size，这个直接深搜即可

时间复杂度：O(N)

AC代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthLargestPerfectSubtree(self, root: Optional[TreeNode], k: int) -> int:
        ans = []
        def dfs(t: Optional[TreeNode])->int:
            if not t: return 0
            L, R = dfs(t.left), dfs(t.right)
            if L < 0 or L != R: return -1
            ans.append(L + 1)
            return L + 1

        dfs(root)
        if len(ans) < k: return -1
        ans.sort()
        return (1 << ans[-k]) - 1

3320. 统计能获胜的出招序列数

原题链接

3320. 统计能获胜的出招序列数

思路分析

记忆化搜索+可行性剪枝

我们考虑 dfs(i, j, last) 为 到 下标 i 位置，分差为j，Bob在上一个位置出的是last 的 方案数

那么我们枚举 下标 i 位置Bob出的字符，就能根据last 和 s[i] 算出下一个位置的分数，然后加法原理即可

时间复杂度：O(N^2)

AC代码

P = 1_000_000_007
class Solution:
    def countWinningSequences(self, s: str) -> int:
        @cache
        def dfs(i: int, j: int, last: str) -> int:
            if i == len(s):
                return 1 if j > 0 else 0
            if len(s) - i + j < 0: return 0
            res = 0
            for c in 'FWE':
                if c == last: continue
                if c == s[i]:
                    res += dfs(i + 1, j, c)
                elif c == 'F':
                    if s[i] == 'E':
                        res += dfs(i + 1, j + 1, c)
                    elif s[i] == 'W':
                        res += dfs(i + 1, j - 1, c)
                elif c == 'W':
                    if s[i] == 'E':
                        res += dfs(i + 1, j - 1, c)
                    elif s[i] == 'F':
                        res += dfs(i + 1, j + 1, c)
                elif c == 'E':
                    if s[i] == 'F':
                        res += dfs(i + 1, j - 1, c)
                    elif s[i] == 'W':
                        res += dfs(i + 1, j + 1, c)
                if res >= P: res -= P
            return res
        dfs.cache_clear()
        return dfs(0, 0, '#')

3321. 计算子数组的 x-sum II

原题链接

3321. 计算子数组的 x-sum II

思路分析

平衡树 + 模拟 + 滑窗

显然要维护一个长度为k的滑窗，但是滑窗内的信息用什么数据结构来维护呢？

考虑用 平衡树 维护 键值对 <cnt, val>，代表 窗口内的 val 出现了 cnt次，节点除了键值对外还要维护 子树和：Σ cnt * val

注意平衡树内插入了 极小值极大值两个哨兵

对于 每个 ans，我们查询 第 size(root) - x - 1 大 的节点it，然后将 极小值Splay 到根，itSplay到根节点的右儿子，那么 答案就是 sum(root->ch[1])

时间复杂度：O(NlogN)

AC代码

using i64 = long long;
constexpr int N = 2E5 + 2;
constexpr int inf32 = 1E9 + 7;

struct Tree{
    std::pair<int, int> val;
    i64 sum = 0;
    int sz = 1;
    Tree *ch[2] = {nullptr, nullptr}, *p = nullptr;
    Tree(int val = 0, int cnt = 0) {
        this->val = {cnt, val};
        sum = 1LL * val * cnt;
    }
}pool[N];

int tot = 0;

Tree *newNode(int val = 0, int cnt = 0) {
    Tree *res = &pool[tot ++];
    *res = Tree(val, cnt);
    return res;
}

int pos(Tree *t) {
    return t->p->ch[1] == t;
}

int size(Tree *t) {
    return t ? t->sz : 0;
}

i64 sum(Tree *t) {
    return t ? t->sum : 0;
}

void pull(Tree *t) {
    assert(t);
    t->sz = size(t->ch[0]) + size(t->ch[1]) + 1;
    t->sum = sum(t->ch[0]) + sum(t->ch[1]) + 1LL * t->val.second * t->val.first;
}

void rotate(Tree *t) {
    Tree *q = t->p;
    int x = !pos(t);
    q->ch[!x] = t->ch[x];
    if (t->ch[x]) t->ch[x]->p = q;
    t->p = q->p;
    if (q->p) q->p->ch[pos(q)] = t;
    t->ch[x] = q;
    q->p = t;
    pull(q);
    pull(t);
}

void splay(Tree *&root, Tree *x, Tree *k) {
    while (x->p != k) {
        Tree *y = x->p, *z = y->p;
        if (z != k)
            pos(y) ^ pos(x) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (!k) root = x;
}

void insert(Tree *&root, Tree *v) {
    if (!root) {
        // assert(false);  // 永远不会走这个逻辑
        root = v;
        return;
    }
    Tree *x = root, *p = nullptr;
    while (x) {
        p = x;
        x = x->ch[x->val < v->val];
    }
    p->ch[p->val < v->val] = v;
    v->p = p;
    splay(root, v, nullptr);
}

void getv(Tree *&root, const std::pair<int, int> &val) {
    Tree *res = nullptr, *t = root;
    while (t) {
        if (t->val >= val) res = t, t = t->ch[0];
        else t = t->ch[1];
    }
    splay(root, res, nullptr);
}

Tree *findpre(Tree *&root, const std::pair<int, int> &val) {
    getv(root, val);
    if (root->val < val) return root;
    Tree *t = root->ch[0];
    while (t->ch[1])
        t = t->ch[1];
    return t;
}

Tree *findNext(Tree *&root, const std::pair<int, int> &val) {
    getv(root, val);
    if (root->val > val) return root;
    Tree *t = root->ch[1];
    while (t->ch[0])
        t = t->ch[0];
    return t;
}

void erase(Tree *&root, const std::pair<int, int> &val) {
    Tree *l = findpre(root, val);
    Tree *r = findNext(root, val);
    splay(root, l, nullptr), splay(root, r, l);
    r->ch[0] = nullptr;
    pull(r), pull(l);
}

Tree *findKth(Tree *t, int k) {
    while (true) {
        if (size(t->ch[0]) >= k)
            t = t->ch[0];
        else if(size(t->ch[0]) + 1 < k)
            k -= size(t->ch[0]) + 1, t = t->ch[1];
        else
            return t;
    }
}

void dfs(Tree *t) {
    if (!t) return;
    dfs(t->ch[0]);
    std::cout << t->val.first << ':' << t->val.second << ' ';;
    dfs(t->ch[1]);
}

class Solution {
public:
    std::vector<i64> findXSum(std::vector<int>& nums, int k, int x) {
        int n = nums.size();
        tot = 0;
        Tree *L = newNode(0, -inf32), *R = newNode(0, inf32);
        Tree *root = L;
        insert(root, R);

        std::vector<i64> res;
        std::unordered_map<int, int> cnt;

        for (int i = 0; i < n; ++ i) {
            if (cnt[nums[i]]) {
                erase(root, std::pair(cnt[nums[i]], nums[i]));
            }
            insert(root, newNode(nums[i], ++ cnt[nums[i]]));
            if (i >= k) {
                erase(root, std::pair(cnt[nums[i - k]] --, nums[i - k]));
            
            if (cnt[nums[i - k]]) {
                insert(root, newNode(nums[i - k], cnt[nums[i - k]]));
            }
            }
            if (i + 1 >= k) {
                if (size(root) <= x + 2) {
                    res.push_back(sum(root));
                }
                else {
                    auto it = findKth(root, size(root) - x - 1);
                    splay(root, L, nullptr);
                    splay(root, it, nullptr);
                    res.push_back(sum(root->ch[1]));
                }
            }
        }
        return res;
    }
};


原文地址：https://blog.csdn.net/EQUINOX1/article/details/142898372

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024