:-: 4.3 排列硬币 ***** **题干：** 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。 n 是一个非负整数，并且在32位有符号整型的范围内。 示例 1: ``` n = 5 硬币可排列成以下几行: ¤ ¤ ¤ ¤ ¤ 因为第三行不完整，所以返回2. ``` 示例 2: ``` n = 8 硬币可排列成以下几行: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ 因为第四行不完整，所以返回3. ``` **题目分析：** 由题目分析得我们返回的值是不完整的那一行的上一行的行数，且每行的硬币个数是当前的行数，且符合首项为1，公差为1的等差数列（a1 = 1,d = 1）,等差数列前n项和公式为Sn = n * a1 + (((n * (n - 1)) / 2) * d。 **新手有可能遇到的解题思路陷阱：** 返回值返回了当前不完整的行数中的硬币数，当正好排满时返回了当前的行数的上一行的行数，应该是下一行行数。 **解题思路分析以及代码实现：** 第一种思路：暴力破解：1.用当前硬币数减去从第一行至不完整行数的上一行的硬币数，每次成功减去则进行计数器累加，当硬币数小于当前行数，则输出计数器的值；2.根据等差数列求和公式，依次计算前n项和与输入的硬币数比较，当前n项和不大于输入的硬币数则计数器累加，当大于则返回计数器的值。 **为什么中间使用long类型？因为中间值的计算可能超过int类型所能表达的范围。以下同上。** **为什么 i 的取值范围小于Math.sqrt(sum * 2)？因为Sn = (n^2 + n) / 2,但是n不能确定，所以sum = n^2 / 2代替。或者直接将 i <= Math.sqrt(sum * 2)的限制条件去除掉（for (int i = 1; ; i++)）** 第一种思路代码一： ``` public int arrangeCoins(int n) { long sum = n; int result = 0; for (int i = 1; i <= Math.sqrt(sum * 2); i++) { if (n < i) { break; } n = n - i; result++; } return result; } ``` 第一种思路代码二： ``` public static int arrangeCoins(int n) { long sum = n; int result = 0; for (long i = 1; i <= Math.sqrt(sum * 2); i++) { if (((i * i + i) / 2) > n) { return result; } result++; } return result; } ``` **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 第二种思路：二分法，找出前i行之和刚好大于n的临界点值，怎么找出这个值？还是使用等差数列前n项和公式。 **为什么使用low + (high - low) / 2而不使用(high + low) / 2呢？ 防止溢出！解释：看下面两个问题的答案就好了，解释的很清楚。** [low+(high-low)/2 is cheaper than (low+high)/2 ](https://stackoverflow.com/questions/38395275/lowhigh-low-2-is-cheaper-than-lowhigh-2) [Why in Java (high + low) / 2 is wrong but (high + low) >>> 1 is not?](https://stackoverflow.com/questions/13785210/why-in-java-high-low-2-is-wrong-but-high-low-1-is-not) **为什么(low + high) >>> 1会有一个这样的替代呢？为什么不是(low + high) >> 1它呢？ 因为 >>> 无符号，>> 有符号！中文版解释：看下面这个问题的答案就好了，解释的很清楚。** [为什么在 Java 中用 (low+high)>>>1 代替 (low+high)/2 或 (low+high)>>1 来计算平均值呢？](https://www.zhihu.com/question/20101702) 第二种思路代码： ``` public int arrangeCoins(int n) { if (n <= 1) return n; long low = 0, high = n; while (low <= high) { /* long mid = (low + high) >>> 1; */ long mid = low + (high - low) / 2; if ((mid * (mid + 1)) >>> 1 <= n) low = mid + 1; else high = mid - 1; } return (int) (low - 1); } ``` **复杂度分析：** 时间复杂度：O(n)。 空间复杂度：O(1)。 第三种思路：二元一次方程求解。a * x^2 + b * x + c = 0； :-: 或者 上述问题首项为1，公差为1的等差数列（a1 = 1,d = 1）,等差数列前n项和公式为Sn = n * a1 + (((n * (n - 1)) / 2) * d可化简为Sn = (n^2 + n) / 2,我们把输入的硬币数当作常数c，则代入以上方程求解（求前n项和是当前输入硬币数的n（有可能不是整数）），且我们的数都是正数，所以我们的解也只要正数解，又因为返回的可能带有小数，我们又是获得不完整行数的上一行的行数，也就是说忽略掉小数，只保留正整数就可以了。 第三种思路代码： ``` public int arrangeCoins(int n) { /* return (int) (Math.sqrt(1 + 8 * (long) n) - 1) / 2; */ return (int) (Math.sqrt(2 * (long) n + 0.25) - 0.5); } ``` **复杂度分析：** 时间复杂度：O(1)。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**