LeetCode441 排列硬币

发表于

这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战。

题目描述：

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

示例一

image.png

1
2
3
ini复制代码输入： n = 5
输出： 2
解释： 因为第三行不完整，所以返回 2 。

示例二

image.png

1
2
3
ini复制代码输入： n = 8
输出： 3
解释： 因为第四行不完整，所以返回 3 。

提示：

  • 1 <= n <= 2^31 - 1

思路分析

二分法

我们知道第 i 行必须 正好 有 i 个硬币（最后一行除外），再根据数学法，我们知道，到第 i 行时总共使用的硬币数量为 total=i(i+1)/2

所以现在我们的目标就是要寻找这么一个 i 使用得 total 小于或等于 n，而且 i 介于 1 和 n 之间。

除去暴力法，我们很容易就想到二分法了。

这里我们假设左边界为 1，右边界为 n,这里取中的时候有个小细节，我们要让结果更靠近右边界，所有有个 +1 的操作，直接上代码。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Kotlin复制代码class Solution {
    fun arrangeCoins(n: Int): Int {
        var left = 1
        var right = n
        while(left < right) {
            val mid = (right - left + 1)/2 + left
            if(mid.toLong() * (mid + 1) / 2 <= n ) {
                left = mid
            }else {
                right = mid - 1
            }
        }
        return left
    }
}

总结

虽然是二分法，但是这里的 +1 非常的关键，平常的二分法其实偏左偏右都可以，但是这题要取偏右的，不然如果就剩2个点的时候，mid = left，就会死循环，如果不 +1 ，这一题的答案也会因为死循环超时的。

参考

排列硬币 - 排列硬币 - 力扣（LeetCode） (leetcode-cn.com)

【宫水三叶】一题双解 :「数学」&「二分」 - 排列硬币 - 力扣（LeetCode） (leetcode-cn.com)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%