# C#LeetCode刷题之#441-排列硬币（Arranging Coins）

n 是一个非负整数，并且在32位有符号整型的范围内。

n = 5

¤
¤ ¤
¤ ¤

n = 8

¤
¤ ¤
¤ ¤ ¤
¤ ¤

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.

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

```public class Program {

public static void Main(string[] args) {
var n = 8;
var res = ArrangeCoins(n);
Console.WriteLine(res);

n = 18;
res = ArrangeCoins2(n);
Console.WriteLine(res);

n = 28;
res = ArrangeCoins3(n);
Console.WriteLine(res);

n = 38;
res = ArrangeCoins4(n);
Console.WriteLine(res);

n = 58;
res = ArrangeCoins5(n);
Console.WriteLine(res);

n = 68;
res = ArrangeCoins6(n);
Console.WriteLine(res);

}

private static int ArrangeCoins(int n) {
//暴力解法，此解法LeetCode超时未AC
var res = 0;
var value = (long)0;
while(n > (value = ComputerT(++res))) { }
if(n != value) res--;
return res;
//以下解法同理，但 LeetCode 可以 AC
//if(n == 0) return 0;
//for(long i = 1; ; i++) {
//    if(n >= (i + 1) * i / 2 && n < (i + 2) * (i + 1) / 2)
//        return (int)i;
//}
}

private static int ComputerT(int n) {
//抽出来是为了让程序结构更清晰
return (1 + n) * n / 2;
}

private static int ArrangeCoins2(int n) {
//按1、2、3、4、5这样一直减下去
//直到n小于或等于0时为止
var index = 1;
while((n -= index++) > 0) { }
//考虑上述循环中因为是 index++
//index最终被多加了一次
//真实的索引应该是 index - 1
index--;
//小于0时，最后一排不完整，所以再减1
if(n < 0) return index - 1;
//等于0时，最后一徘正好完整
return index;
}

private static int ArrangeCoins3(int n) {
/* 推导过程
*
* 说明=>x ^ 2 表示 x 的平方
* 公式1：a ^ 2 + 2 * a * b + b ^ 2 = (a + b) ^ 2
* 公式2：公差为1的等差数列的求和公式为 S = (1 + n) * n / 2
*
* 推导=>
* 设在第 k 行硬币排完，那么
* (1 + k) * k / 2 = n
* 展开并两边同时乘以 2
* k + k ^ 2 = 2 * n
* 两边同时 + 0.25
* k ^ 2 + k + 0.25 = 2 * n + 0.25
* 合并
* (k + 0.5) ^ 2 = 2 * n + 0.25
* 两边同时开根号
* k + 0.5 = Math.Sqrt(2 * n + 0.25)
* 两边同时 - 0.5，求出 k 的值
* k = Math.Sqrt(2 * n + 0.25) - 0.5
*/
//原来的 n 为int，直接 2 * n + 0.25 会导致值溢出
//所以用 (long)n 强转
return (int)(Math.Sqrt(2 * (long)n + 0.25) - 0.5);
//以下解法同理，但换了一种求 k 的方式
//具体推导过程请看以下博文
//https://blog.csdn.net/zx2015216856/article/details/81950377
//return (int)((Math.Sqrt(8 * (long)n + 1) - 1) / 2);
}

private static int ArrangeCoins4(int n) {
//解法思路同ArrangeCoins
//都属于暴力求解，但此解法效率略高，可AC
var x = (long)n;
var temp = (long)n;
while(x * x + x > 2 * temp) {
x = (x * x + 2 * temp) / (2 * x + 1);
}
return (int)x;
}

private static int ArrangeCoins5(int n) {
//基本思路同ArrangeCoins和ArrangeCoins4
var k = (int)(Math.Sqrt(2) * Math.Sqrt(n));
return k * (k + 1) <= 2 * n ? k : k - 1;
}

private static int ArrangeCoins6(int n) {
//二分法
//二分是对暴力解法的优化
//使得循环更快的靠近目标
var left = 0L;
var right = (long)n;
while(left <= right) {
var mid = left + (right - left) / 2;
var sum = mid * (mid + 1) / 2;
if(sum > n) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return (int)(left - 1);
}

}```

```3
5
7
8
10
11```