Leetcode之二分法专题-441. 排列硬币（Arranging Coins）

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

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

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

示例 1:

n = 5

硬币可排列成以下几行:

¤

¤ ¤

¤ ¤

因为第三行不完整，所以返回2.

示例 2:

n = 8

硬币可排列成以下几行:

¤

¤ ¤

¤ ¤ ¤

¤ ¤

因为第四行不完整，所以返回3.

读题，问题可以转化为：求最后一列完整的行数。
首先第一步，根据等差数列公式Sn=(a1+an)*n/2，a1=1,an=a1+(n-1)，得到Sn*2=(1+n)*n
在我们后续的式子中，用n代替Sn，用mid代替n

那么我们可以写出二分规则：
如果mid*(mid+1)>2*n的话，证明第mid行是不够数量的，所以不需要保留，R = mid - 1
否则，第mid行可能够也可能小于，所以我们保留，并取右边，L = mid

class Solution {

    public int arrangeCoins(int n) {

        int L = 0;

        int R = n;

        while(L<R){

            int mid = (L+R+1)>>>1;

            if((long)(Math.pow(mid, 2)+mid)>(long)2*n){

                R = mid-1;

            }else{

                L = mid;

            }

        }

        return L;

    }

}

巴特西

Leetcode之二分法专题-441. 排列硬币（Arranging Coins）

最新文章

热门文章