leetcode 441. Arranging Coins 等差数列求和

快来打我* 2022-06-04 09:07 166阅读 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.

题意很简单，就是一个简单的等比数列求和问题

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        /*
            1 + 2 + 3 + ... + x = n
            -> (1 + x)x / 2 = n
            ->x ^ 2 + x = 2n
            ->x ^ 2 + x + 1 / 4 = 2n + 1 / 4
            -> (x + 1 / 2) ^ 2 = 2n + 1 / 4
            -> (x + 0.5) = sqrt(2n + 0.25)
            ->x = -0.5 + sqrt(2n + 0.25)
        */
    
        int arrangeCoins(int n) 
        {
            return floor(-0.5 + sqrt((double)2 * n + 0.25));
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关通过图形规律构造等差数列，利用等差数列求和公式定位结果。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

迈不过友情╰/ 2023年01月03日 01:54/ 0 赞/ 141 阅读

相关 leetcode413等差数列划分

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

﹏ヽ暗。殇╰゛Y/ 2022年09月04日 02:50/ 0 赞/ 166 阅读

相关求和（数学，等差数列）

求和 Time Limit: 1000 ms Memory Limit: 64 MB Total Submission: 64 Submission Accept

迈不过友情╰/ 2022年08月01日 12:27/ 0 赞/ 161 阅读

相关 [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 赞/ 125 阅读

相关【Leetcode】【python】Arranging Coins

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

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

相关 leetcode 268. Missing Number 等差数列求和 + 位操作

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that

约定不等于承诺〃/ 2022年06月08日 13:25/ 0 赞/ 151 阅读

相关 441_ Arranging_Coins

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

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

相关 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 赞/ 167 阅读

相关 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 赞/ 353 阅读