你总共有 n 枚硬币,并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯,其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
给你一个数字 n ,计算并返回可形成 完整阶梯行 的总行数。
示例 1:
输入:n = 5
输出:2
解释:因为第三行不完整,所以返回 2 。
示例 2:
输入:n = 8
输出:3
解释:因为第四行不完整,所以返回 3 。
提示:
1 <= n <= 231 - 1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/arranging-coins
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
package cn.fansunion.leecode.recursion;
/**
* 441. 排列硬币 <br/>
* 你总共有 n 枚硬币,并计划将它们按阶梯状排列。<br/>
* 对于一个由 k 行组成的阶梯,其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。<br/>
* 给你一个数字 n ,计算并返回可形成 完整阶梯行 的总行数。<br/>
*
* 来源:力扣(LeetCode) 链接:力扣 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*
* @author wen.lei@brgroup.com
*
* 2022-3-9
*/
public class ArrangingCoins {
/*示例 1:
输入:n = 5
输出:2
解释:因为第三行不完整,所以返回 2 。
示例 2:
输入:n = 8
输出:3
解释:因为第四行不完整,所以返回 3 。
提示:
1 <= n <= 231 - 1*/
/**
* 解题思路:n个数,落在第k行:>=第k行的最大值, <第k+1行的最大值 <br/>
* 第k行的范围:第k行的最小值,(1+2+3...+k)-(k-1); <br/>
* 第k行的最大值(1+2+3...+k); <br/>
*/
public int arrangeCoins(int n) {
for (int k = 1; k < n; k++) {
long maxK = fullK(k);
long maxK1 = maxK + (k + 1);
// 变种的二分查找,暂不考虑了,代码不好理解,可读性太差
if (n >= maxK && n < maxK1) {
return k;
}
}
return 1;
}
/**
* 第k行铺满,i枚硬币 (等差数列,高斯求和);乘法,应该比for循环的加法快很多
*
* @param k
* @return
*/
private long fullK(long k) {
// 2个数必有一个偶数,肯定能“除尽”
// int的最大值也太小了,2147483647,2个万相乘就是亿了
// 输入类型为long,可以支持更大的k;但是如果k太大,也会溢出
return (1 + k) * k / 2;
}
// 返回值用long,也会越界
private long fullKOverflow2(int k) {
return (1 + k) * k / 2;
}
// 越界了
private int fullKOverflow(int k) {
// int的最大值也太小了,2147483647,2个万相乘就是亿了
return (1 + k) * k / 2;
}
}
package test.leecode.recursion;
import org.junit.Assert;
import org.junit.Test;
import cn.fansunion.leecode.recursion.ArrangingCoins;
/**
* @author wen.lei@brgroup.com
*
* 2022-2-25
*/
public class ArrangingCoinsTest {
@Test
public void test() {
ArrangingCoins test = new ArrangingCoins();
Assert.assertEquals(60070,test.arrangeCoins(1804289383));
Assert.assertEquals(1,test.arrangeCoins(1));
Assert.assertEquals(2,test.arrangeCoins(3));
Assert.assertEquals(2,test.arrangeCoins(4));
Assert.assertEquals(2,test.arrangeCoins(5));
Assert.assertEquals(3,test.arrangeCoins(6));
Assert.assertEquals(3,test.arrangeCoins(7));
Assert.assertEquals(3,test.arrangeCoins(8));
Assert.assertEquals(3,test.arrangeCoins(9));
Assert.assertEquals(4,test.arrangeCoins(10));
}
}