每日一题(9)

每日一题(9)

题目：排列硬币

题目描述

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

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

解题思路

1. 可以通过累加求和的方法，当和大于给定的硬币数量时停止
2. 根据求和公式列一元二次方程，对方程进行求解
3. 二分法，总行数只可能在1~n之间，通过求和公式来比较大小，得到最终的结果

代码

class Solution {
public:int arrangeCoins(int n) {int i=0;long sum=0;for(;;++i){sum+=i;if(sum>n){break;}}return i-1;}
};

class Solution {
public:int arrangeCoins(int n) {return (int) ((sqrt((long long) 8 * n + 1) - 1) / 2);}
};

class Solution {
public:int arrangeCoins(int n) {int left=1,right=n;while(left<right){int mid=(right-left+1)/2+left;if((long long)mid*(mid+1)<=(long long)2*n){left=mid;}else{right=mid-1;}}return left;}
};