LeetCode 第131场双周赛个人题解

本文主要是介绍LeetCode 第131场双周赛个人题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

100309. 求出出现两次数字的 XOR 值

原题链接

求出出现两次数字的 XOR 值 - 力扣 (LeetCode) 竞赛

思路分析

签到题，一次遍历

AC代码

class Solution:def duplicateNumbersXOR(self, nums: List[int]) -> int:cnt = Counter(nums)res = 0st = set(nums)for x in st:if cnt[x] == 2:res ^= xreturn res

100303. 查询数组中元素的出现位置

原题链接

　　查询数组中元素的出现位置 - 力扣 (LeetCode) 竞赛

思路分析

　　记录下每个次数的位置，然后遍历一下查询就行

时间复杂度O(n)

AC代码

class Solution:def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:mp = defaultdict()s = 0for i, v in enumerate(nums):if v == x:s += 1mp[s] = ireturn [mp[v] if v in mp else -1 for v in queries]

100313. 所有球里面不同颜色的数目

原题链接

　　所有球里面不同颜色的数目 - 力扣 (LeetCode) 竞赛

思路分析

　　一开始敲了个莫队的板子，又看了下题看错题了。。。没那么复杂

边遍历边执行操作，边维护每个元素出现次数，然后记录下集合中的元素就行

时间复杂度O(n)

AC代码

class Solution:def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:cnt = Counter()mp = defaultdict(int)ret = []st = set()for x, y in queries:cnt[mp[x]] -= 1if cnt[mp[x]] == 0:st.remove(mp[x])mp[x] = ycnt[y] += 1st.add(y)ret.append(len(st))return ret

100314. 物块放置查询

原题链接

　　物块放置查询 - 力扣 (LeetCode) 竞赛

思路分析

　　思路就是线段树维护区间和，但是会卡常。

对原数轴重新编号

原数轴上的点i变为2 * i + 1，点与点之间的空隙也依次编号

然后空隙的权值为1，原数轴点的权值为0

在原数轴放障碍相当于将其赋值为负无穷

对于每个查询[0, x]等价于查询[1, 2 * x + 1]的最大连续子段和是否大于等于sz

我们只需要用线段树维护最大连续子段和即可

只涉及单点修改和区间查询，时间复杂度为O(nlogn)

---

由于拆点，区间长度为1e5量级，但是竟然被卡常了？

加个快读和吸氧才过

掉大分！！！

AC代码

#pragma GCC optimize(2)
const int N = 1e5 + 10;
#define lc p << 1
#define rc p << 1 | 1
struct node{int l, r;long long sum, lma, rma, ma;
}tr[N << 2];int n, m, a[N];void pushup(node& p, node& l, node& r){p.sum = l.sum + r.sum;p.lma = max(l.lma, l.sum + r.lma);p.rma = max(r.rma, r.sum + l.rma);p.ma = max(l.rma + r.lma, max(l.ma, r.ma));
}void build(int p, int l, int r){tr[p] = { l, r, 0, 0, 0, 0 };if(l == r){if (l % 2 == 0) tr[p] = { l, l, 1, 1, 1, 1 };return;}int mid = l + r >> 1;build(lc, l, mid), build(rc, mid + 1, r);pushup(tr[p], tr[lc], tr[rc]);
}node query(int p, int l, int r){if(l <= tr[p].l && tr[p].r <= r)return tr[p];int mid = tr[p].l + tr[p].r >> 1;if(r <= mid) return query(lc, l, r);else if(l > mid) return query(rc, l, r);node left = query(lc, l, r);node right = query(rc, l, r);node ret = { 0 };pushup(ret, left, right);return ret;
}void update(int p, int x, int k){ //点修if(tr[p].l == x && tr[p].r == x){tr[p] = { x, x, k, k, k, k };return;}int mid = tr[p].l + tr[p].r >> 1;if(x <= mid) update(lc, x, k);else update(rc, x, k);pushup(tr[p], tr[lc], tr[rc]);
}class Solution {
public:Solution() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);}vector<bool> getResults(vector<vector<int>>& queries) {memset(tr, 0, sizeof tr);build(1, 1, N);vector<bool> ret;for (auto& v : queries) {int op = v[0];if (op == 1) {update(1, v[1] * 2 + 1, -1e8);}else {auto t = query(1, 1, v[1] * 2 + 1);ret.push_back(t.ma >= v[2]);}}return ret;}
};

这篇关于LeetCode 第131场双周赛个人题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---