2021.10.10 - 119.排列硬币

• 1. 题目
• 2. 思路
• • (1) 数学法
  • (2) 二分查找
• 3. 代码

• 利用求根公式直接求出行数。

• 根据题目条件可知，n个硬币最少可形成1行（1个硬币），最多可形成n行（1个硬币），因此每次取中间行数计算其最多可包含的硬币数。
• 若硬币数小于等于n，则最小行数修改为中间行数；若硬币数大于n，则最大行数修改为中间行数减1。

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int arrangeCoins(int n) {
        return (int) ((-1 + Math.sqrt(1 + (long) 8 * n)) / 2);
    }
}

class Solution1 {
    public int arrangeCoins(int n) {
        int min = 1;
        int max = n;
        int mid;
        while (min < max) {
            mid = min + ((max - min + 1) >>> 1);
            if ((long) (1 + mid) * mid <= (long) n * 2) {
                min = mid;
            } else {
                max = mid - 1;
            }
        }
        return min;
    }
}