100323. 优质数对的总数 I

原题链接

100323. 优质数对的总数 I

思路分析

签到题

AC代码

class Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:n, m = len(nums1), len(nums2)ret = 0for i in range(n):for j in range(m):if nums1[i] % (nums2[j] * k) == 0:ret += 1return ret

100326. 压缩字符串 III

原题链接

100326. 压缩字符串 III

思路分析

一次遍历模拟即可

时间复杂度O(n)

AC代码

class Solution:def compressedString(self, word: str) -> str:n = len(word)i = 0ret = []while i < n:j = iwhile j < n and j - i < 9 and word[i] == word[j]:j += 1ret.append(str(j - i) + str(word[i]))i = jreturn "".join(ret)

100321. 优质数对的总数 II

原题链接

100321. 优质数对的总数 II

思路分析

用nums2 * k 得到的新数集合去给自己的倍数累加贡献，最后求和即可

时间复杂度就是经典的调和级数乘个n

时间复杂度：O()

AC代码

class Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:cnt1, cnt2 = Counter(), Counter([x * k for x in nums2])n = max(nums1)for x, c in cnt2.items():t = xwhile t <= n:cnt1[t] += ct += xreturn sum(cnt1[x] for x in nums1)

100306. 不包含相邻元素的子序列的最大和

原题链接

不包含相邻元素的子序列的最大和 - 力扣 (LeetCode) 竞赛

思路分析

和昨晚T4一样的套路。。

不过由于这里要求子序列不相邻，我们考虑维护四个值

ma 左右端点都不包含的最大子序列和

lma 左端点没限制，右端点不包含的最大子序列和

rma 右端点没限制，左端点一定不包含的最大子序列和

lrma 左右端点都没限制的最大子序列和

然后我们只需实现单点修改和递归建树

每次修改后，根节点的lrma即为答案

单点修改的逻辑见代码

时间复杂度O(nlogn)

AC代码

using i64 = long long;
const int N = 5e4 + 10, mod = 1e9 + 7;
struct node {int l, r;i64 ma, lma, rma, lrma;
} tr[N << 2];void pushup (node& t, node& l, node& r) {t.ma = max(l.rma + r.ma, l.ma + r.lma);t.lma = max(l.lma + r.lma, l.lrma + r.ma);t.rma = max(l.rma + r.rma, l.ma + r.lrma);t.lrma = max(l.lrma + r.rma, l.lma + r.lrma);
}
#define lc p << 1
#define rc p << 1 | 1
void build (int p, int l, int r, vector<int>& a) {tr[p] = { l, r };if (l == r) {tr[p] = { l, l, 0, 0, 0, max(a[l - 1], 0) };return;}int mid = l + r >> 1;build(lc, l, mid, a), build(rc, mid + 1, r, a);pushup(tr[p], tr[lc], tr[rc]);
}void update (int p, int x, int v) {if (tr[p].l == x && tr[p].r == x) {tr[p] = { x, x, 0, 0, 0, max(0, v) };return;}int mid = tr[p].l + tr[p].r >> 1;if (x <= mid) update(lc, x, v);else update(rc, x, v);pushup(tr[p], tr[lc], tr[rc]);
}#undef lc
#undef rcclass Solution {
public:int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();build(1, 1, n, nums);i64 res = 0;for (auto& v : queries) {update(1, v[0] + 1, v[1]);res = (res + tr[1].lrma) % mod;}return res;}
};