北京市住房和城乡建设网站wordpress 开源模板

题意：

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 231 - 1

题目来源： https://leetcode.cn/problems/arranging-coins/description/

解题方法：

方法一：迭代递减

//迭代递减
function arrangeCoins($n) {for($i = 1; $i <= $n; $i++){$n -= $i;if($n == 0 || $n < $i+1){return $i;}}
}

方法二：二分法（利用）

// 等差数列{an}的通项公式为：an=a1+(n-1)d。前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2,d为公差
function arrangeCoins($n) {if($n == 1 || $n == 2){return 1;}$start = 1;$end = $n;while($start < $end){$mid = $start + intval(($end - $start + 1) / 2);$sum = ($mid * ($mid + 1)) / 2; //Sn=n(a1+an)/2 => n=$mid, a1=1, an=$midif($sum > $n){$end = $mid - 1;}else{$start = $mid;}}return $start;
}

方法三：数学，一元二次方程求根

// 数学，一元二次方程求根
function arrangeCoins($n) {return intval((pow(8 * $n + 1, 0.5) - 1) / 2);
}

参考：
作者：力扣官方题解
链接：https://leetcode.cn/problems/arranging-coins/solutions/1038396/pai-lie-ying-bi-by-leetcode-solution-w52c/
来源：力扣（LeetCode）