LeetCode 441题 “Arranging Coins” 是一个中等难度的数学问题。题目描述如下：
你总共有 n 枚硬币，并希望将它们排列成一个阶梯形状，第 k 行必须正好有 k 枚硬币。
给你一个整数 n，返回你可以完整排列的行数。
示例 1:
输入: n = 5
输出: 2
解释:
因为第三行不完整，所以返回 2.
示例 2:
输入: n = 8
输出: 3
解释:
因为第四行不完整，所以返回 3.
解题思路
这个问题可以通过数学公式和二分查找来解决。
方法一：数学公式
我们知道，前 k 行需要的硬币总数是：
[ S = \frac{k(k + 1)}{2} ]
我们需要找到一个最大的 k，使得：
[ \frac{k(k + 1)}{2} \leq n ]
这可以通过解以下不等式得到： [ k^2 + k – 2n \leq 0 ]
使用求根公式：
[ k = \frac{-b \pm \sqrt{b^2 – 4ac}}{2a} ]
其中，a = 1，b = 1，c = -2n。
所以： [ k = \frac{-1 \pm \sqrt{1 + 8n}}{2} ]
我们取正根： [ k = \frac{-1 + \sqrt{1 + 8n}}{2} ]
最后取整即可。
方法二：二分查找
我们可以使用二分查找来找到最大的 k，使得：
[ \frac{k(k + 1)}{2} \leq n ]
初始化 left = 1，right = n，然后进行二分查找。
代码实现
方法一：数学公式
import math
def arrangeCoins(n: int) -> int: return int((-1 + math.sqrt(1 + 8 * n)) // 2)
示例
print(arrangeCoins(5)) # 输出: 2 print(arrangeCoins(8)) # 输出: 3
方法二：二分查找
def arrangeCoins(n: int) -> int:
left, right = 1, n
while left <= right:
mid = (left + right) // 2
current = mid * (mid + 1) // 2
if current == n:
return mid
elif current < n:
left = mid + 1
else:
right = mid - 1
return right
示例
print(arrangeCoins(5)) # 输出: 2 print(arrangeCoins(8)) # 输出: 3
总结
- 数学公式法：通过求解一元二次方程来直接计算结果，时间复杂度为 (O(1))。
- 二分查找法：通过二分查找逐步逼近结果，时间复杂度为 (O(\log n))。
两种方法各有优劣，数学公式法更直观且速度快，但可能存在浮点数精度问题；二分查找法更通用且精度高，但稍微复杂一些。
希望这些详细的解释和代码示例能帮助你理解和解决这个题目！如果有更多问题，欢迎继续提问。
发表回复