AlgoPressAppearance
题目描述
https://leetcode.cn/problems/arranging-coins 你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。
示例 1：
输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。
示例 2：
输入：n = 8
输出：3
解释：因为第四行不完整，所以返回 3 。
提示：
- 1 <= n <= 2^31 - 1
思路1：模拟计算
时间复杂度 O(n)
csharp
public class Solution {
public int ArrangeCoins(int n) {
for(int i=1; i<=n; i++){
n = n - i;
if(n <= i){ //不够了
return i;
}
}
return 0;
}
}
思路2:二分查找
使用公式求出中间 mid 需要的耗费硬币数
csharp
//二分查找，用公式求出中间 mid 需要耗费的硬币数
public static int arrangeCoin2(int n){
int left = 0, right = n;
while(left <= right){
int mid = left + (right - left) / 2;
int target = ((mid+1) * mid) / 2;
if(target == n){
return mid;
}
else if(target > n){
right = mid-1;
}
else{
left = mid+1;
}
//没找到就返回右边指针
return right;
}
}
思路3：牛顿迭代
csharp
//double res = (x + (2*n-x)/x) /2;
public class Solution {
public int ArrangeCoins(int n) {
return (int) ((Math.Sqrt((long) 8 * n + 1) - 1) / 2);
}
}