排列硬币

题目形容:你总共有 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));    }}
【每日寄语】 凡事若等今天做,时机便从眼前过。