面试准备（十四）排列硬币

古城微笑少年丶 2022-10-13 01:47 109阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70][]

**解题思路：**

迭代：循环计算和大于n之后输出

二分法：

牛顿迭代：

**代码：**

public class ArrangeCoin {
        public static void main(String[] args) {
            System.out.println(arrangeCoins(10));
            System.out.println(arrangeCoins2(10));
            System.out.println(arrangeCoins3(10));
        }
    
        //迭代
        public static int arrangeCoins(int n){
            for(int i=1;i<=n;i++){
                n = n-i;
                if(n<=i){
                    return i;
                }
            }
            return 0;
        }
    
        //二分查找
        public static int arrangeCoins2(int n){
            int low=0,high=n;
            while (low<=high){
                int mid = (high -low)/2+low;
                int cost = ((mid+1)*mid)/2;
                if(cost==n){
                    return mid;
                }else if(cost>n){
                    high=mid-1;
                }else if(cost<n){
                    low = mid+1;
                }
            }
            return 0;
        }
    
        //牛顿迭代
        public static int arrangeCoins3(int n){
            if(n==0){
                return 0;
            }
            return (int)sqrt(n,n);
        }
    
        private static double sqrt(double x, int n){
            double res = (x+(2*n-x)/x)/2;
            if (res == x){
                return x;
            }else {
                return sqrt(res,n);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzcxNTY3_size_16_color_FFFFFF_t_70]: /images/20221005/6b5ed24f8c574f61a2f93aa9449d13b7.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 P10 排列硬币

一、迭代 // 时间O(n),空间O(1) func sortCoin(n int) int { nums := n for i :

ゝ一世哀愁。/ 2022年10月20日 01:17/ 0 赞/ 106 阅读

相关面试准备（二十）java HashMap

为什么用红黑树解决链表过长，查询效率过低的问题为什么不直接使用红黑树红黑树插入会很慢，要维护自己的结构为什么使用红黑树的阈值是8 之所以是8，是因为Java的

叁歲伎倆/ 2022年10月19日 04:19/ 0 赞/ 105 阅读

相关面试准备（十九）java常见

一、什么是面向对象？谈谈你对面向对象的理解面向过程：注重事情的每一个步骤及顺序。面向过程比较高效。面向对象：注重事情有哪些参与者（对象）、各自需要做什么。更易于复用、扩

淡淡的烟草味﹌/ 2022年10月13日 12:50/ 0 赞/ 187 阅读

相关面试准备（十七）柠檬水找零

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQw

女爷i/ 2022年10月13日 05:14/ 0 赞/ 58 阅读

相关面试准备（十四）排列硬币

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQw

古城微笑少年丶/ 2022年10月13日 01:47/ 0 赞/ 110 阅读

相关面试准备（十一）删除排序数组

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQw

约定不等于承诺〃/ 2022年10月12日 15:55/ 0 赞/ 126 阅读

相关面试准备（十）素数个数统计

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQw

柔光的暖阳◎/ 2022年10月12日 15:55/ 0 赞/ 106 阅读

相关力扣-441题排列硬币（C++）

题目链接：[https://leetcode-cn.com/problems/arranging-coins/][https_leetcode-cn.com_problems_

╰+哭是因爲堅強的太久メ/ 2022年08月28日 06:56/ 0 赞/ 158 阅读

相关面试准备

在求职中，我主要投报了软件研发和嵌入式软件研发两个职位，与各位分享一下我的面试准备。面试需要准备一下几个方面：首先，是自我介绍准备一段1分钟之内的自我介绍，包含基本

心已赠人/ 2022年05月30日 09:06/ 0 赞/ 223 阅读