h*********2
发帖数: 192 | 1 Given a non-empty array A. Set S[k] is defined as S[k]={A[k], A[A[k]], A[A[A
[k]]], ...}. For example, A={5, 4, 0, 3, 1, 6, 2}. S[2]={0, 5, 6, 2}. Find
out the longest Set size.
int solution(vector &A) {
//write your code in c++11
}
My idea is to DFS find each set and update a max size so far. Is it optimal?
Thanks! | a*******e
发帖数: 455 | | t********n
发帖数: 611 | 3 S[0] = [5,6,2,0]
S[2] = [0,5,6,2]
S[5] =[6,2,0,5]
S[6]= [2,0,5,6]
所以只要算出一个，其他的数就是一个循环，长度一样。所以不用重复计算。比如，只
要算出S［0］，那么S［5］，S［6］，S［2］ 都可以忽略了。然后找下一个不在数组
中的index，这里也就是1，然后算S［1］。不过既然S［0］的长度已经超过原来数组的
一半，所以这就是最佳长度。否则应该再计算S［1］，S[1] = [4,1], 然后就只剩下S
［3］了。
[A
optimal?
【在 h*********2 的大作中提到】
: Given a non-empty array A. Set S[k] is defined as S[k]={A[k], A[A[k]], A[A[A
: [k]]], ...}. For example, A={5, 4, 0, 3, 1, 6, 2}. S[2]={0, 5, 6, 2}. Find
: out the longest Set size.
: int solution(vector &A) {
: //write your code in c++11
: }
: My idea is to DFS find each set and update a max size so far. Is it optimal?
: Thanks!
| y**********a
发帖数: 824 | 4 public int largestSet(int[]A) {
int rel=0;
int[]dp=new int[A.length];
boolean[]v=new boolean[A.length];
for (int i=0;i
if (!v[i]) rel=Math.max(rel, fillCycle(A, v, dp, i));
return rel;
}
int fillCycle(int[]A, boolean[]v, int[]dp, int i) {
int j=i;
for (j=i;!v[j];j=A[j]){
if (dp[j]!=0) return dfs(A, dp, i);
v[j]=true;
}
int count=1,k=A[j];
for (;k!=j;k=A[k]) ++count;
for (k=A[k];k!=j;k=A[k])dp[k]=count;
dp[j]=count;
return dfs(A, dp, i);
}
int dfs(int[]A, int[]dp, int i) {
if (dp[i]!=0) return dp[i];
return dp[i]=dfs(A, dp, A[i])+1;
} | o****s
发帖数: 143 | 5
S
按照这个思路写了一个：
public int longestSetSize(int A[], int k){
int count = 0;
int max = 0;
boolean[] visited = new boolean[A.length];
while(count < A.length){
if(k >= A.length || visited[k]){
for(int i=0;i
if(!visited[i]){
k = i;
break;
}
}
}
int temp = 0;
while(k
temp++;
k = A[k];
count++;
}
max = Math.max(max,temp);
}
return max;
}
【在 t********n 的大作中提到】
: S[0] = [5,6,2,0]
: S[2] = [0,5,6,2]
: S[5] =[6,2,0,5]
: S[6]= [2,0,5,6]
: 所以只要算出一个，其他的数就是一个循环，长度一样。所以不用重复计算。比如，只
: 要算出S［0］，那么S［5］，S［6］，S［2］ 都可以忽略了。然后找下一个不在数组
: 中的index，这里也就是1，然后算S［1］。不过既然S［0］的长度已经超过原来数组的
: 一半，所以这就是最佳长度。否则应该再计算S［1］，S[1] = [4,1], 然后就只剩下S
: ［3］了。
:
|
|
