排列硬币
一、题目描述
总共有n和硬币,并计划将它们按阶梯状排列。对于一个有k行组成的阶梯,其第i行必须正好有i枚硬币。阶梯的最后一行可能是不完整的。
给定一个数组n,计算并返回可形成完整阶梯行的总行数。
示例1
输入:n = 5
输出:22
输入:n = 8
输出:3
二、解题思路
类似于如下形式
1
11
111
1111
使用求和公式n=[k(k+1)]/2,k就是阶数,k从1开始,因为在n>=1的情况下,最少也有1阶。
三、解题方法
方法1(二分查找)
使用二分查找在1-n内与k值,即可。
代码实现
class Solution {
public int arrangeCoins(int n) {
int left = 1;
int rignt = n;
while(left < rignt){
int mid = (rignt - left +1)/2 + left;
if((long) mid *(mid +1) <= (long)2*n ){
left = mid;
}else{
rignt = mid -1;
}
}
return left;
}
}
标签:排列,硬币,int,mid,rignt,left
From: https://www.cnblogs.com/zjjtt/p/16944344.html