🙋大家好！我是毛毛张!
🌈个人首页： 神马都会亿点点的毛毛张

今天分享的是LeetCode中一道标签为简单的算法题，本质是一道数学题

---

LeetCode链接：441. 排列硬币

---

1.题目描述

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

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

示例 1：

输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。

示例 2：

输入：n = 8
输出：3
解释：因为第四行不完整，所以返回 3 。

提示：

• $1<=n<=2^{31}-1$

2.题解

2.1 公式解法

class Solution {public int arrangeCoins(int n) {// 使用数学公式求解排列硬币问题// 使用 long 类型防止溢出long num = (long) n;// 计算公式：// 完整行数 k 满足的方程：k * (k + 1) / 2 <= n// 变形成：k^2 + k <= 2 * n// 转化为求解 k 的公式：k = (sqrt(8 * n + 1) - 1) / 2// 计算 k 的值，并将结果转换为 int 类型返回return (int) ((Math.sqrt(8 * num + 1) - 1) / 2);}
}

2.2 暴力解法

class Solution {public int arrangeCoins(int n) {// 初始化变量i为0，用于表示行数int i = 0;// 循环判断能够放多少行完整的硬币while (i <= n) {// 增加行数i++;// 计算当前行数需要的硬币总数，使用long类型防止溢出long coins = (long) i * (1 + i) / 2;// 如果当前行数需要的硬币总数大于n，退出循环if (coins > n) break;}// 返回完整行数的数量return i - 1;}
}

2.3 二分查找

class Solution {public int arrangeCoins(int n) {// 初始化二分查找的左边界和右边界int left = 1, right = n;// 使用二分查找寻找最大完整行数while (left <= right) {// 计算中间位置，防止整型溢出int mid = left + (right - left) / 2;// 计算当前中间位置能放的硬币总数，使用 long 类型防止溢出long num = (long) mid * (1 + mid) / 2;// 如果 n 小于当前总数，则说明完整行数过多，缩小右边界if (n < num) {right = mid - 1; // 修正为 right} else {// 否则，说明当前行数可以放下 n，增加左边界left = mid + 1;}}// 返回右边界，即最大完整行数return right; // 返回完整行数}
}