LeetCode 第399场周赛个人题解

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(n ln n)

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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/331914.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

千亿级开源大模型Qwen110B部署实测

近日&#xff0c;通义千问团队震撼开源 Qwen1.5 系列首个千亿参数模型 Qwen1.5-110B-Chat。 千亿级大模型普通显卡是跑不了推理的&#xff0c;普通人一般也没办法本地运行千亿级大模型。 为了探索千亿级大模型到底需要计算资源&#xff0c;我用云计算资源部署了Qwen1.5-110B-…

Leetcode 剑指 Offer II 079.子集

题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer&#xff08;专项突击版&#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述 给定一个整数数组 nums &#xff0c;数组中的元素 互不相同 。返…

20232801 2023-2024-2 《网络攻防实践》实践十一报告

#20232801 2023-2024-2 《网络攻防实践》实践十一报告 1.实践内容 &#xff08;1&#xff09;web浏览器渗透攻击 使用攻击机和Windows靶机进行浏览器渗透攻击实验&#xff0c;体验网页木马构造及实施浏览器攻击的实际过程。 &#xff08;2&#xff09;取证分析实践—网页木马…

北核论文完美复现:自适应t分布与动态边界策略改进的算术优化算法

声明&#xff1a;文章是从本人公众号中复制而来&#xff0c;因此&#xff0c;想最新最快了解各类智能优化算法及其改进的朋友&#xff0c;可关注我的公众号&#xff1a;强盛机器学习&#xff0c;不定期会有很多免费代码分享~ 目录 原始算术优化算法 改进点1&#xff1a;引入…

那智不二越机器人维修案例分享

那智不二越工业机器人在工业范围内广泛应用于各种生产领域。其示教器作为人机交互的重要设备&#xff0c;常常需要定期维护和Nachi不二越机械手示教盒修理。 【Nachi不二越机器人示教器维修步骤】 1. 关闭电源 在进行任何那智不二越机器人维修操作之前&#xff0c;务必确保机器…

IDEA打开项目报错

IDEA打开项目报错&#xff1a; Cannot read scheme C:\Users\xxxxxx\AppData\Roaming\JetBrains\IntelliJIdea2023.2\qaplug_profiles\Default.xmljava.lang.AbstractMethodError: Receiver class com.soldevelo.qaplug.scanner.AnalysisProfileManager$2 does not define or i…

单条16g和双条8g哪个好

单条16g和双条8g各有优劣,具体选择要根据个人需求和电脑配置来决定。 以下是一些参考信息: •单条16g内存的价格比双条8g内存的价格低,而且16g的内存容量大,一条内存十分的方便。 •两条8g内存可以组成双通道,电脑运行速度要快一些。 •对于普通使用电脑的人群与热衷于…

项目管理-人力资源管理

目录 一、概述 二、人力资源计划编制 2.1 概述 2.2 层次结构图 2.3 分配任务矩阵 三、组建项目团队 3.1 概述 3.2 内部谈判 3.3 事先分派 3.4 外部招聘 3.5 虚拟团队 3.6 总结 四、项目团队建设 4.1 概述 4.2 团队发展过程 4.2.1 概述 4.2.2 形成期 4.2.3 震…

vue3 ts问题 找不到模块“@/views/home/index.vue”或其相应的类型声明。

1. 找不到模块“/views/HomeView.vue”或其相应的类型声明 今天帮同事看了一个问题&#xff0c;他尝试用vitevue3tspinia创建项目&#xff0c;结果刚上来就遇到这么一个问题 2. 解决办法 出现这个问题的原因就是&#xff1a;ts只支持导出导入模块&#xff0c;但是vue不是模块…

红蓝对抗-HW红蓝队基本知识(网络安全学习路线笔记)

第一, 什么是蓝队 蓝队&#xff0c;一般是指网络实战攻防演习中的攻击一方。 蓝队一般会采用针对目标单位的从业人员&#xff0c;以及目标系统所在网络内的软件、硬件设备同时执行多角度、全方位、对抗性的混合式模拟攻击手段&#xff1b;通过技术手段实现系统提权、控制业务、…

利用Python去除PDF水印

摘要 本文介绍了如何使用 Python 中的 PyMuPDF 和 OpenCV 库来从 PDF 文件中移除水印&#xff0c;并将每个页面保存为图像文件的方法。我们将深入探讨代码背后的工作原理&#xff0c;并提供一个简单的使用示例。 导言 简介&#xff1a;水印在许多 PDF 文件中都很常见&#x…

自建公式,VBA在Excel中轻松获取反义词

自建公式&#xff0c;VBA在Excel中轻松获取反义词 文章目录 前言一、爬取网站数据二、代码1.创建数据发送及返回方法2.汉字转UTF8编码2.获取反义词 三、运行效果截图 前言 小学语文中&#xff0c;近义词、反义词是必考内容之一。家长不能随时辅导怎么办&#xff1f;有VBA&…

脚注:书籍的小秘密,躲藏在脚注间

脚注&#xff1a;书籍的小秘密&#xff0c;躲藏在脚注间 脚注是一种在文本中提供补充信息、引用出处或注解的方式&#xff0c;有助于读者更全面地理解文中内容&#xff0c;并为进一步研究提供参考和跳转点。 在一书本中&#xff0c;脚注是额外提供给读者的文字信息&#xff0…

自动化您的任务——crewAI 初学者教程

今天&#xff0c;我写这篇文章是为了分享您开始使用一个非常流行的多智能体框架所需了解的所有信息&#xff1a;crewAI。 我将在这里或那里跳过一些内容&#xff0c;使本教程成为一个精炼的教程&#xff0c;概述帮助您入门的关键概念和要点 今天&#xff0c;我写这篇文章是为了…

RedHat9 | DNS剖析-配置主DNS服务器实例

一、实验环境 1、BIND软件包介绍 BIND软件是一款开放源码的DNS服务器软件&#xff0c;由美国加州大学Berkeley分校开发和维护&#xff0c;全称为Berkeley Internet Name Domain。该软件在DNS&#xff08;域名系统&#xff09;领域具有重要地位&#xff0c;是目前世界上使用最…

[数组查找]1.图解线性查找及其代码实现

线性查找 线性查找是一种在数组中查找数据的算法。与二分查找不同&#xff0c;即便数据没有按顺序存储&#xff0c;也可以应用线性查找。线性查找的操作很简单&#xff0c;只要在数组中从头开始依次往下查找即可。虽然存储的数据类型没有限制&#xff0c;但为了便于理解&#x…

stm32学习-流水灯

接线 注意&#xff1a;LED灯长一点的引脚是正极。 配置GPIO 1.使用RCC开启GPIO时钟 void RCC_AHBPeriphClockCmd(uint32_t RCC_AHBPeriph, FunctionalState NewState); void RCC_APB2PeriphClockCmd(uint32_t RCC_APB2Periph, FunctionalState NewState); void RCC_APB1Perip…

【credit_based流控机制】

credit_based流控机制 1 credit_based way1.1 Principle1.3 DFD1.4 Module1.4.1 Interface1.4.2 Code Block 在网络芯片处理大流量报文中&#xff0c;一般主要是两种机制&#xff1a;1.valid–ready反压(backpressure)机制&#xff1b;2.credit信用机制&#xff1b; credit机制…

软件设计师干货资料分享

从2月份备考&#xff0c;到5月份结束&#xff0c;满打满算四个月准备时间。在此我想提醒一句&#xff0c;世界上没有什么不劳而获的事情&#xff0c;never&#xff0c;只要你是一个普通人&#xff0c;但凡你想索取一些什么&#xff0c;无一例外你都需要付出&#xff0c;而且是踏…

Pytorch深度学习实践笔记6(b站刘二大人)

&#x1f3ac;个人简介&#xff1a;一个全栈工程师的升级之路&#xff01; &#x1f4cb;个人专栏&#xff1a;pytorch深度学习 &#x1f380;CSDN主页 发狂的小花 &#x1f304;人生秘诀&#xff1a;学习的本质就是极致重复! 《PyTorch深度学习实践》完结合集_哔哩哔哩_bilibi…