个人中心
文章发布
退出
作者热门文章
- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
27
4
题目地址：https://leetcode.com/problems/arranging-coins/#/descriptionopen in new window
Youhave 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.
nis 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个硬币，问能摆出多少层，如果最后一层不满足的话，是不算的。
如果模拟这个安排硬币的过程的话，可以这么做：
class Solution(object):
def arrangeCoins(self, n):
"""
:type n: int
:rtype: int
"""
level = 0
count = 0
while count + level + 1 <= n:
level += 1
count += level
return level
1 2 3 4 5 6 7 8 9 10 11 12
上面做法的效率不高。因为前k层的硬币个数可以直接通过(k + 1) * k / 2求出来，所以很直接的想法就可以使用二分查找。
即目的是找到(k + 1) * k / 2<=sum的最大数字，套用二分查找的模板，很容易写出来。
class Solution(object):
def arrangeCoins(self, n):
"""
:type n: int
:rtype: int
"""
left, right = 0, n + 1[left, right)
while left < right:
mid = left + (right - left) / 2
if mid * (mid + 1) / 2 <= n:
left = mid + 1
else:
right = mid
return left - 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14
刷题的时候第一次遇到纯数学的问题，其实就是求解sum = (x + 1) * x / 2这个方程，很简单的就能得到x = (-1 + sqrt(8 * n + 1)) / 2，向下取整就能得到结果了。
下面的代码的括号也要重视一下。
public class Solution {
public int arrangeCoins(int n) {
return (int)((-1 + Math.sqrt(1 + 8 * (long) n)) / 2);
}
}
1 2 3 4 5
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发
27
4
0
在以下情况下，如何确定函数返回 0 或 1 的概率: Let the function_A return 0 with probability 40% and 1 with probability 6
我是 prolog 的新手，正在尝试解决这个经典的硬币找零问题。 用公式 M>=0 和 M = P+5*N+10*D 改变(M,P,N,D)这是我的方法 change(M,P,N,D) :-
我目前正在使用 COIN OR BCP 框架研究分支和价格 (BAP) 算法。这是一个不错的框架，但有点旧，而且文档也不好。我希望这里有人能够回答我的问题。 我的 BAP 算法运行良好，但我注意到，我
题目地址：https://leetcode.com/problems/coin-change/description/ 题目描述 Youare given coins of different d
题目地址：https://leetcode.com/problems/arranging-coins/#/descriptionopen in new window 题目描述 Youhave a
为什么我的代码没有打印名为 coins 的 int ？运行调试系统时我没有看到任何错误。 #include #include int main(void) { // getting the us
我正在尝试设置 Coin-CLP按照网站上的说明还支持 CPLEX(我已经安装并在我的机器上顺利运行)。 不幸的是，当我尝试在安装时运行配置步骤时，在我想要包含 CPLEX 的版本中看起来像这样: .
所以我正在做硬币系统，但我遇到了一个小问题。通常，每当我输入某些内容时，我都会得到 1 个硬币，但当我使用 !coins 命令检查我有多少硬币时，我不希望机器人给我硬币。我希望它在使用此命令时忽略给我
我在使用 Javascript Coin Slider 时遇到问题(非常棒，下载地址:this workshop)。我附上 2 个屏幕截图。一个是在 chrome 中工作的文件，第二个是同时托管在我的
我有一个输入: 测试用例数量 一笔钱 作为我需要的输出: 我们拥有的不同硬币的数量以及每枚硬币的值(value)。 程序应该确定是否有解决方案，因此输出应该是"is"或“否”。 我使用动态规划编写了程
所以这是我的代码，我试图找出从无限供应的硬币中组成我的目标数量的最小硬币数量。我的问题是我没有得到所需的硬币数量，而是得到了 0。那么我该如何解决这个问题呢？如果我不清楚的话，很抱歉。我的英语不太好:
尝试为一般硬币找零问题编写 DP 解决方案，同时跟踪使用了哪些硬币。到目前为止，我一直在努力为我提供所需的最少硬币数量，但无法弄清楚如何获得使用了哪些硬币以及使用了多少次。如果使用硬币，我尝试用值设置
http://uva.onlinejudge.org/external/6/674.html我正在努力解决这个问题。不过请注意，这不是最小硬币找零问题，它要求我使用 50、25、15、10、5 和 1
我正在研究一些算法，遇到了 coin change问题。 在思考这个问题时，我想到了这个朴素的递归解决方案: int coinChange(const vector& coins, int start
我遇到了 a nice post在@amalloy 上寻找 hylomorhism示例，通过有用的讨论和完整的实现来说明递归方案 (RS) 的用法: {-# LANGUAGE DeriveFuncto
当接受我正在制作的 NFT 的付款时，我如何确保我可以从我的模块调用 coin.transfer 和 coin.details？ 最佳答案 所以唯一的必要条件是 代币合约引用 传输能力 您可以像普通函
我想在 ERC-20 网络上创建一个 token 。 我想继承我合约中的接口(interface)。 当我继承表单界面时，它向我显示此错误: Contract "CpayCoin" should be
/**************************************************** **********************************************
我最近开始解决 DP 问题，并遇到了 COINS。我尝试使用带有内存功能的 DP 来解决它，如果我使用 int 数组(我猜)，它就可以正常工作。这是我的方法(剩下一些修改): #include #i
假设有一家公司拥有几个vending machines收集硬币的。当投币保险箱已满时，机器将无法出售任何新元素。为了防止这种情况发生，公司必须在此之前收集硬币。但如果公司太早 dispatch 技术人
我是一名优秀的程序员,十分优秀！