当前位置: 首页 > 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…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...