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

古城微笑少年丶 2022-10-13 01:47 150阅读 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