[Swift]LeetCode441.排列硬币|ArrangingCoins

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10339427.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 fullstaircase 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.

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

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

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

示例 1:

n = 5

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

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

示例 2:

n = 8

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

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

20ms

1 class Solution {
2     func arrangeCoins(_ n: Int) -> Int {
3         return Int((-1 + sqrt(Double(1 + 8 * n))) / 2)
4     }
5 }

28ms

 1 class Solution {
 2     func arrangeCoins(_ n: Int) -> Int {
 3             guard n > 1 else {
 4         return n
 5     }
 6     var index = n, lhs = 0, rhs = n, mid = 0
 7     while lhs < rhs {
 8         mid = (rhs + lhs) / 2
 9         let result = (1 + mid) * mid / 2
10         if result == n {
11             return mid
12         } else if result > n {
13             rhs = mid
14         } else {
15             lhs = mid + 1
16         }
17     }
18     return lhs - 1
19     }
20 }

36ms

 1 class Solution {
 2     func arrangeCoins(_ n: Int) -> Int {
 3         var left = 1
 4         var right = n
 5 
 6         while left <= right {
 7             let mid = left + (right - left) / 2
 8             if n * 2 < mid * (mid + 1) {
 9                 right = mid - 1
10             } else {
11                 left = mid + 1
12             }
13         }
14 
15         return left - 1
16     }
17 }

52ms

1 class Solution {
2     func arrangeCoins(_ n: Int) -> Int {
3         var result = Int(sqrt(Double(n * 2))) - 1
4         while result * (result + 1) / 2 <= n {
5             result += 1
6         }
7         return result - 1
8     }    
9 }

80ms

 1 class Solution {
 2     func arrangeCoins(_ n: Int) -> Int {
 3         var row = 1
 4         var sum = row
 5         while true {
 6             if sum == n {
 7                 return row
 8             } else if sum > n {
 9                 return row - 1
10             }
11             row += 1
12             sum += row
13         }
14     }
15 }

176ms

 1 class Solution {
 2     func arrangeCoins(_ n: Int) -> Int {
 3     return self.lineCoins(n, 1)
 4     }
 5         func lineCoins(_ n: Int, _ line: Int) -> Int {
 6         if n<line {
 7             return line-1
 8         }
 9         return lineCoins(n-line, line+1);
10     }
11 }

204ms

 1 class Solution {
 2     func arrangeCoins(_ n: Int) -> Int {
 3         if n == 0 || n == 1 {
 4             return n
 5         }
 6         for value in 1...n {
 7             if Double((1 + value) * value) * 0.5 > Double(n) {
 8                 return (value - 1)
 9             }
10         }
11         return 0
12     }
13 }