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

问题

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

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

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.

示例

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);

        Console.ReadKey();

    }

    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);

    }

}

以上给出6种算法实现，以下是这个案例的输出结果：

分析：

显而易见，ArrangeCoins、ArrangeCoins2、ArrangeCoins4、ArrangeCoins5的时间复杂度均为： C#LeetCode刷题之#441-排列硬币（Arranging Coins）-LMLPHP ，ArrangeCoins3的时间复杂度基于 Math.Sqrt() 的实现，ArrangeCoins6的时间复杂度为：。