kotlin - Kotlin Integer.MAX_VALUE返回负数

Question

预期
为了比较目的，使用Integer.MAX_VALUE可以一致地返回大量数字。
观测到的Integer.MAX_VALUE返回负数。
实行
在示例代码中，将值保存到2D表中，以便找到组成给定数量所需的最小硬币数量。
使用Integer.MAX_VALUE-2147483647是从Integer.MAX_VALUE派生的。

fun main() {
// Steps - Iterative/bottom-up
//     1. Create a 2D table: Rows = Denominations(Denoms), Columns = Amount(Amt)
//     2. Store min # of coins in at [R][C] = Min(currentDenomMin, previousDenomMin)
//         a. currentDenomMin = [R][C - coins.get(R)] + 1
//         b. previousDenomMin = [R - 1][C]
//     3. Return minCount or -1 for table[coins.size - 1, Amt].
    println("Min count: ${coinChange(intArrayOf(2), 3)}")
}

lateinit var table: Array<IntArray>
lateinit var mCoins: IntArray
private val maxValue = Integer.MAX_VALUE
fun coinChange(coins: IntArray, amt: Int): Int {
    table = Array(coins.size, { IntArray(amt + 1) })
    mCoins = coins
    coins.sort()
    buildMinCounts(amt)
    val minCount = table[coins.size - 1][amt]
    return if (minCount == maxValue) -1 else minCount

}

fun buildMinCounts(amt: Int) {
    for (r in 0..mCoins.size - 1) {
        for (c in 0..amt) {
            val currentDenomValue = mCoins.get(r)
            val currentDenomMin = getDenomMin(r, c - currentDenomValue) + 1
            val previousDenomMin = getDenomMin(r - 1, c)
            if (c == 0) {
                table[r][c] = 0
            } else table[r][c] = Math.min(currentDenomMin, previousDenomMin)
        }
    }
}

fun getDenomMin(r: Int, c: Int): Int {
    if (r < 0 || c < 0) return maxValue
    else return table[r][c]
}

fun printT(amt: Int) {
    for (r in 0..mCoins.size - 1) {
        for (c in 0..amt) {
            print("${table[r][c]} ")
        }
        println("")
    }
}

改用 999999999作为 maxValue可以正常工作。

fun main() {
    println("Min count: ${coinChange(intArrayOf(2), 3)}")
}

lateinit var table: Array<IntArray>
lateinit var mCoins: IntArray
private val maxValue = 999999999
fun coinChange(coins: IntArray, amt: Int): Int {
    table = Array(coins.size, { IntArray(amt + 1) })
    mCoins = coins
    coins.sort()
    buildMinCounts(amt)
    val minCount = table[coins.size - 1][amt]
    return if (minCount == maxValue) -1 else minCount

}

fun buildMinCounts(amt: Int) {
    for (r in 0..mCoins.size - 1) {
        for (c in 0..amt) {
            val currentDenomValue = mCoins.get(r)
            val currentDenomMin = getDenomMin(r, c - currentDenomValue) + 1
            val previousDenomMin = getDenomMin(r - 1, c)
            if (c == 0) {
                table[r][c] = 0
            } else table[r][c] = Math.min(currentDenomMin, previousDenomMin)
        }
    }
}

fun getDenomMin(r: Int, c: Int): Int {
    if (r < 0 || c < 0) return maxValue
    else return table[r][c]
}

fun printT(amt: Int) {
    for (r in 0..mCoins.size - 1) {
        for (c in 0..amt) {
            print("${table[r][c]} ")
        }
        println("")
    }
}

Answer 1

这是因为溢出。 getDenomMin(r, c - currentDenomValue) + 1返回会导致溢出的Integer.MAX_VALUE + 1。有两种方法可以避免这种情况:

将maxValue更改为不会溢出并且实际上是最大的值。例如，您有一个大小为10 ^ 5的数组，其中包含1到10 ^ 9之间的整数。现在最大可能的和为10 ^ 5 * 10 ^ 9，即10 ^ 14，因此我们可以将maxValue设置为大于或等于10 ^ 14的任何值。在您的情况下，您可以将其设置为10 ^ 5之类的值，因为您不需要计数就可以达到最大可用硬币数之和。

val currentDenomMin = getDenomMin(r, c - currentDenomValue) + 1在添加1之前，可以将其键入Long，以免溢出。val currentDenomMin = getDenomMin(r, c - currentDenomValue).toLong + 1