首页 > 其他分享 >排列硬币

排列硬币

时间:2023-08-08 20:22:17浏览次数:32  
标签:排列 硬币 int 示例 阶梯 high 完整

你总共有 n 枚硬币,并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯,其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ,计算并返回可形成 完整阶梯行 的总行数。

示例 1:

输入:n = 5
输出:2
解释:因为第三行不完整,所以返回 2 。
示例 2:

输入:n = 8
输出:3
解释:因为第四行不完整,所以返回 3 。

双指针写法

class Solution {
    public int arrangeCoins(int n) {
        int low = 0, high = n;
        //双指针,根据公式x*(x+1)/2为总数目
        //我们要找到1~n中满足公式的x*(x+1)/2值
        while(low<=high){
            long mid = (low+high)/2;
            long cost = mid*(mid+1)/2;
            if(n==cost){
                return (int)mid;
            }else if(n>cost){
                low = (int)mid + 1;
            }else{
                high = (int)mid - 1;
            }
        }
        return (int)high;
    }
}

标签:排列,硬币,int,示例,阶梯,high,完整
From: https://www.cnblogs.com/xiaochaofang/p/17615282.html

相关文章

  • 对集合数组进行降序排列的方法
    在Dart中,你可以使用List的sort()方法对集合数组进行排序。要按降序排列,可以在排序方法中指定一个自定义的比较函数。以下是一种常见的降序排序方法:List<int>numbers=[3,1,4,2,5];numbers.sort((a,b)=>b.compareTo(a));print(numbers);//[5,4,3,2,1]在上述示例中,......
  • 排列数与组合数
    首先是定义组合数:从\(n\)个不同元素中,任取\(m(m\len)\)个元素并成一组,叫做从\(n\)个不同元素中取出\(m\)个元素的一个组合;\(C_{n}^{m}\)表示从\(n\)个不同元素中取出\(m(m\len)\)个元素的所有组合的个数,叫做从\(n\)个不同元素中取出\(m\)个元素的组合数。......
  • DFS 算法模板——二叉树的遍历非递归写法要会,排列组合的一定要自己画一颗树,变量i和当
    dfs算法模板:1、下一层仅2个节点的dfs,也就是二叉树的dfs先序遍历,迭代和递归写法都要熟悉:defpreoder_traversal(root):ifnotroot:returnstack=[root]whilestack:node=stack.pop()dosomethingwithnodeifnode.ri......
  • nflsoj 5924 选排列
    与全排列略微有些不同,只需要将退出条件需要改成u==r#include<iostream>usingnamespacestd;constintN=15;intr,n;intpath[N];boolst[N];voiddfs(intu){if(u==r){for(inti=0;i<r;i++)printf("%d",path[i]);printf("\n&......
  • 排列组合
     排列:从n个元素的集合S中,有序的选出r个元素,叫做S 的一个r排列排列数的性质:第一条性质:(n*(n-1)*...*2*1)/((n-1-m+1)*...*2*1)=n!/(n-m)!;第二条性质:m*(n-1)!/(n-m)!+(n-1)!/(n-1-m)!=(n-m+m)*(n-1)!/(n-m)!=n!/(n-m)! 组合:从n个元素的集合S中,无序的选出r......
  • echarts中legend实现排列对齐
    问题当图表中的legend过多的时候,就需要考虑legend进行换行,但是换行之后,图例就会无法对齐。解决legend:{icon:"rect",width:"80%",itemWidth:6,itemHeight:6,bottom:0,textStyle:{color:"#333",rich:{a:{width:100,......
  • mongodb 倒叙排列
    MongoDB倒序排列在MongoDB中,我们可以使用sort()方法对查询结果进行排序。默认情况下,sort()方法按升序排序。如果想要倒序排列,我们可以在sort()方法中指定-1作为排序规则。在本文中,我们将讨论如何在MongoDB中进行倒序排列,并提供一些代码示例来演示这一过程。配置环境首先,我们需......
  • gdb 反汇编disas源码排列问题
    问题在开发过程中,可能需要查看cpp文件生成的汇编代码来确认一些问题。由于单纯的汇编代码看起来并不太容易捋清楚内部逻辑,所以最好能够把源代码的位置列出来。在gdb的早期版本中,这个功能是通过disas命令的/m修饰符(选项)来实现的。如果使用过这个选项就会发现,这个功能显示的结果......
  • 根据内存占据的大小排列,看到C盘里面哪个文件占据流量最大?
    大家好,我是皮皮。一、前言这篇文章还得从前几天在Python最强王者群【......
  • 排列组合
    错排问题对于第n信,必然放在1~n-1号信封中。假设n号信放在1号信封中,考虑一号信放在哪放在n号信封中,还剩的n-2封信和信封构成了n-2的子问题f(n-2)放在k号信封(\(2\lek<n\))f(n-1)因为n可以放在n-1个位置。所以(f(n-1)+f(n-2))*(n-1)P1595信封问题板子题,不多说了P4071[SDO......