《LeetCode之每日一题》:174.排列硬币

有关题目

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

提示：1 <= n <= 2^31 - 1

题解

法一：迭代
代码一：

//n - ans 表示n 减去 上一次答案,必须要大于等于 1，这样根据阶梯的递增加一，才有满足条件的新的一行阶梯
class Solution {
public:int arrangeCoins(int n) {int ans = 0;while(n - ans > 0){n -= ++ans;}return ans;}
};

代码二：

//sum > n跳出循环，由于++i，所以跳出循环的i 先 减去 1，由于sum > n 说明上一步的sum += i中的i 太大了，故再减一
class Solution {
public:int arrangeCoins(int n) {int i = 1;long sum = 0;while(sum <= n){sum += i;++i;}return i - 2;}
};

时间复杂度：O(n)
空间复杂度：O(1)

法二：二分查找
参考官方题解
Tips

等差数列求和公式变形

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

法三：数学
参考官方题解

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

时间复杂度：sqrt跟CPU指令有关，这里不做研究
空间复杂度：O(1)