Codility測試Java數組S = A [A [A [A [int]]]]？

-2

我嘗試了一個Codility測試，它給了我一個普通的數組'A'，並要求執行如下計算：x = A[i], x = A[A[i]], x = A[A[A[i]]] ....（更多細節見圖），我不明白它背後的邏輯。在問題數組A = [5,4,0,3,1,6,2] and A[2] = 0, A[A[i]] = 4, A[A[A[i]]] = 6, A[A[A[A[i]]]] = 2中顯示的示例中。Codility測試Java數組S = A [A [A [A [int]]]]？

有人可以解釋這背後的邏輯，並顯示自己的解決方案的問題。

codility測試snipet

附：我能夠完成並通過示例測試，但我覺得我使用了一種非常便宜的方法，可能無法爲我贏得任何積分。

下面的代碼是我的解決方案，它的工作原理，但我敢打賭，不是誰做的是誰在尋找。我無法弄清楚「A [A [A ....]」背後的邏輯，如果我確實能做出更好的解決方案。

class Solution { 
    public int solution(int[] A) { 
     // write your code in Java SE 8 

     String[] values = new String[A.length]; 

     int max = 0; 
     int counter = 0; 

     for(int i = 0; i < A.length; i++){ 

     String ASet1 = Integer.toString(A[i]); 
     String ASet2 = Integer.toString(A[A[i]]); 
     String ASet3 = Integer.toString(A[A[A[i]]]); 
     String ASet4 = Integer.toString(A[A[A[A[i]]]]); 
     String ASet5 = Integer.toString(A[A[A[A[A[i]]]]]); 
     String ASet6 = Integer.toString(A[A[A[A[A[A[i]]]]]]); 
     String ASet7 = Integer.toString(A[A[A[A[A[A[A[i]]]]]]]); 
     String ASet8 = Integer.toString(A[A[A[A[A[A[A[A[i]]]]]]]]); 
     String ASet9 = Integer.toString(A[A[A[A[A[A[A[A[A[i]]]]]]]]]); 

      values[i] = ASet1 + ASet2 + ASet3 + ASet4 + ASet5 + ASet6 + ASet7 + ASet8 + ASet9; 

      //System.out.println(values[i]); 
      } 



     for(int l = 0; l < values.length; l++){ 
     String valueline = values[l]; 
     for(int j = 0; j < values.length; j++){ 


      counter = 0; 
      char c = valueline.charAt(j); 

      for(int k = 1; k < values.length; k++){ 
      char c2 = valueline.charAt(k); 


      if(c != c2){ 

      counter++; 

      }else{ 
       continue; 
       //counter = 0; 
       } 

      if(max < counter){ 
       max = counter; 
       } 
     } 

     } 
     } 

     return max - 1; 
    } 
}

來源

2017-06-21 Sami Rahman

歡迎來到本網站薩米。這是一個針對開發者的網站，許多開發者都在這裏幫助你。但是，除非我們看到您的代碼，否則您的問題無法解決。粘貼您在這個問題中編寫的代碼。 – progyammer

@progyammer你是對的，但除了顯示代碼（見[mcve]）之外，還應該有一個需要解決的問題陳述。只是「顯示他們自己解決問題的方法」，就像OP請求對於SO一樣總是太寬泛。 OP應該閱讀[help] –

sry沒有完整的代碼snipet，但我試圖解釋我的整個過程，我主要試圖理解S [K] = A [K]，A [A []] ，A [A [A [K]]] ... ... –

您需要查找排列的最長不相交週期的長度。很明顯，您接近ASetXXX是死路一條。只需使用條件循環來確定您的跳轉何時返回到同一點。

i = startidx 
    do 
    i = A[i] 
    while (i != startidx)

對所有可能的操作進行該操作startidx。

標誌使用索引來避免過度的工作

來源

2017-06-21 09:07:29 MBo

我如何計算值A [A [i]]等等，而沒有過多的代碼，如何我能預測它嗎？ –

請考慮給定的僞代碼。應用於'[5,4,0,3,1,6,2]'陣列，使用鉛筆和紙。 – MBo

對我來說，它看起來像：而我！= startidx {i = A [i]; i ++} 不會這只是通過一維數組循環，我不知道你會設置startidx。 –

我知道這是回答，但因爲它是有趣的爲我解決任務自己，爲什麼不能在這裏發表我的解決方案。

這個想法是在原始數組內存儲設置序列長度（任務描述允許）。

在訪問Set元素時，我們用集合中的順序替換值，但帶負號。基本上，我們可以簡單地用-1來代替數值。

只要訪問了一個Set，我們就會移動到另一個Set。

時間複雜度是線性的。存儲的複雜性是不變的。

解決方案在C++：

#include <iostream> 
#include <string> 
#include <stack> 
#include <vector> 

int solve(std::vector<int>& i_arr) 
{ 
    int ret = 0; 
    for (int i = 0, sz = i_arr.size(); i < sz; ++i) // sequences beginnings searching loop 
    { 
     if (i_arr[i] < 0) // already visited, thus not the sequence beginning 
      continue; 
     for (int j = i, c = 0;;) // sequence elements iteration loop 
     { 
      int val = i_arr[j]; 
      if (val >= 0) // not the sequence end, continue sequence iteration 
      {     
       i_arr[j] = --c; // replacing value with order in sequence but negative 
       j = val; // moving to the next element in sequence 
      } 
      else // sequence end reached, looping back... 
      { 
       if (c < ret) // detecting longest sequence 
        ret = c; 
       break; // current sequence end reached, breaking 
      } 
     } 
    } 
    return -ret; 
} 

int main() 
{ 
    std::vector<int> arr{5,4,0,3,1,6,2}; 
    std::cout << solve(arr) << std::endl; 
    for (const auto& e : arr) 
     std::cout << e << ' '; 
    return 0; 
}

這就是輸出的樣子（第二行給出了一個想法陣列如何原來被修改）：

4 
-1 -1 -4 -1 -2 -2 -3

來源

2017-06-28 09:55:23

Codility測試Java數組S = A [A [A [A [int]]]]？

回答

相關問題