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);
}
}
}