欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

441. 排列硬币

程序员文章站 2024-03-16 08:35:16
...

一、迭代法

class Solution {
    public int arrangeCoins(int n) {
        for (int i = 1; i <= n; i++) {
            n = n - i;
            if (n <= i) {
                return i;
            }
        }
        return 0;
    }
}

二、二分查找

 public static int arrangeCoins(int n) {
        // O(logn)
        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 {
                low = mid + 1;
            }
        }
        return low;
    }

三、牛顿迭代

package leetcode;

public class Solution {

    public static void main(String[] args) {
        System.out.println((int)arrangeCoins(10));
    }

    public static int arrangeCoins(int n) {
        if (n == 0) {
            return 0;
        }
        return (int)sqrt(n, n);
    }
    public static double sqrt(double i, int n) {
        double res = (i + (2 * n - i) / i) / 2;;
        if (res == i) {
            return res;
        } else {
            return sqrt(res, n);
        }
    }
}


牛顿迭代法

相关标签: LeetCode