时间戳

首页 > 解决方案 > JS 最小到目前为止回溯算法错误

javascript - JS 最小到目前为止回溯算法错误

问题描述

我正在尝试在 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}` );

标签： javascriptalgorithmbacktracking

解决方案

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

(3) 表示分配findMin( digits, n, k - 1, minSoFar )给本地值，从循环中返回最佳值。

推荐阅读