数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++数组嵌套
假设我们有一个长度为N的、从0到N-1的零索引数组A。我们必须找到并返回集合S的最长长度，其中S[i] = {A[i], A[A[i]], A[A[A[i]]], ...}，服从如下规则：考虑S中的第一个元素从索引=i的元素A[i]开始，S中的下一个元素应该是A[A[i]]，然后是A[A[A[i]]]……以此类推，我们在S中出现重复元素之前停止添加。因此，如果数组类似于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。
为了解决这个问题，我们将遵循以下步骤：
- 所以创建一个名为dfs的函数。这将接收节点、arr数组、v数组和一个名为visited的集合。在dfs数组中执行以下操作：
- 如果访问了节点，则返回
- 将节点插入v，将节点标记为已访问
- dfs(arr[node], arr, v, visited)
- 在主方法中，执行以下操作：
- ret := 0, n := nums的大小。创建一个名为visited的集合
- 对于范围从0到n – 1的i
- 创建一个数组v
- 如果nums[i]未被访问，则dfs(nums[i], nums, v, visited)
- ret := ret和v的大小中的最大值
- 返回ret
让我们来看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(int node, vector <int>& arr, vector <int>& v, set <int>& visited){
if(visited.count(node)) return;
v.push_back(node);
visited.insert(node);
dfs(arr[node], arr, v, visited);
}
int arrayNesting(vector<int>& nums) {
int ret = 0;
int n = nums.size();
set <int> visited;
for(int i = 0; i < n; i++){
vector <int> v;
if(!visited.count(nums[i]))dfs(nums[i], nums, v, visited);
ret = max(ret, (int)v.size());
}
return ret;
}
};
main(){
vector<int> v = {5,4,0,3,1,6,2};
Solution ob;
cout << (ob.arrayNesting(v));
}输入
[5,4,0,3,1,6,2]
输出
4
更新于：2020年5月4日
429 次浏览
广告