2

我正在解决这个问题，给我带来麻烦的部分问题表述如下：

一个。从索引 i=0 开始；

湾。跳转到索引 i=A[i];

C。如果当前索引 i 超出 [0..N-1] 的有效范围，则打印“Out”并停止；

d。否则，如果当前索引 i 是索引 N-1，则打印“完成”并停止；

e1。否则，重复步骤b；

e2。如果这样做会导致无限循环，请打印“Cyclic”并停止；

（所有输出都没有引号）

arr是一个非负整数数组：

let index = 0;
const seen = new Set([0]);
while (true) {
  index = arr[index];
  if (index > arr.length - 1) {
    console.log("Out");
    break;
  }
  if (index === arr.length - 1) {
    console.log("Done");
    break;
  }
  if (seen.has(index)) {
    console.log("Cyclic");
    break;
  }
  seen.add(index);
}

我在一些隐藏的测试用例上得到了 WA（错误答案），但我一辈子都想不出一个失败的测试用例。

  • 1 2 3 4 5 0->Done
  • 1 2 3 4 6 0->Out
  • 1 0 0->Cyclic

编辑：

我的 C++ 解决方案有完全相同的失败测试用例，一定是我的逻辑...

4

1 回答 1

1

I believe the issue is that the coded algorithm is not adhering to the requirement. Specifically e1 indicates to repeat step b which fetches the next value, and **if doing this** leads to an infinite loop then print "Cycle". The problem is that the code is actually doing it, rather than checking first...

So, as the current code is written, a test case of...

12344

...will return "Done" rather than "Cyclic"...

EDIT In the parlance code, this is what I'm suggesting (untested)...

let index = 0;
const seen = new Set([0]);
while (true) {
  index = arr[index];
  if (index > arr.length - 1) {
    console.log("Out");
    break;
  }
  if (index === arr.length - 1) {
    console.log("Done");
    break;
  }
  if (seen.has(index) || seen.has(arr[index])) {
    console.log("Cyclic");
    break;
  }
  seen.add(index);
}

EDIT #2 Upon getting a chance to test my previously untested code just above, I discovered that it did not capture the nuance of my point. So, in an effort to further clarify, below is the Current and Proposed algorithms, with sample cases to show the similarities and the difference.

The last case, where the cyclic entry is the final entry, is where step e2 reports "Cyclic" before step c is able to report "Done"...

Comments in the proposed() function show the steps of the algorithm...

function current( arr ) {
  let index = 0;
  const seen = new Set([0]);
  while (true) {
    index = arr[index];
    if (index > arr.length - 1) {
      console.log("Out");
      break;
    }
    if (index === arr.length - 1) {
      console.log("Done");
      break;
    }
    if (seen.has(index)) {
      console.log("Cyclic");
      break;
    }
    seen.add(index);
  }
}

function proposed( arr ) {
  // a. Start from index i=0;
  let index = 0;

  // b. Jump to index i=A[i];
  const seen = new Set( [ index ] );
  index = arr[ index ];

  while( true ) {
    // c. If the current index i is outside the valid bound of [0..N-1], print “Out” and stop;
    if ( index > arr.length - 1 ) {
      console.log( "Out" );
      break;
    }
    
    // d. Else if the current index i is index N-1, print “Done” and stop;
    if ( index === arr.length - 1 ) {
      console.log( "Done" );
      break;
    }
    
    // e1. Otherwise, repeat step b;
    seen.add( index );
    index = arr[ index ];
    
    // e2. If doing this leads to an infinite loop, print “Cyclic” and stop;
    if ( seen.has( arr[index] ) ) {
      console.log("Cyclic");
      break;
    }
  }
}

arr = [1,0,2];
console.log( arr );
current( arr );
proposed( arr );

arr = [1,2,3,4,5];
console.log( arr );
current( arr );
proposed( arr );

arr = [1,2,3,6,5];
console.log( arr );
current( arr );
proposed( arr );

arr=[1,2,3,4,0];
console.log( arr );
current( arr );
proposed( arr );

于 2022-02-06T15:54:53.967 回答