LeetCode : 441. Arranging Coins布置金币-蒲公英云

LeetCode : 441. Arranging Coins布置金币

桃扇骨 2021-06-24 16:12 465阅读 0赞

试题
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.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.
Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.
代码
这一题可以看成1-n之间存在一个映射数组[1,…,(n+1)*n/2]，而我们就是要找这个数组中小于n的最大整数。

class Solution {
    public int arrangeCoins(int n) {
        if(n==0) return 0;
        long left = 1, right = n/2+1;
        while(left < right){
            long mid = left + (right - left) / 2;
            long value = (mid + 1) * mid / 2;
            if(value == n){
                return (int)mid;
            }else if(value < n){
                left = mid + 1;
            }else if(value > n){
                right = mid - 1;
            }
        }
        return (int)((left+1)*left/2<=n?left:left-1);
    }
}