
问题
你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。
给定一个数字 n,找出可形成完整阶梯行的总行数。
n 是一个非负整数,并且在32位有符号整型的范围内。
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤因为第三行不完整,所以返回2.
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤因为第四行不完整,所以返回3.
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.
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤Because the 3rd row is incomplete, we return 2.
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤Because the 4th row is incomplete, we return 3.
示例
public class Program { public static void Main(string[] args) { var n = 8; var res = ArrangeCoins(n); Console.WriteLine(res); n = 18; res = ArrangeCoins2(n); Console.WriteLine(res); n = 28; res = ArrangeCoins3(n); Console.WriteLine(res); n = 38; res = ArrangeCoins4(n); Console.WriteLine(res); n = 58; res = ArrangeCoins5(n); Console.WriteLine(res); n = 68; res = ArrangeCoins6(n); Console.WriteLine(res); Console.ReadKey(); } private static int ArrangeCoins(int n) { //暴力解法,此解法LeetCode超时未AC var res = 0; var value = (long)0; while(n > (value = ComputerT(++res))) { } if(n != value) res--; return res; //以下解法同理,但 LeetCode 可以 AC //if(n == 0) return 0; //for(long i = 1; ; i++) { // if(n >= (i + 1) * i / 2 && n < (i + 2) * (i + 1) / 2) // return (int)i; //} } private static int ComputerT(int n) { //抽出来是为了让程序结构更清晰 return (1 + n) * n / 2; } private static int ArrangeCoins2(int n) { //按1、2、3、4、5这样一直减下去 //直到n小于或等于0时为止 var index = 1; while((n -= index++) > 0) { } //考虑上述循环中因为是 index++ //index最终被多加了一次 //真实的索引应该是 index - 1 index--; //小于0时,最后一排不完整,所以再减1 if(n < 0) return index - 1; //等于0时,最后一徘正好完整 return index; } private static int ArrangeCoins3(int n) { /* 推导过程 * * 说明=>x ^ 2 表示 x 的平方 * 公式1:a ^ 2 + 2 * a * b + b ^ 2 = (a + b) ^ 2 * 公式2:公差为1的等差数列的求和公式为 S = (1 + n) * n / 2 * * 推导=> * 设在第 k 行硬币排完,那么 * (1 + k) * k / 2 = n * 展开并两边同时乘以 2 * k + k ^ 2 = 2 * n * 两边同时 + 0.25 * k ^ 2 + k + 0.25 = 2 * n + 0.25 * 合并 * (k + 0.5) ^ 2 = 2 * n + 0.25 * 两边同时开根号 * k + 0.5 = Math.Sqrt(2 * n + 0.25) * 两边同时 - 0.5,求出 k 的值 * k = Math.Sqrt(2 * n + 0.25) - 0.5 */ //原来的 n 为int,直接 2 * n + 0.25 会导致值溢出 //所以用 (long)n 强转 return (int)(Math.Sqrt(2 * (long)n + 0.25) - 0.5); //以下解法同理,但换了一种求 k 的方式 //具体推导过程请看以下博文 //https://blog.csdn.net/zx2015216856/article/details/81950377 //return (int)((Math.Sqrt(8 * (long)n + 1) - 1) / 2); } private static int ArrangeCoins4(int n) { //解法思路同ArrangeCoins //都属于暴力求解,但此解法效率略高,可AC var x = (long)n; var temp = (long)n; while(x * x + x > 2 * temp) { x = (x * x + 2 * temp) / (2 * x + 1); } return (int)x; } private static int ArrangeCoins5(int n) { //基本思路同ArrangeCoins和ArrangeCoins4 var k = (int)(Math.Sqrt(2) * Math.Sqrt(n)); return k * (k + 1) <= 2 * n ? k : k - 1; } private static int ArrangeCoins6(int n) { //二分法 //二分是对暴力解法的优化 //使得循环更快的靠近目标 var left = 0L; var right = (long)n; while(left <= right) { var mid = left + (right - left) / 2; var sum = mid * (mid + 1) / 2; if(sum > n) { right = mid - 1; } else { left = mid + 1; } } return (int)(left - 1); } }
以上给出6种算法实现,以下是这个案例的输出结果:
3 5 7 8 10 11
分析:
显而易见,ArrangeCoins、ArrangeCoins2、ArrangeCoins4、ArrangeCoins5的时间复杂度均为: ,ArrangeCoins3的时间复杂度基于 Math.Sqrt() 的实现,ArrangeCoins6的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3995。