-1

好的...我需要检查一个数组是否是一个完整的链。我会告诉你这意味着什么：

我有 arr [5, 3, 2, 0, 4, 1]。N（数组大小）= 6，N-1 = 5。所以数组应该包含数字 0-5。然后我们从 arr[0] 开始。

arr[0] = 5，所以我们转到 arr[5]= 1，arr[1] = 3，arr[3] = 0，这又回到了 arr[0]。

由于这个数组没有去每个号码，它不是一个完整的链。我希望这是有道理的，哈哈。

我应该在 java 中编写一个从 arr[0] 开始并像我说的那样经过的方法，如果它命中数组中的每个数字，它就是完整的链（真）。如果它回到它已经命中的数字，它不是（假的）。

我理解这背后的逻辑......我只是无法实现它。我不知道如何使用循环来跟踪数字和索引......（我们应该使用循环）。

谁能帮我指出正确的方向？我不是在寻找代码，但如果有人能解释我如何用这个实现一个循环，那就太棒了！

4

5 回答 5

2

boolean[]如果我们第二次点击索引，我会使用辅助工具来告诉我们。由于您显然需要一种方法来存储您已经看到的元素，并且由于该结构在最坏的情况下会占用线性空间，因此您不妨使用它。我会这样做

public static boolean arrayIsCompleteChain(int[] array) {
    boolean[] visited = new boolean[array.length];
    int index = 0;
    int steps = 0;

    // stop once we visit an index twice
    while(!visited[index]) {
        visited[index] = true; // mark index as visited
        index = array[index];  // go to the next index
        steps++;               // count this step
    }

    // if we made one step for every index, then the array is a complete chain
    if(steps == array.length) {
        return true;
    } else {
        return false;
    }

    // for anyone reading this who thinks to himself the "if" construct is
    // unnecessary: this is for didactic purposes
}

请注意，此方法不对输入进行任何验证检查，即它是否包含会使索引超出范围的元素或数组本身是否为null. 如果你想要，这很容易做到。

于 2013-11-10T03:20:25.430 回答
0

您可以使用 for 循环在数组中进行迭代。这是一个例子：

int[] array = new int[4];
array[0] = 2;
array[1] = 5;
array[2] = 1;
array[3] = 8;

for(int i = 0; i<array.length; i++){
    System.out.println("The element in the array at position: "+ i +" is: " + array[i]);
}

怎么看，我先声明并初始化数组。在for循环中，首先我声明并初始化一个临时变量（这个变量将在for循环结束时被删除）为0（int i = 0）。接下来我为“for循环”（i < array.length）编写结束表达式，该表达式确定for何时结束，在这种情况下，for循环将继续运行，直到“i”小于数组.长度 (4)。接下来我将 temp 变量增加一 (i++)。

在这种情况下，for 循环的主体很简单（打印给定位置 (i) 中的数组元素）。但它可以是你想要对数组做的任何事情。

我希望你能理解。

PS：对不起我的英语。我的第一语言是西班牙语。:D

于 2013-11-10T02:38:40.067 回答
0

您希望为从您的链中掉出的元素设置一个计数器（初始化为 0）。您还需要一个与数组大小相同的布尔类型的数组。这种布尔类型的数组用于跟踪是否有重复元素。

为了使程序更快，在你的 for 循环中（用于迭代你的数组），当你找到一个超出你的链范围的元素时，你增加计数器并跳出循环。之后，您只需检查计数器是否 == 0。如果为 0，则您的链是完整的，否则不完整。我希望这有帮助。

如何检查元素是否超出范围？检查元素是否 >= array.length 或 < 0 （如果我理解你的问题正确）

我意识到你可能正在写作业或类似的东西，我省略了大部分代码让你自己处理。下面是我如何使用布尔类型的数组来跟踪元素元素：

int[] arrayToCheck = new int[]{5, 3, 2, 0, 1, 1};
boolean[] arrayMarker = new boolean[arrayToCheck.length];

int count = 0;  // count the number out of the chain

for (int i : arrayToCheck) {
    // here you need to write code to check the element i is within
    // your range, if not, increment counter, break out

    if (arrayMarker[i] != true) {
        arrayMarker[i] = true;
    } else {
        count++;
        break;
    }
}

boolean completeChain = (count == 0) ? true : false;
System.out.println("is completeChain: " + completeChain);
于 2013-11-10T03:16:03.130 回答
0

假设数字是唯一的：

public int sum(int[] arr) {
    int ret = 0;
    for (int i : arr) {
        ret += arr[i];
    }
    return ret;
}

int[] arr = { 5, 3, 2, 0, 4, 1 };
int tmp = arr[0];
int sum = 0;
for (int i = 0; i < arr.length; i++) {
    sum += arr[tmp];
    tmp = arr[tmp];
}
System.out.println(sum == sum(arr));
于 2013-11-10T03:17:15.210 回答
-1

我将描述一个方法，它在给定一个整数数组的情况下返回给定索引位置的值。

public static int getAtPosition(int nextPosition, int... elements) {
    return elements[nextPosition];
}

本质上，我使用的任何值nextPosition都用于索引到数组中。

接下来考虑，您正在nextPosition使用arr[0]to start 播种，如果与方法调用结合使用，则会导致下一个位置值为1.

您还正确地观察到它在振荡，这使其成为无效链。

现在，这里的技巧是选择一个数据结构来存储我们看到的元素，并防止我们再次触发重复。让我们使用 aSet<Integer>来完成此操作，因为我们可以add相对便宜，并且当且仅当此元素未添加到先前的集合中时Set，它返回的命令接口。true

public static boolean invalidChain(Set<Integer> values, int index) {
    return !values.add(index);
}

一个解释：

  • 给定一组整数，我添加刚刚看到的索引位置。
  • 如果索引位置被成功添加，我返回 false - 因为，成功add()意味着该值从未放入集合中。
  • 如果索引位置没有成功添加，我返回 true - 与上述相反的原因。

鉴于所有这些，您现在必须编写一个利用 booleaninvalidChain和 int的循环getAtPosition。提示： invalidChain是您应该在循环中检查的唯一条件。

于 2013-11-10T03:09:55.177 回答