打印对堆进行排序所需的最少步骤数

Question

我正在尝试解决这个问题：

Playing Disks:

DJ Varun works in a club and plays cool songs. He has N disks of different albums (each of equal radius). Every disk has a distinct number out of 1 to N associated with it.

Disks are placed one over the other in a single pile. Varun wants to sort this pile of disks in an increasing order i.e. top to bottom. But he has a very special method of doing this.

In a single step he can only choose one disk out of the pile and he can only put it at the top. So the task here is that Varun wants to sort his pile of disks in minimum number of possible steps. What is the minimum number of possible steps to sort the pile so that that Varun can check whether he is doing his work right or wrong?

Input Format: First line contains integer N, the size of the array followed by, an array of size N containing integers 1 to N in any random order which shows the position of disks top to bottom.

Constraints: 0<=N<=1000

Output Format: Print the Minimum number of steps needed to sort the pile. If it can't be sorted then return output as -1.

Sample TestCase 1

Input:
3
1
3
2
Output:
2

到目前为止我的解决方案只得到 20%，我至少需要 60%：

var input_stdin_array = ['3' , '1' , '3' , '2'];

//convert into number
input_stdin_array = input_stdin_array.map(i=>Number(i))

//remove lenght
input_stdin_array.splice(0,1);

var Total = input_stdin_array.length;
var noOfSwap = Total - 1;

var noOfSeq = 0;
var lastIndex = 0;
var currentValue = 0;
var perviousValue = 0;
for(var i=0; i< input_stdin_array.length;i++)
{

var maxNum = Math.max(...input_stdin_array);
var indexOfMax = input_stdin_array.indexOf(maxNum);
if(i == 0)
{
    currentValue = maxNum;
}
    
if(indexOfMax != 0 )
{
    if(i == 0)
        lastIndex = indexOfMax - 1;
    else
        lastIndex-=1;

    console.log('Last index',lastIndex);

    if(lastIndex >= 0)
    {
        perviousValue = input_stdin_array[lastIndex];
        var checkValue = currentValue -1;
        currentValue = checkValue;
        console.log('Previous ',perviousValue, ' Checkvalue ',checkValue);
        if(i != 0)
        {
            if(perviousValue == checkValue)
            {
                noOfSeq++;
            }
        }
        
    }
}
}
// noOfSeq +=1;
console.log("NO of seq ",noOfSeq);
noOfSwap = noOfSwap - noOfSeq;
noOfSwap = noOfSwap == 0 ? -1 : noOfSwap;
console.log("no of swp ",noOfSwap);

Answer 1

我们可以做一些观察：

如果我们将值 i 移动到顶部，我们确信我们必须至少再移动 i-1 次。例如，如果我们将 3 移动到顶部，那么我们肯定必须在其后移动 2 和 1。
我们永远不应该将最大值移到顶部
如果只有一个最大值比最大值更靠近顶部，则该值也不应移至顶部，...等等

这导致了这个非常简单的算法：

function numSteps(arr) {
    let find = arr.length;
    for (let i = arr.length - 1; i >= 0; i--) {
        if (arr[i] == find) find--;
    }
    return find;
}

// I/O handling

let output = document.querySelector("span");
let input = document.querySelector("textarea");

input.addEventListener("input", refresh);

function refresh() {
    let arr = input.value.match(/\d+/g).slice(1).map(Number);
    let result = numSteps(arr);
    output.textContent = result;
}

refresh();

div { float: left; margin: 5px }

<div>Input:<br>
<textarea rows=10 cols=5>3
1
3
2
</textarea></div>
<div>Output:<br>
<span></span></div>

打印对堆进行排序所需的最少步骤数

Print the Minimum number of steps needed to sort the pile

javascript

algorithm

sorting

data-structures

towers-of-hanoi