预期
使用 Integer.MAX_VALUE
可以一致地返回较大的数字以进行比较。
观察
Integer.MAX_VALUE
返回负数。
实现
在示例代码中,值被保存到二维表中,以便找到组成给定数量所需的最小硬币数量。
使用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("")
}
}
最佳答案
这是因为溢出。 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
关于Kotlin Integer.MAX_VALUE 返回负数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62524736/