441. 排列硬币

English Version

题目描述

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

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

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

示例 1:

n = 5

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤

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

示例 2:

n = 8

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

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

解法

1. 数学推导

(1 + x) * x / 2 <= n，求解 x。

(x + 1/2)² <= 2n + 1/4，即 x <= sqrt(2n + 1/4) - 1/2。

由于 2n 可能溢出，故转换为 x <= sqrt(2) * sqrt(n + 1/8) - 1/2。

2. 二分查找

Python3

class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int(math.sqrt(2) * math.sqrt(n + 0.125) - 0.5)

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = (left + right + 1) >> 1
            s = ((1 + mid) * mid) >> 1
            if n < s:
                right = mid - 1
            else:
                left = mid
        return left

Java

class Solution {
    public int arrangeCoins(int n) {
        return (int) (Math.sqrt(2) * Math.sqrt(n + 0.125) - 0.5);
    }
}

class Solution {
    public int arrangeCoins(int n) {
        long left = 1, right = n;
        while (left < right) {
            long mid = (left + right + 1) >> 1;
            long s = ((1 + mid) * mid) >> 1;
            if (n < s) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return (int) left;
    }
}

C++

using LL = long;

class Solution {
public:
    int arrangeCoins(int n) {
        LL left = 1, right = n;
        while (left < right)
        {
            LL mid = left + right + 1 >> 1;
            LL s = (1 + mid) * mid >> 1;
            if (n < s) right = mid - 1;
            else left = mid;
        }
        return left;
    }
};

Go

func arrangeCoins(n int) int {
	left, right := 1, n
	for left < right {
		mid := (left + right + 1) >> 1
		s := (1 + mid) * mid >> 1
		if n < s {
			right = mid - 1
		} else {
			left = mid
		}
	}
	return left
}

...