本文主要是介绍Arranging Coins，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：https://leetcode.com/problems/arranging-coins/
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 = 5The coins can form the following rows:
¤
¤ ¤
¤ ¤Because the 3rd row is incomplete, we return 2.Example 2:
n = 8The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤Because the 4th row is incomplete, we return 3.题目理解起来还是比较容易的，就是看一下等差数列 1,2,3,4,......，i 的和，等差数列前 i 项和公式：
在本题目中，我们做的其实就是 a1=1 ， d=1 的情况，于是有：
Si=i(i+1)2
我们要确定的就是 Si 刚好小于硬币个数n时候的i，也就是等差数列的第i项，于是有：
Si<=n<Si+1⇒
i(i+1)2<=n<(i+1)(i+2)2⇒
i(i+1)<=2n<(i+1)(i+2)
于是我们代码可以这么写：
public class ArrangingCoins {public static int arrangeCoins(int n) {for (int i = 1; i < n; i++) {if ((i * (i + 1) <= 2 * n) && ((i + 1) * (i + 2) > 2 * n))return i;continue;}return 0;}public static void main(String[] args) {// 超时报错System.out.println(arrangeCoins(1804289383));}
}可以看出，这个循环是从1开始的，如果n比较大的话，这个时间就玄乎了，有没有更快的方法呢？我们再看一下，现在知道了这个：
2n<(i+1)(i+2)⇒
2n<i2+3i+2⇒
2n+2<i2+4i+4=(i+2)2⇒
2n+2<(i+2)2⇒
i>2n+2−−−−−√−2
有了这个以后，那么我们前面的就不用算了，省的费那么多时间，于是代码实现为：
public class ArrangingCoins {public static int arrangeCoins(int n) {if (n <= 1)return n;int start = (int)Math.sqrt(n + 1) * (int)Math.sqrt(2) - 2;for (int i = start; i < n; i++) {if ((i * (i + 1) <= 2 * n) && ((i + 1) * (i + 2) > 2 * n))return i;continue;}return 0;}public static void main(String[] args) {System.out.println(arrangeCoins(1804289383));}
}这回就快多了。
这篇关于Arranging Coins的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
