You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:
n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ Because the 4th row is incomplete, we return 3.
首先理解题目的意思
给出一个数N，然后利用这个数去排列。
每行尽可能排满，第一行1个，第二行2个。。。。
返回排满的行数
首先列出看的见的等式。
（1+x）*x/2 + r = n;
其中x为最后有多少行，r为最后返回的结果，n为给出的数据。
//然后我们就把这个问题转换成了一个数学问题
也就是我们要计算出一个x要满足等式成立的情况下r最小。
如何找到这个x呢？
1、首先最简单的解法，枚举所有的x，直到r为负数为止，前一个x就是满足条件的。
所以最后的复杂度肯定是x+1，x为最终成立的行数，x为需要返回的结果。
还有更快的方法吗？
我的想法是，当r为0时，x可以从sqrt（n*2）向下取整，然后从这个数，按照方法1往上找。这个是n最大的情况
当r为x-1时，也就是n最小的情况。按照上面的方法也没错，因为这个数小，所以往上找也是可以的。
public class Solution { public int arrangeCoins(int n) { int x = (int) Math.floor(Math.sqrt(n*1.0)); int r = 0; while (true){ if(x%2 == 0) r = x / 2 * (1+x); else r = (1+x) / 2 * x; if(n - r < 0) break; else x++; } return --x; } }
其中要注意的是x的值过大时先要计算除法不然两个数相乘超过int就会出现一个极小数会影响判断。
当然还有更牛逼的方法
先不管r是多少，当做r是0，先利用解方程的方法n计算出来一个x
然后对这个x往小了取整数就可以了。
public class Solution { public int arrangeCoins(int n) { /* 数学推导 (1+k)*k/2 = n k+k*k = 2*n k*k + k + 0.25 = 2*n + 0.25 (k + 0.5) ^ 2 = 2*n +0.25 k + 0.5 = sqrt(2*n + 0.25) k = sqrt(2*n + 0.25) - 0.5 */ return (int) (Math.sqrt(2*(long)n+0.25) - 0.5); } }