LeetCode : 441. Arranging Coins布置金币

桃扇骨 2021-06-24 16:12 337阅读 0赞

**试题**  
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.

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.  
**代码**  
这一题可以看成1-n之间存在一个映射数组\[1,…,(n+1)\*n/2\]，而我们就是要找这个数组中小于n的最大整数。

class Solution {
        public int arrangeCoins(int n) {
            if(n==0) return 0;
            
            long left = 1, right = n/2+1;
            while(left < right){
                long mid = left + (right - left) / 2;
                long value = (mid + 1) * mid / 2;
                if(value == n){
                    return (int)mid;
                }else if(value < n){
                    left = mid + 1;
                }else if(value > n){
                    right = mid - 1;
                }
            }
            return (int)((left+1)*left/2<=n?left:left-1);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，337人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 441. 排列硬币（Java版）

题目 [https://leetcode-cn.com/problems/arranging-coins/][https_leetcode-cn.com_problems

小灰灰/ 2023年01月17日 07:48/ 0 赞/ 100 阅读

相关 LeetCode - Medium - 322. Coin Change

Topic Dynamic Programming Description [https://leetcode.com/problems/coin-chan

谁践踏了优雅/ 2022年12月31日 13:20/ 0 赞/ 133 阅读

相关 [leetcode]: 441. Arranging Coins

1.题目 You have a total of n coins that you want to form in a staircase shape, where ev

太过爱你忘了你带给我的痛/ 2022年06月15日 06:15/ 0 赞/ 110 阅读

相关【Leetcode】【python】Arranging Coins

Arranging Coins 标准答案代码来自[书影博客][Link 1] 题目大意你有n枚硬币，想要组成一个阶梯形状，其中第k行放置k枚硬币。给定n，

超、凢脫俗/ 2022年06月13日 10:25/ 0 赞/ 114 阅读

相关 441_ Arranging_Coins

/ 441. Arranging Coins You have a total of n coins that you want to for

旧城等待，/ 2022年06月08日 00:51/ 0 赞/ 140 阅读

相关 leetcode 441. Arranging Coins 等差数列求和

You have a total of n coins that you want to form in a staircase shape, where every k-th

快来打我*/ 2022年06月04日 09:07/ 0 赞/ 151 阅读

相关 leetcode [322]Coin Change

You are given coins of different denominations and a total amount of money amount. Write

小咪咪/ 2021年12月07日 14:21/ 0 赞/ 230 阅读

相关 [leetcode]322. Coin Change找零钱

You are given coins of different denominations and a total amount of money amount. Write

待我称王封你为后i/ 2021年11月11日 01:34/ 0 赞/ 452 阅读

相关 LeetCode : 979. Distribute Coins in Binary Tree分布在树中的金币

试题 Given the root of a binary tree with N nodes, each node in the tree has node.val co

喜欢ヅ旅行/ 2021年06月24日 16:12/ 0 赞/ 285 阅读

相关 LeetCode : 441. Arranging Coins布置金币

试题 You have a total of n coins that you want to form in a staircase shape, where every

桃扇骨/ 2021年06月24日 16:12/ 0 赞/ 338 阅读