我给大家分享 LeetCode 算法题，主要都是挑选那些很可能在面试中出现的题，或者可能出现类似的题，多看看这些题至少能够在面试中不那么被动。
今天给大家分享的 LeetCode 算法题和硬币相关：如何排列硬币，一起来看一看。
题目：
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。n 是一个非负整数，并且在32位有符号整型的范围。
示例1：
n = 5 硬币可排列成以下几行: ¤ ¤ ¤ ¤ ¤ 因为第三行不完整，所以返回2.
示例2：
n = 8 硬币可排列成以下几行: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ 因为第四行不完整，所以返回3.
题目结合示例，很好理解。这里主要给大家分享三个解题方法。
1. 直接干
为什么说直接干呢？拿到这个题，第一反应是，我从第一行开始往上加，等加到 n 的时候就结束，或者大于 n 的时候就结束即可。
这个思路没有问题，但是需要考虑一个小坑在里面，那就是数据溢出的问题，因为从 1 往上加的话，有可能最后一行加了之后，就超出整数范围了，就会变成负数，所以需要注意一下溢出问题。下面给出我的代码：
public int arrangeCoins(int n) { int layer = 1; int layerTmpt = 1; int result = 1; while(result < n) { layerTmpt++; // 说明溢出 if (layerTmpt < 0) { return layer; } result += layerTmpt; // 说明溢出 if (result < 0) { return layer; } layer++; } if(result == n) { return layer; } else { return layer - 1; } }
2. 逆向思维
从刚刚我们分析中可知，如果从 1 开始往上加，会有可能造成数据溢出，那么我们可以反过来考虑，如果我们用 n 从 1 开始减呢？是不是就不存在溢出问题了？答案是肯定的。
public int arrangeCoins(int n) { int layer = 0; for (int i = 1; i <= n; ++i) { n -= i; if (n < 0) { return layer; } else { layer++; } } return layer; }
这样的话，代码明显就简洁多了。如果面试官看到这种代码，肯定会更加满意。
3. 用数学公式
这种就没啥好说的了，根据题目意思，排列的硬币符合等差数列，1+2+3+...+x <= n，假设相等，先求出解，然后向下取整即可。
public int arrangeCoins(int n) { return (int) (Math.sqrt((long) n * 2 + 0.25) - 0.5); }
这就很魔性了，一行代码写完了，不过这是基于数学公式来做的。
