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

算法 环形数组是否存在循环 力扣执行速度击败100%

目录

题目 leetcode 457

求解思路

代码

结果


题目 leetcode 457

存在一个不含 0 的 环形 数组 nums ,每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数:

  • 如果 nums[i] 是正数,向前(下标递增方向)移动 |nums[i]| 步
  • 如果 nums[i] 是负数,向后(下标递减方向)移动 |nums[i]| 步

因为数组是 环形 的,所以可以假设从最后一个元素向前移动一步会到达第一个元素,而第一个元素向后移动一步会到达最后一个元素。

数组中的 循环 由长度为 k 的下标序列 seq 标识:

  • 遵循上述移动规则将导致一组重复下标序列 seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...
  • 所有 nums[seq[j]] 应当不是 全正 就是 全负
  • k > 1

如果 nums 中存在循环,返回 true ;否则,返回 false 

示例 1:

输入:nums = [2,-1,1,2,2]
输出:true
解释:存在循环,按下标 0 -> 2 -> 3 -> 0 。循环长度为 3 。

示例 2:

输入:nums = [-1,2]
输出:false
解释:按下标 1 -> 1 -> 1 ... 的运动无法构成循环,因为循环的长度为 1 。根据定义,循环的长度必须大于 1 。

示例 3:

输入:nums = [-2,1,-1,-2,-2]
输出:false
解释:按下标 1 -> 2 -> 1 -> ... 的运动无法构成循环,因为 nums[1] 是正数,而 nums[2] 是负数。
所有 nums[seq[j]] 应当不是全正就是全负。

提示:

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

求解思路

首先定义一个工具函数next_index求下一个索引,值得注意的是python支持这种方法内部定义方法的方式

然后对每个下标起点进行遍历

如果nums[i] 为 0,则代表这里会卡死,要跳过

我们让fast指针快slow一步,一个是方便后面的代码,二个是加快执行效率,让快指针更快追上慢指针,得出是否存在循环

while作检测,检查慢指针和当前快指针指向的数字,也就是移动步数是否同号(题目要求循环的路径要同号),检查慢指针和快指针下一步位置是否同号

如果同号,继续比较快慢指针现在是否相等,如果相当,还要检查慢指针下一步位置是不是自己(题目要求路径长度至少为2),如果不是自己才能return True

如果不相当,则让快指针两步走,慢指针一步走

直到while循环结束,还没return结果,执行下面的代码

接下来的代码是性能提升关键,不加上的话只能击败9.52%的人,,

我需要重新让慢指针为i,一切重新开始,让慢指针一步步走,一步步把它走过的地方变成0,让以后再来到这里就知道这里没有结果

代码

class Solution(object):def circularArrayLoop(self, nums):def next_index(i):return (i + nums[i]) % len(nums)for i in range(len(nums)):if nums[i] == 0:continueslow, fast = i, next_index(i)while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next_index(fast)] > 0:if slow == fast:if slow == next_index(slow):breakreturn Trueslow = next_index(slow)fast = next_index(next_index(fast))# 性能提升slow = i while nums[slow] * nums[next_index(slow)] > 0:tmp = slow slow = next_index(slow)nums[tmp] = 0return False

结果

相关文章:

算法 环形数组是否存在循环 力扣执行速度击败100%

目录 题目 leetcode 457 求解思路 代码 结果 题目 leetcode 457 存在一个不含 0 的 环形 数组 nums &#xff0c;每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数&#xff1a; 如果 nums[i] 是正数&#xff0c;向前&#xff08;下标递增方向&#xff0…...

FFmpeg——开源的开源的跨平台音视频处理框架简介

引言&#xff1a; FFmpeg是一个开源的跨平台音视频处理框架&#xff0c;可以处理多种音视频格式。它由Fabrice Bellard于2000年创建&#xff0c;最初是一个只包括解码器的项目。后来&#xff0c;很多开发者参与其中&#xff0c;为FFmpeg增加了多种新的功能&#xff0c;例如编码…...

怎么看待Groq

用眼睛看。 就是字面上的意思用眼睛看。 我属于第一波玩到的,先给大家一个直观的印象,Groq到底有多快。 目前Groq只能选Llama的70b,和Mixtral的MoE,那我选7*8的这个MoE模型来实验。 这么好些字大概花了不到1秒,流式响应,其实是不是流式已经没那么重要了 ,然后看每秒Toke…...

Kafka | SpringBoot集成Kafka

SpringBoot集成Kafka 一、前言二、项目1. pom2. application.properties4. 消息生产者-测试5. 消息消费者 三、启动测试四、有总结的不对的地方/或者问题 请指正, 我在努力中 一、前言 该文章中主要对SpringBoot 集成Kafka 主要是 application.properties 与 pom坐标就算集成完…...

python的tqdm库不显示动态进度条的问题

python的tqdm库不显示动态进度条的问题 本质原因是tqdm无法获取内部对象的长度&#xff0c;这可能是因为内部对象是一个迭代器&#xff0c;问题经常发生在同时使用tqdm与enumerate的场合&#xff0c;例如深度学习中经常可能出现的&#xff1a; tqdm.tqdm(enumerate(train_loade…...

【prompt四】Domain Prompt Learning for Efficiently Adapting CLIP to Unseen Domains

motivation 领域泛化(DG)是一个复杂的迁移学习问题,旨在学习未知领域的可泛化模型。最近的基础模型(FMs)对许多分布变化都具有鲁棒性,因此,应该从本质上提高DG的性能。在这项工作中,我们研究了采用视觉语言基础模型CLIP来解决图像分类中的DG问题的通用方法。虽然ERM使用标…...

利用Amazon Bedrock畅玩Claude 3等多种领先模型,抢占AI高地(体验倒计时4小时)

快乐的时间总是短暂的&#xff0c;Claude 3 在亚马逊云科技上限时体验仅剩4小时&#xff0c;上次分享了入门级操作教程&#xff0c;本期给大家带来AWS Lambda Amazon Bedrock一起构建可以便捷使用的Claude 3接口 AWS Lambda AWS Lambda 是一项计算服务&#xff0c;可以运行您…...

MySql分布式事务

1 seata 底层原理 Seata&#xff08;Simple Extensible Autonomous Transaction Architecture&#xff09;是一个开源的分布式事务解决方案&#xff0c;其底层原理主要基于改进的传统2PC&#xff08;Two-Phase Commit&#xff0c;两阶段提交&#xff09;协议&#xff0c;并结合…...

android基础学习

从上面的描述就可以知道&#xff0c;每一个Activity组件都有一个对应的ViewRoot对象、View对象以及WindowManager.LayoutParams对象。这三个对象的对应关系是由WindowManagerImpl类来维护的。具体来说&#xff0c;就是由WindowManagerImpl类的成员变量mRoots、mViews和mParams所…...

解决方案:Python画图汉字丢失显示小方块

解决方案&#xff1a; linux python解决中文字体 - jingsupo - 博客园 (cnblogs.com) 在找字体缓存文件的时候我找了一会儿&#xff0c;我的路径是这里&#xff1a; 做了所有更改之后&#xff0c;最后一定要把缓存文件删掉&#xff0c;不然还是会报同样的错误的。 这里再贴一…...

JWT的是什么

session共享 什么是session共享 Session共享是指在分布式系统中&#xff0c;在多个服务器之间共享同一个用户的会话数据。在传统的Web应用中&#xff0c;用户的会话信息通常存储在服务器端的Session中&#xff0c;而每个用户的请求在同一个服务器上处理&#xff0c;因此可以轻…...

git常用命令集合

1.差异对比 显示出branch1和branch2中差异的部分 git diff branch1 branch2 --stat显示出所有有差异的文件的详细差异 git diff branch1 branch2查看branch1分支有&#xff0c;而branch2中没有的log git log branch1 ^branch22.分支 列出所有本地分支 git branch列出所有远…...

UDP通信发送和接收 || UDP实现全双工通信

recvfrom ssize_t recvfrom(int sockfd, void *buf, size_t len, int flags, struct sockaddr *src_addr, socklen_t *addrlen); 功能: 从套接字中接收数据 参数: sockfd:套接字文件描述符 buf:存放数据空间首地址 …...

Mac 以SH脚本安装Arthas

SH脚本安装Aethas curl -L https://alibaba.github.io/arthas/install.sh | sh安装脚本说明 示例源文件&#xff1a; #! /bin/bash# temp file of as.sh TEMP_ARTHAS_FILE"./as.sh.$$"# target file of as.sh TARGET_ARTHAS_FILE"./as.sh"# update timeo…...

Elasticsearch:dense vector 数据类型及标量量化

密集向量&#xff08;dense_vector&#xff09;字段类型存储数值的密集向量。 密集向量场主要用于 k 最近邻 (kNN) 搜索。 dense_vector 类型不支持聚合或排序。 默认情况下&#xff0c;你可以基于 element_type 添加一个 dend_vector 字段作为 float 数值数组&#xff1a; …...

Linux C/C++下使用Lex/Yacc构建实现DBMS(Minisql)

DBMS&#xff08;数据库管理系统&#xff09;是一种用于管理和组织数据库的软件系统。它的重要性在于提供了一种有效地存储、管理和访问大量数据的方式。本文将深入探讨如何使用C语言、Lex&#xff08;词法分析器生成器&#xff09;和Yacc&#xff08;语法分析器生成器&#xf…...

c语言指针小白基础教学

指针 1. 什么是指针&#xff1f;2. 如何编址&#xff08;即如何给地址分配空间呢&#xff09;3. 概念和基本术语3.1指针的值指针所指向的地址/内存区3.2 指针的类型&#xff08;指针本身的类型&#xff09;思考&#xff1a; 3.3 指针所指向的类型3.4 指针本身所占据的内存区3.5…...

面向对象设计之里氏替换原则

设计模式专栏&#xff1a;http://t.csdnimg.cn/4Mt4u 思考&#xff1a;什么样的代码才算违反里氏替换原则&#xff1f; 目录 1.里氏替换原则的定义 2.里氏替换原则与多态的区别 3.违反里氏替换原则的反模式 4.总结 1.里氏替换原则的定义 里氏替换原则&#xff08;Liskov S…...

MySQL·SQL优化

目录 一 . 前言 二 . 优化方法 1 . 索引 &#xff08;1&#xff09;数据构造 &#xff08;2&#xff09;单索引 &#xff08;3&#xff09;explain &#xff08;4&#xff09;组合索引 &#xff08;5&#xff09;索引总结 2 . 避免使用select * 3 . 用union all代替u…...

Dockerfile指令大全

Dockerfile文件由一系列指令和参数组成。指令的一般格式为INSTRUCTION arguments。具体来说&#xff0c;包括"配置指令"(配置镜像信息)和"操作指令"(具体执行操作)。每条指令&#xff0c;如FROM&#xff0c;都是大小写不敏感的。但是为了区分指令和参数&am…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...