資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告