• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode441.排列硬币|ArrangingCoins

原作者: [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,找出可形成完整阶梯行的总行数。

是一个非负整数,并且在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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
用C#完成Swift远程推送通知发布时间:2022-07-13
下一篇:
「音乐」Taylor Swift—the lakes (bonus track)发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap