题目
你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。给定一个数字 n,找出可形成完整阶梯行的总行数。n 是一个非负整数,并且在32位有符号整型的范围。
- 示例1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整,所以返回2.
- 示例2:
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整,所以返回3.
解法1:直接排列
NSInteger maxRowCountWithCoins1(NSInteger coins) {
NSInteger leftCoins = coins;
NSInteger rowCount = 0;
while (leftCoins >= rowCount) {
rowCount += 1;
// 按行数减去相应值
leftCoins -= rowCount;
if (leftCoins < 0) {
// 不够数,减1
rowCount -= 1;
}
}
return rowCount;
}
解法2:数学公式
NSInteger maxRowCountWithCoins2(NSInteger coins) {
// 公式法,由于是等差数列(1,2,3...n,和为coins),使用等差数列求和公式,算出最小的整数n,即为行数
// 1. 等差数列求和公式为:((A1 + An) * n) / 2 = Sn,带入公式,得
// ((1 + n) * n) / 2 = coins
// 变形得 n^2 + n - 2 * coins = 0,可知此为一元二次方程
// 2. 根据一元二次方程的求根公式,x = (-b +- sqrt(b^2 - 4ac)) / 2a,带入公式,得
// n = (-1 +- sqrt(1 + 8 * coins)) / 2
// 变形,得 n = sqrt(0.25 + 2 * coins) - 0.5
// 3. 故只要求出最小的正整数n即可
return (NSInteger)(sqrt(0.25 + 2 * coins) - 0.5);
}
网友评论