关于java:LeetCode441排列硬币

排列硬币

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

给定一个数字 n，找出可造成残缺阶梯行的总行数。

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

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：穷举法

简略的累加，直到大于n为止，最初返回相应的层数。这种办法效率太低，n很大时会超时。

解法二：二分查找法

首先，上上限low和high别离是最大和最小的层数，最大值依据 n = x * (x + 1) / 2 估算失去，而后利用二分查找法找到最多能够放到第几层，最初返回层数即可。

public class LeetCode_441 {
    /**
     * 穷举法，n超大时会超时，效率不高
     *
     * @param n
     * @return
     */
    public static int arrangeCoins(int n) {
        int sum = 0, rows = 0;
        for (int i = 1; ; i++) {
            if (sum + i > n) {
                break;
            }
            sum += i;
            rows++;
        }
        return rows;
    }

    /**
     * 二分查找法
     *
     * @param n
     * @return
     */
    public static int arrangeCoins2(int n) {
        // low和high别离是最大和最小的层数，最大值依据 `n = x * (x + 1) / 2` 估算失去
        int low = 1, high = (int) Math.sqrt(Double.valueOf(Integer.MAX_VALUE) * 2), mid = -1;
        // 利用二分查找法找到最多能够放到第几层
        while (low <= high) {
            mid = (low + high) / 2;
            double temp = (double) mid * (mid + 1) / 2;
            if (temp > n) {
                high = mid - 1;
            } else if (temp < n) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        double temp = (double) mid * (mid + 1) / 2;
        if (temp > n) {
            return mid - 1;
        } else {
            return mid;
        }
    }

    public static void main(String[] args) {
        // 测试用例一，冀望输入： 2
        System.out.println(arrangeCoins2(5));
        // 测试用例二，冀望输入： 3
        System.out.println(arrangeCoins2(8));
        // 测试用例三，冀望输入：65535
        System.out.println(arrangeCoins2(2147483647));
        // 测试用例三，冀望输入：60070
        System.out.println(arrangeCoins2(1804289383));
    }
}

【每日寄语】 凡事若等今天做，时机便从眼前过。