你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。
给定一个数字 n,找出可形成完整阶梯行的总行数。
n 是一个非负整数,并且在32位有符号整型的范围内。
示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整,所以返回2.
class Solution {
public int arrangeCoins(int n) {
long left = 1;
long right = n;
while (left <= right) {
long mid = left + (right - left) / 2;
long sum = mid * (mid + 1) / 2;
if (sum == n) {
return (int)mid;
}
else if (sum > n) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return (int)right;
}
}
给定一个长度为 n 的 非空 整数数组,每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。
示例:
输入:
[1,2,3]
输出:
3
解释:
只需要3次操作(注意每次操作会增加两个元素的值):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
class Solution {
public int minMoves(int[] nums) {
Arrays.sort(nums);
int diff = 0;
int change = 0;
for (int i = 1; i < nums.length; i++) {
diff = change + nums[i] - nums[i - 1];
nums[i] += change;
change += diff;
}
return change;
}
}
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为*O(n)*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int n = nums.length;
List<Integer> ans = new ArrayList<>();
for (int x: nums) {
nums[(x - 1) % n] += n;
}
for (int x = 0; x < nums.length; x++) {
if (nums[x] <= n) {
ans.add(x + 1);
}
}
return ans;
}
}