LeetCode 565. 数组嵌套
发布日期:2021-07-01 03:27:03
浏览次数:2
分类:技术文章
本文共 1507 字,大约阅读时间需要 5 分钟。
1. 题目
索引从0开始长度为N的数组A,包含0到N - 1的所有整数。
找到最大的集合S并返回其大小,其中S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }
且遵守以下的规则。 假设选择索引为i的元素A[i]为S的第一个元素,S的下一个元素应该是A[A[i]]
,之后是A[A[A[i]]]...
以此类推,不断添加直到S出现重复的元素。
示例 1:输入: A = [5,4,0,3,1,6,2]输出: 4解释: A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.其中一种最长的 S[K]:S[0] = { A[0], A[5], A[6], A[2]} = { 5, 6, 2, 0} 提示:N是[1, 20,000]之间的整数。A中不含有重复的元素。A中的元素大小在[0, N-1]之间。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/array-nesting
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 把走过的标记成 -1
- 每次从没有走过的地方开始,记录长度
class Solution { // C++public: int arrayNesting(vector & nums) { int maxlen = 0, len = 0, idx = 0, prev; for(int i = 0; i < nums.size(); ++i) { if(nums[i] == -1) continue; idx = i; len = 0; while(idx != -1 && nums[idx] != -1)//没有出现循环 { len++; prev = idx;//前一个id idx = nums[idx];//下一个id nums[prev] = -1;//走过的标记成-1 } maxlen = max(maxlen, len); } return maxlen; }};
36 ms 29.3 MB
class Solution:# py3 def arrayNesting(self, nums: List[int]) -> int: maxlen = 0 for i in range(len(nums)): if nums[i] == -1: continue idx = i length = 0 while idx != -1 and nums[idx] != -1: length += 1 prev = idx idx = nums[idx] nums[prev] = -1 maxlen = max(maxlen, length) return maxlen
172 ms 15.5 MB
转载地址:https://michael.blog.csdn.net/article/details/106832333 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月16日 17时39分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Spark学习——利用Mleap部署spark pipeline模型
2019-05-01
Oracle创建表,修改表(添加列、修改列、删除列、修改表的名称以及修改列名)
2019-05-01
使用redis实现订阅功能
2019-05-01
对称加密整个过程
2019-05-01
java内存模型
2019-05-01
volatile关键字
2019-05-01
Servlet_快速入门
2019-05-01
Request_继承体系
2019-05-01
前端权限控制:获取用户信息接口构造数据
2019-05-01
七牛云存储:断点续传
2019-05-01
字节流复制文本文件【应用】
2019-05-01
私钥加密私钥解密
2019-05-01
锁的释放流程-ReentrantLock.unlock
2019-05-01
Java判断字符串是否为数字(浮点类型也包括)
2019-05-01
ubuntu opencv-python 安装很慢问题
2019-05-01
MySQL5.7版本修改了my.ini配置文件后mysql服务无法启动问题
2019-05-01
Azkaban体系结构
2019-05-01
机器学习之重头戏-特征预处理
2019-05-01