JS Minimum So Far 回溯算法 Bug

Question

我正在尝试在 JS 中实现一个回溯算法，通过交换 k 个数字来找到可能的最小值。

我不明白为什么我的代码不起作用。如果我注销 num 的值，它会下降到 159 但由于某种原因，它不会作为 minSoFar 返回。

有什么想法吗？

function swap( arr, i, j ) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function findMin( digits, n, k, minSoFar ) {
    // Compare current number with minimum number so far
    const num = parseInt( digits.join( '' ) );

    if ( num < minSoFar ) {
    minSoFar = num;
    }

    // base case - no more swaps allowed.
    if ( k < 1 ) {
    return minSoFar;
    }


    // For each digit in the input string
    for ( let i = 0; i < n - 1; i++ ) {
    // compare the current digit with remaining digits
    for ( let j = i + 1; j < n; j++ ) {
        // if digit at i'th index is more than the digit at j'th index
        if ( digits[i] > digits[j] ) {
        // swap digits i and j
        swap( digits, i, j );

        // recur for remaining k - 1 swaps
        findMin( digits, n, k - 1, minSoFar );

        // backtrack - restore the string back
        swap( digits, i, j );
        }
    }
    }
    return minSoFar;
}

let i = 951;
let k = 2;
let digits = Array.from( String( i ), Number );
let minimum = findMin( digits, digits.length, k, i );
console.log( `The minimum number formed by doing at most ${k} swaps is ${minimum}` );

Answer 1

它无法 return 正确，因为分配的 minSoFar 是它所在的递归框架的本地值。要么 (1) 使 minSoFar 成为递归的全局值，要么 (2) 使其成为对象中的值并传递对象（因为它们是通过引用传递的，递归框架将修改相同的值），或者（3）实际比较 returned min 而不是尝试分配它。

(3) 表示将 findMin( digits, n, k - 1, minSoFar ) 分配给本地值，return 从循环中取最好的值。

JS Minimum So Far 回溯算法 Bug

JS Minimum So Far Backtracking Algorithm Bug

javascript

algorithm

backtracking