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

排列硬币

时间:2022-12-02 14:22:11浏览次数:38  
标签:排列 硬币 int mid rignt left

排列硬币

一、题目描述

总共有n和硬币,并计划将它们按阶梯状排列。对于一个有k行组成的阶梯,其第i行必须正好有i枚硬币。阶梯的最后一行可能是不完整的。
给定一个数组n,计算并返回可形成完整阶梯行的总行数。
示例1

输入:n = 5
输出:22 
输入:n = 8
输出:3

二、解题思路

类似于如下形式
1
11
111
1111
使用求和公式n=[k(k+1)]/2,k就是阶数,k从1开始,因为在n>=1的情况下,最少也有1阶。

三、解题方法

方法1(二分查找)
使用二分查找在1-n内与k值,即可。
代码实现

class Solution {
    public int arrangeCoins(int n) {
        int left = 1;
        int rignt = n;

        while(left < rignt){
            int mid = (rignt - left +1)/2 + left;
            if((long) mid *(mid +1) <= (long)2*n ){
                left = mid;
            }else{
                rignt = mid -1;
            }
        }

        return left;
    }
}

标签:排列,硬币,int,mid,rignt,left
From: https://www.cnblogs.com/zjjtt/p/16944344.html

相关文章

  • STL应用之随机化全排列
    输入:一个序列,可以是一组数字,如1,2,3,4....,也可以是一组字符串"111","222",....输出:原序列的随机化序列要求:每种随机的序列出现的概率相等,如输入{1,2,3},那么有6种随机化序列......
  • 一种粗糙的全排列算法
    /*ThisisafreeProgram,YoucanmodifyorredistributeitunderthetermsofGNU*Description:给定一个字符串,输出它的全排列,如给定字符串abc,输出abc,bac,......
  • 手把手教你如何实现大量图片的自适应图片页面的排列
    前言最近在开发一个批量展示图片的页面,图片的自适应排列是一个无法避免的问题在付出了许多头发的代价之后,终于完成了图片排列,并封装成组件,最终效果如下:1、设计思路为了使结......
  • 奇偶的神奇排列
    题目:输入一个整数数组,实现一个函数,来调整该数组中数字的顺序使得数组中所有的奇数位于数组的前半部分,所有偶数位于数组的后半部分分析:1、首先输入一个整数数组,然后对数组内......
  • 排列(permutation)
    排列(permutation)      用1,2,3,...,9组成3个三位数abc,def和ghi,每个数字恰好使用一次,要求abc:def:ghi=1:2:3。按照“abcdefghi”的格式输出所有解,每行一个解。【......
  • 排列组合公式 与24点编程游戏
    排列组合公式此外, 规定0!=1.24点游戏编程问题问题描述你有4张写有1到9数字的牌。你需要判断是否能通过 *,/,+,-,(,) 的运算得到24。示例1:输入:[4,1,8,7......
  • 【LeeCode】46. 全排列
    【题目描述】​​https://leetcode.cn/problems/permutations/?favorite=2cktkvj​​给定一个不含重复数字的数组 ​​nums​​ ,返回其 所有可能的全排列 。你可以 按......
  • 四种语言刷算法之全排列
    力扣46.全排列1、C/***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothre......
  • mysql升序排列id为0的在最后
    在实际开发中有时会有升序排列id为0的在最后的需求,这里我记录了一种在stackoverflow中比较简单的方法如下:Youmaywanttotrythefollowing:SELECT*FROMyour_tableOR......
  • 31. 下一个排列(stl的algorithm中next_permutation的实现)
    注:这题思路就是stl的algorithm中next_permutation的实现思路整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。例如,arr=[1,2,3] ,以下这些都可以视作 ......