当前位置: 首页 > news >正文

LeetCode---391周赛

题目列表

3099. 哈沙德数

3100. 换水问题 II

3101. 交替子数组计数

3102. 最小化曼哈顿距离

一、哈沙德数

简单的模拟题,代码如下

class Solution {
public:int sumOfTheDigitsOfHarshadNumber(int x) {int s = 0, tmp = x;while(tmp){s+=tmp%10;tmp/=10;}return x%s==0?s:-1;}
};

二、换水问题II

这题也是一个模拟题,我们只要维护好空瓶数和喝掉的瓶数,就能很容易得出答案。

代码如下

class Solution {
public:int maxBottlesDrunk(int numBottles, int numExchange) {int ans = numBottles; // 记录喝掉的瓶数int empty = numBottles; // 记录剩余空瓶子的数量while(empty>=numExchange){// 用numExchange个空瓶子换一瓶empty-=numExchange;empty++;numExchange++;ans++;}return ans;}
};

我们来简单算一下该模拟算法的时间复杂度,假设一开始有sum个瓶子,循环执行了n次,从numExchange=1开始,那么会有 1+2+3+...+n+n+1 <= sum + n,粗略的估算一下n^2<=sum,n<=sqrt(sum),所以该算法是根号级的时间复杂度(甚至更优),所以模拟算法也可以很快

三、交替子数组计数

这题我们可以统计以i为右端点符合条件的子数组个数【以i为右端点的符合条件的最长子数组中的元素个数=以i为右端点的符合条件的子数组个数

代码如下

class Solution {
public:long long countAlternatingSubarrays(vector<int>& nums) {int n = nums.size();long long ans = n; // 单独一个0/1组成的子数组符合条件// 统计 长度>=2 的符合要求的子数组个数for(int i=0;i<n;){int j=i++;while(i<n&&nums[i-1]!=nums[i]){ans += i-j; // 统计以i为右端点的符合条件的子数组个数i++;}}return ans;}
};

四、最小化曼哈顿距离

(曼哈顿距离:|x1 - x2| + |y1 - y2|)

这题的关键在于如何快速的找到一堆点的最大曼哈顿距离。

从公式出发:

|x1 - x2| + |y1 - y2|

= max(x1-x2+y1-y2,x1-x2+y2-y1,x2-x1+y1-y2,x2-x1+y2-y1)

= max( (x1+y1) - (x2+y2),(x1-y1) - (x2-y2),(x2-y2) - (x1-y1),(x2+y2) - (x1+y1))

= max( |(x1+y1) - (x2+y2)|,|(x1-y1) - (x2-y2)| )

很显然,只要维护好x+y和x-y的最大值和最小值,就能在O(1)的时间中得到最大的曼哈顿距离
代码如下

class Solution {
public:int minimumDistance(vector<vector<int>>& points) {multiset<int>s1,s2;for(auto&v:points){s1.insert(v[0]+v[1]);s2.insert(v[0]-v[1]);}int ans = INT_MAX;for(auto&v:points){s1.extract(v[0]+v[1]);s2.extract(v[0]-v[1]);ans=min(ans,max(*s1.rbegin()-*s1.begin(),*s2.rbegin()-*s2.begin()));s1.insert(v[0]+v[1]);s2.insert(v[0]-v[1]);}return ans;}
};

相关文章:

LeetCode---391周赛

题目列表 3099. 哈沙德数 3100. 换水问题 II 3101. 交替子数组计数 3102. 最小化曼哈顿距离 一、哈沙德数 简单的模拟题&#xff0c;代码如下 class Solution { public:int sumOfTheDigitsOfHarshadNumber(int x) {int s 0, tmp x;while(tmp){stmp%10;tmp/10;}return x…...

微信小程序的页面交互2

一、自定义属性 &#xff08;1&#xff09;定义&#xff1a; 微信小程序中的自定义属性实际上是由data-前缀加上一个自定义属性名组成。 &#xff08;2&#xff09;如何获取自定义属性的值&#xff1f; 用到target或currentTarget对象的dataset属性可以获取数据 &#xff…...

【VSCode】修改插件地址

不想放在原始C盘下面C:\Users\{用户}\.vscode\extensions为了后续存储空间考虑&#xff0c;想通过添加环境变量创建名为VSCODE_EXTENSIONS的环境变量&#xff0c;内容指向vs Code扩展所在目录即可 直接配置环境变量&#xff0c;不要在有空格的文件夹下面 变量名称&#xff1a;…...

自然语言处理NLP概述

大家好&#xff0c;自然语言处理(NLP)是计算机科学领域与人工智能领域中的一个重要方向&#xff0c;其研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法。本文将从自然语言处理的本质、原理和应用三个方面&#xff0c;对其进行概述。 一、NLP的本质 NLP是一种…...

计算机网络——37认证

认证 目标&#xff1a;Bob需要Alice证明他的身份 Protocol ap1.0&#xff1a;Alice说"A am Alice" 可能出现的问题&#xff1a; 在网络上Bob看不到Alice&#xff0c;因此Trudy可以简单的声称他是Alice 认证&#xff1a;重新尝试 Protocol ap2.0&#xff1a;Alice…...

Java中利用BitMap位图实现海量级数据去重

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 目录 前言 什么是BitMap&#xff1f;有什么用&#xff1f; 基本概念 位图的优势 …...

Linux知识点记录

Linux知识点记录 1. 后台运行应用程序方法一&#xff1a;&方法二&#xff1a;nohup & 2. 一个shell脚本中执行多个应用程序3. 2>&14. shell脚本清除日志5. 通过grep查找匹配字符串 1. 后台运行应用程序 参考文章&#xff1a;https://blog.csdn.net/Pan_peter/…...

js的check函数

在JavaScript中&#xff0c;并没有一个内置的名为check的函数。然而&#xff0c;你可以根据需求自定义一个check函数&#xff0c;用于执行各种验证和检查任务。这个check函数的具体作用完全取决于你如何定义和实现它。 以下是一个简单的示例&#xff0c;展示了如何定义一个che…...

赛尼格磁电科技邀您到场参观2024第13届生物发酵展

参展企业介绍 北京赛尼格磁电科技有限公司是一家中加合资的专业永磁组件生产商&#xff0c;2001年成立于中国北京。公司专业从事磁性材料的应用及各类磁系统的设计、开发及制造&#xff0c;公司产品广泛应用于汽车行业、建筑行业、电子行业、航海领域、医学领域、教育领域等。 …...

gpt国内怎么用?最新版本来了

claude 3 opus面世后&#xff0c;这几天已经有许多应用&#xff0c;而其精确以及从不偷懒&#xff08;截止到2024年3月11日还没有偷懒&#xff09;的个性&#xff0c;也使得我们可以用它来首次完成各种需要多轮对话的尝试。 今天我们想要进行的一项尝试就是—— 如何从一个不知…...

Vim脚本语言入门:打造你的编辑器

简介 Vim脚本语言是Vim编辑器内置的一种脚本语言&#xff0c;它赋予用户高度的定制和自动化编辑任务的能力。通过编写Vim脚本&#xff0c;用户可以根据自己的需求来扩展和改进Vim编辑器的功能&#xff0c;从而提高编辑效率和舒适度。 在Vim中&#xff0c;脚本语言被广泛用于创…...

myweb项目资料集

项目要求 前后端分离后端采用 flask 框架前端采用 vue3 框架 后端部分 Flask 3 框架&#xff1a; https://dormousehole.readthedocs.io/en/latest/quickstart.html Session&#xff1a; https://blog.csdn.net/zhangvalue/article/details/93892241 MySQL 操作&#xf…...

Kubernetes(k8s):部署、使用 metrics-server

Kubernetes&#xff08;k8s&#xff09;&#xff1a;部署、使用 metrics-server 一、metrics-server简介二、部署metrics-server2.1、 下载 Metrics Server 部署文件2.2、修改metrics-server.yaml 文件2.3、 部署 Metrics Server2.4、 检查 Metrics Server 三、使用 Metrics Se…...

为什么建议你学习Spring底层原理?

1.根因 Java诞生以来&#xff0c;一直是业界的主流语言和平台&#xff0c;而Spring则是Java开发的平台。与其说是用Java编程&#xff0c;不如说是在Spring框架上编程。即便最近几年比较火的Spring Boot、Spring Cloud&#xff0c;其底层内核仍然是Spring。因此&#xff0c;作为…...

post请求搜索功能爬虫

<!--爬虫仅支持1.8版本的jdk--> <!-- 爬虫需要的依赖--> <dependency> <groupId>org.apache.httpcomponents</groupId> <artifactId>httpclient</artifactId> <version>4.5.2</version> </dependency>…...

#pragma once的作用

使用visual studio新建头文件时&#xff0c;第一行会出现如下默认代码&#xff0c; #pragma once 它是一种编译器指令&#xff0c;通常用于确保头文件只被包含一次&#xff0c;以避免产生重复定义的问题。当编译器处理一个源文件时&#xff0c;遇到#pragma once指令时&#xf…...

【Android】图解View的工作流程原理

文章目录 入口DecorView如何加载到Window中MeasureSpec MeasureView的测量ViewGroup的测量 LayoutView的layout() Draw1、绘制背景3、绘制View内容4、绘制子View6、绘制装饰 入口 DecorView如何加载到Window中 MeasureSpec 该类是View的内部类&#xff0c;封装View的规格尺寸…...

记工时流程

记工时流程 加入团体 加入观古鉴古服务队 登录成功后&#xff0c;点击我的-我的成员 添加成员 进入小程序 扫描后登录&#xff0c;我的-我的团体&#xff0c;可以看到观古鉴古服务队&#xff0c; 进入后点项目 选择观古鉴古文化志愿者招募 -> 我要报名 -> 选择文化志…...

Ubuntu20.04使用Neo4j导入CSV数据可视化知识图谱

1.安装JDK&#xff08; Ubuntu20.04 JDK11&#xff09; sudo apt-get install openjdk-11-jdk -y java -version which java ls -l /usr/bin/java ls -l /etc/alternatives/java ls -l /usr/lib/jvm/java-11-openjdk-amd64/bin/java确认安装路径为/usr/lib/jvm/java-11-openjd…...

vue-cli打包 nodejs内存溢出 vue2.x Last few GCs

遇到这种情况百度各种博客&#xff0c;什么改package.json里的配置&#xff0c;什么安装increase-memory-limit &#xff0c;都尝试了并没什么用处&#xff0c;最后解决方案为执行下方名单&#xff0c;再次打包就成功了&#xff1a; export NODE_OPTIONS--max_old_space_size4…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...