当前位置：首页 > article >正文

力扣第331场周赛题解

article 来源：原创 2023/2/5 15:12:14

rank	T1	T2	T3	T4
331 / 4256	0:01:46	0:06:18 (1)	0:11:58	0:57:29 (4)

T1 从数量最多的堆取走礼物

模拟题，每次操作找出最大值 $ma xx$ 并将其变成 $s q r t (ma xx)$ ， $k$ 次操作后求和。

数据范围很小，可以暴力模拟，更好的方法是使用优先队列模拟。

时间复杂度 $O (ma x (n, k) l o g (n))$
空间复杂度 $O (n)$

参考代码

class Solution {public:long long pickGifts(vector<int>& a, int k) {priority_queue<int> q;for (auto it : a) {q.push(it);}while (k--) {int s = q.top();q.pop();s = sqrt(s);q.push(s);}long long ans = 0;while (q.size()) {ans += q.top();q.pop();}return ans;}
};

T2 统计范围内的元音字符串数

给定一个字符串数组，每次询问区间 $[l, r]$ 内，首尾字母都是元音字母的字符串数量。

预处理前缀和，差分询问。

时间复杂度 $O (n + q)$
空间复杂度 $O (n)$

参考代码

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
class Solution {public:map<int, int> mp;bool check(string s) {return mp[s[0]] && mp[s.back()];}int sum[N];vector<int> vowelStrings(vector<string>& a, vector<vector<int>>& q) {mp['a'] = 1;mp['e'] = 1;mp['i'] = 1;mp['o'] = 1;mp['u'] = 1;int n = a.size();for (int i = 0; i < n; i++) {sum[i + 1] = sum[i] + check(a[i]);}vector<int> ans;for (auto it : q) {ans.emplace_back(sum[it[1] + 1] - sum[it[0]]);}return ans;}
};

T3 打家劫舍 IV

要求最大值最小，经典二分答案+ $c h ec k$
$c h ec k$ 思路：二分出 $mi d$ ，贪心地线性检查能否取出 $k$ 个价值 $<= mi d$ 的房屋即可。

时间复杂度 $O (n l o g (m))$
空间复杂度 $O (n)$

参考代码

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;class Solution {public:int minCapability(vector<int>& a, int k) {int n = a.size();int l = 1, r = 1e9, ans;while (l <= r) {int mid = (l + r) / 2;int pre = -2;int sum = 0;for (int i = 0; i < n; i++) {if (i - pre == 1) {//不能相邻continue;}if (a[i] <= mid) {//选择sum++;pre = i;}}if (sum >= k) {r = mid - 1;ans = mid;} else {l = mid + 1;}}return ans;}
};

T4 重排水果

如下考虑：

判断原数组是否合法：两个数组排序后相同，则直接返回0。
判断是否存在解：将两个数组的元素混合在一起，如果某个元素为奇数个，那么一定无解。
剩下来的是必定有解，但需要交换的情况。
首先去除他们的交集元素，现在数组 $a$ 和数组 $b$ 分别多了某些元素。根据每个元素的总数量，容易计算得到他们分别多出来 $x_i$ 个 $y_i$ ，维护 $o u t a$ 和 $o u t b$ ， $o u t a [x] = y$ 表示数组 $a$ 的 $x$ 元素多了 $y$ 个。
考虑如何交换最优：
① 用数组 $a$ 中的最小值和数组 $b$ 中的最大值交换，花费为 $min(a_{minn},b_{maxx})$
② 用数组 $a$ 中的最大值和数组 $b$ 中的最小值交换，花费为 $min(b_{minn},a_{maxx})$
③ 容易遗漏的一种情况，利用所有元素的最小值作为中间者，间接的交换 $ab$ 中的元素：swap(a,c); swap(b,c);，因为 $c$ 必定为最小值，且被用到了两次，因此花费为 $minn * 2$
贪心地，如果数组 $a$ 中的最小值 $<$ 数组 $b$ 中的最小值，则选用方案①③的组合，否则选用方案②③的组合。

时间复杂度 $O (n l o g (n))$
空间复杂度 $O (n)$

参考代码

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
class Solution {public:long long minCost(vector<int>& a, vector<int>& b) {int MINN = INF;map<int, int> mp, ma, mb;for (auto it : a) {mp[it]++, ma[it]++;MINN = min(MINN, it);}for (auto it : b) {mp[it]++, mb[it]++;MINN = min(MINN, it);}if (ma == mb) {// 已经合法return 0;}for (auto& it : mp) {if (it.second % 2) {// 某个元素总数量奇数个，不能平分return -1;}// 期望每个数组各有it.second个it.firstit.second /= 2;}vector<pair<int, int>> outa, outb;int all = 0;for (auto it : mp) {int delta = ma[it.first] - it.second;// a中需要给出delta个it.firstif (delta > 0) {// 总共需要给出all个all += delta;outa.emplace_back(make_pair(it.first, delta));}delta = mb[it.first] - it.second;// b中需要给出delta个it.firstif (delta > 0) {outb.emplace_back(make_pair(it.first, delta));}}long long ans = 0;int n = outa.size();int ra = outa.size() - 1;int rb = outb.size() - 1;int la = 0;int lb = 0;while (all--) {if (!outa[la].second) {++la;}if (!outa[ra].second) {--ra;}if (!outb[lb].second) {++lb;}if (!outb[rb].second) {--rb;}if (outa[la].first < outb[lb].first) {outa[la].second--;outb[rb].second--;// 两种情况，借助最小值来间接交换 / 直接交换ans += min(min(MINN * 2, outa[la].first), outb[rb].first);}if (outa[la].first > outb[lb].first) {outa[ra].second--;outb[lb].second--;ans += min(min(MINN * 2, outa[ra].first), outb[lb].first);}}return ans;}
};

查看全文

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

力扣第331场周赛题解

rankT1T2T3T4331 / 42560:01:460:06:18 (1)0:11:580:57:29 (4) T1 从数量最多的堆取走礼物模拟题，每次操作找出最大值maxxmaxxmaxx并将其变成sqrt(maxx)sqrt(maxx)sqrt(maxx)，kkk次操作后求和。数据范围很小，可以暴力模拟，更好的…...

编程日记 2023/2/5 15:12:14

基于LDA模型的非监督分类算法介绍

前言基于LDA（Latent Dirichlet Allocation）模型的非监督分类算法，将LDA模型从文本分析的应用过渡到遥感高分辨率影像处理的应用，利用Gibbs采样方法设计基于LDA模型的非监督分类算法，并使用IDL语言实现。在一定程度上解…...

编程日记 2023/2/5 15:11:31

以安全有效为目标的综合运营

一、安全行业的现状所有做安全的方案大多会在开始介绍安全的案例，都会列举近期国内外发生的重大安全事件， 基本上都是惨不忍睹，危害巨大。这里就不一一列举了，稍微了解这个行业的人都能看到大量的案例。但业界又有个很奇怪的现象就…...

编程日记 2023/2/5 15:11:17

mysql常见面试题--03 事务常考题以及事务的隔离

什么是事务？ 对数据库的一系列操作,要么全执行,要么不执行. 事务时逻辑上的一组操作，要么全部执行，要么都不执行。事务的三大特征原子性 A 事务是最小执行单位，要么全部执行，要么都不执行一致性 C 事务执行前后&…...

编程日记 2023/2/5 15:10:41

【推荐研究方向（1）】小样本开集目标检测(few-shot open-set detection)

论文题目：Towards Few-Shot Open-Set Object Detection 论文链接：https://arxiv.org/abs/2210.15996 1、任务：小样本开集目标检测，使用少量已知类样本训练模型，使得模型既能够检测小样本已知类又能够检测未知类。 2、动机：解决FSOSOD问题有三个重要原因。 1）可…...

编程日记 2023/2/5 15:09:53

细讲TCP三次握手四次挥手(四)

常见面试题为什么TCP连接的时候是3次？2次不可以吗？ 因为需要考虑连接时丢包的问题，如果只握手2次，第二次握手时如果服务端发给客户端的确认报文段丢失，此时服务端已经准备好了收发数(可以理解服务端已经连接成功)据…...

编程日记 2023/2/5 15:09:26

道路病害识别监测系统 CNN网络

道路病害识别监测系统通过CNN网络深度学习算法，道路病害识别监测对巡检车上实时监控道路影像数据进行分析，输出道路病害裂缝巡检报告并落图展示。在CNN出现之前，对于图像的处理一直都是一个很大的问题，一方面因为图像处理的数据量…...

编程日记 2023/2/5 15:08:57

chromium ARM版本编译记录

需求用的国产电脑，统信麒麟自带的chromium版本都是83版本,lceda要求超过100版本，低版本没法打开编辑器，只能用客户端版本。都是JS，还整这么多事...刚开始想着一步到位直接在阿里云香港主机上买高配置的竞价虚拟机，结果…...

编程日记 2023/2/5 15:08:30

【博客606】k8s如何查看pod崩溃前的日志及其原理

k8s如何查看pod崩溃前的日志及其原理场景当pod处于crash状态的时候，容器不断重启，此时用kubelet logs可能出现一直捕捉不到日志解决方法： kubelet previous参数作用： If true, print the logs for the previous instance of…...

编程日记 2023/2/5 15:07:39

one-shot learning、Siamese网络、Triplet loss、面部验证和二分类

目录1.one-shot learning(一次学习)one-shot learning就是对某一类别只提供一个或者少量的训练样本。而很小的训练集不足以训练一个稳健的神经网络。为了解决这个问题，需要首先训练一个 similarity function：d(img1,img2)，用于表示两张图片的…...

编程日记 2023/2/5 15:06:50

深入浅出 Fast DDS网络协议（入门篇）

如果你是机器人领域的学者，那一定听说过ROS1和ROS2，但这两个有什么区别呢？ ROS1作为一个通信中间件，在两两节点建立TCP/UDP连接之前，通过发布者和订阅者通过xmlRPC和master进行数据交换和查询，待匹配到相同…...

编程日记 2023/3/30 13:42:30

Lambda将List＜Long＞转换成List＜String＞

说明将Long转换为字符串的方式有很多种，如toString，valueOf，拼接字符串，new String()等。将String集合转换成Long集合 List<String> ids Arrays.asList("1", "2", "3", "4", …...

编程日记 2023/3/30 13:42:20

信息系统项目管理师第四版知识摘编：第13章项目资源管理

第13章项目资源管理项目资源管理包括识别、获取和管理所需资源以成功完成项目的各个过程，这些过程有助于确保项目经理和项目团队在正确的时间和地点使用正确的资源。 13.1管理基础 13.1.1相关术语和定义 1项目团队项目团队是执行项目工作&#xf…...

编程日记 2023/3/30 13:42:09

WuThreat身份安全云-TVD每日漏洞情报-2023-03-30

漏洞名称:DriverGenius 内存损坏漏洞级别:中危漏洞编号:CVE-2023-1679 相关涉及:DriverGenius 9.70.0.346 漏洞状态:POC 参考链接:https://tvd.wuthreat.com/#/listDetail?TVD_IDTVD-2023-07738 漏洞名称:Xunrui CMS system_log.html信息泄露漏洞级别:中危漏洞编号:CVE-2…...

编程日记 2023/3/30 13:41:59

java——包机制

类添加包名 module.java分配包名com.henu后，module.java的全名就是com.henu.module.java。编译、运行module.java 文件夹最初目录 Module1.java文件内容 package com.henu; public class Module{public static void main(String args[]){System.out.println("…...

编程日记 2023/3/30 13:41:50

SoapUI基础使用教程

目录一、HTTP接口调用 1、创建项目 2、输入http请求地址 3、选择对应项目的request，输入信息发送请求二、Webservice接口调用 2.1先来看soap风格的webservice接口调用的步骤 2.2再来看rest风格调用webservice接口的步骤三、报文乱码一、HTTP接口调用 1…...

编程日记 2023/3/30 13:41:41

PyAutoGUI实现自动化控制示例代码（含屏幕自适应）

PyAutoGUI自动化控制库的使用 PyAutoGUI是一个Python自动化控制库，可以用于控制键盘和鼠标的输入，以及获取屏幕截图和像素点信息等操作。在本篇博客中，我们将介绍如何使用PyAutoGUI来实现自动化控制，并以代码示例的形式展现其基本…...

编程日记 2023/3/30 13:41:26

LC-1637. 两点之间不包含任何点的最宽垂直区域（模拟）

1637. 两点之间不包含任何点的最宽垂直区域难度中等25 给你 n 个二维平面上的点 points ，其中 points[i] [xi, yi] ，请你返回两点之间内部不包含任何点的最宽垂直区域的宽度。垂直区域的定义是固定宽度，而 y 轴上无限延伸的一块区域…...

编程日记 2023/3/30 13:41:16

第二节：Git基本操作（关键词：git add、commit、diff、reset、checkout、rm、mv）

文章目录一：Git基本工作流程二：Git基本操作（1）git init（2）git add（3）git commit（4）git diff（5）git resetA：概述B&#xff…...

编程日记 2023/3/30 13:41:01

指针太难？手把手教你理解指针（指针？数组？）

目录前言一、指针的基本概念 1、内存 2、指针变量的大小 3、指针的类型及其运算 （1）类型 （2）运算二、指针的进阶 1.字符指针 2.指针数组 3.数组指针 （1）数组指针的定义 （2&…...

编程日记 2023/3/30 13:40:47

相关文章：