100181. Divide an Array Into Subarrays With Minimum Cost I
给你一个长度为 n 的整数数组 nums 。
一个数组的 代价 是它的 第一个 元素。比方说，[1,2,3] 的代价是 1 ，[3,4,1] 的代价是 3 。
你需要将 nums 分成 3 个 连续且没有交集 的子数组。
请你返回这些子数组的 最小 代价 总和 。
测试样例：
输入：nums = [1,2,3,12]
输出：6
解释：最佳分割成 3 个子数组的方案是：[1] ，[2] 和 [3,12] ，总代价为 1 + 2 + 3 = 6 。其他得到 3 个子数组的方案是：
- [1] ，[2,3] 和 [12] ，总代价是 1 + 2 + 12 = 15 。
- [1,2] ，[3] 和 [12] ，总代价是 1 + 3 + 12 = 16 。
解答：第一个数必须留着，然后寻找之后的数字里面最小的2个就行（注意这点，第四题需要明白为啥）。
class Solution {
public int minimumCost(int[] nums) {
int res = nums[0];
int[] best = {Integer.MAX_VALUE, Integer.MAX_VALUE};
for (int i = 1; i < nums.length; ++i) {
if (nums[i] < best[0]) {
best[1] = best[0];
best[0] = nums[i];
} else if (nums[i] < best[1]) {
best[1] = nums[i];
}
}
return nums[0] + best[1] + best[0];
}
}100199. Find if Array Can Be Sorted
给你一个下标从 0 开始且全是 正 整数的数组 nums 。
一次 操作 中，如果两个 相邻 元素在二进制下数位为 1 的数目 相同 ，那么你可以将这两个元素交换。你可以执行这个操作 任意次 （也可以 0 次）。
如果你可以使数组变有序，请你返回 true ，否则返回 false 。
测试样例：
输入：nums = [8,4,2,30,15]
输出：true
解释：我们先观察每个元素的二进制表示。 2 ，4 和 8 分别都只有一个数位为 1 ，分别为 "10" ，"100" 和 "1000" 。15 和 30 分别有 4 个数位为 1 ："1111" 和 "11110" 。我们可以通过 4 个操作使数组有序：
- 交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。
- 交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。
- 交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。
- 交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 ，数组变为 [2,4,8,15,30] 。
数组变成有序的，所以我们返回 true 。注意我们还可以通过其他的操作序列使数组变得有序。
解答：这道题目范围极小，可以直接暴力。类似冒泡排序的思路，当前数左边所有比它小的数字都能和它交换，那么数组就能变的有序。
class Solution {
public boolean canSortArray(int[] nums) {
int[] bitCounts = new int[nums.length];
for (int i = 0; i < nums.length; ++i) {
bitCounts[i] = bitCount(nums[i]);
}
for (int i = 0; i < nums.length; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] < nums[j] && bitCounts[i] != bitCounts[j]) {
return false;
}
}
}
return true;
}
private int bitCount(int n) {
int res = 0;
while (n > 0) {
res += (n & 1);
n = n >> 1;
}
return res;
}
}100164. Minimize Length of Array Using Operations
给你一个下标从 0 开始的整数数组 nums ，它只包含 正 整数。
你的任务是通过进行以下操作 任意次 （可以是 0 次） 最小化 nums 的长度：
- 在 nums 中选择 两个不同 的下标 i 和 j ，满足 nums[i] > 0 且 nums[j] > 0 。
- 将结果 nums[i] % nums[j] 插入 nums 的结尾。
- 将 nums 中下标为 i 和 j 的元素删除。
请你返回一个整数，它表示进行任意次操作以后 nums 的 最小长度 。
测试样例：
输入：nums = [1,4,3,1]
输出：1
解释：使数组长度最小的一种方法是：
- 操作 1 ：选择下标 2 和 1 ，插入 nums[2] % nums[1] 到数组末尾，得到 [1,4,3,1,3] ，然后删除下标为 2 和 1 的元素。nums 变为 [1,1,3] 。
- 操作 2 ：选择下标 1 和 2 ，插入 nums[1] % nums[2] 到数组末尾，得到 [1,1,3,1] ，然后删除下标为 1 和 2 的元素。nums 变为 [1,1] 。
- 操作 3 ：选择下标 1 和 0 ，插入 nums[1] % nums[0] 到数组末尾，得到 [1,1,0] ，然后删除下标为 1 和 0 的元素。nums 变为 [0] 。
nums 的长度无法进一步减小，所以答案为 1 。1 是可以得到的最小长度。
解答：没啥意思的脑筋急转弯题。需要先先到一点如果A > B，那么A % B < B，并且B % A == B。首先寻找当前数组的最小值，如果最小值的出现数字小于等于2，那么一切都好，答案是1（根据第一个规则，所有数都是最小数%大数，留下小数。小数的出现数小于2，那么答案必然是1）。否则，我们寻找任意一个大数，如果这个大数不能被最小数整除，那么一切安好，出现了新的最小数，答案也是1。最差的情况就是找不到，那么任何大数都是k*最小数，无论怎么取模，都会归于最小数。这个情况，出现次数就是最小数22变0。
class Solution {
public int minimumArrayLength(int[] nums) {
int min = Integer.MAX_VALUE;
int count = 0;
for (int n : nums) {
if (n < min) {
min = n;
count = 1;
} else if (n == min) {
count += 1;
}
}
if (count <= 2) {
return 1;
}
for (int n : nums) {
if (n % min != 0) {
return 1;
}
}
return count / 2 + (count % 2);
}
}100178. Divide an Array Into Subarrays With Minimum Cost II
给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。
一个数组的 代价 是数组中的 第一个 元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。
你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足 第二 个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist 。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)] ，那么它需要满足 ik-1 - i1 <= dist 。
请你返回这些子数组的 最小 总代价。
测试样例：
输入：nums = [10,1,2,2,2,1], k = 4, dist = 3
输出：15
解释：将数组分割成 4 个子数组的最优方案是：[10] ，[1] ，[2] 和 [2,2,1] 。这是一个合法分割，因为 ik-1 - i1 等于 3 - 1 = 2 ，小于 dist 。总代价为 nums[0] + nums[1] + nums[2] + nums[3] ，也就是 10 + 1 + 2 + 2 = 15 。分割 [10] ，[1] ，[2,2,2] 和 [1] 不是一个合法分割，因为 ik-1 和 i1 的差为 5 - 1 = 4 ，大于 dist 。15 是分割成 4 个子数组的最小总代价。
解答：这题本质上，就是寻找区间上，最小的k-1个数（第一个数一定会被算进来）。有dist这个限制，那么区间就被锁死了。我们可以用双指针，配合2个优选队列来寻找最佳的k - 1个数（能挑到k - 1个数，那么必然可以分成k - 1个区间）。
class Solution {
private class CustomMap {
TreeMap<Integer, Integer> map;
int size;
long sum;
public CustomMap() {
map = new TreeMap<>();
size = 0;
sum = 0;
}
public boolean removeKey(int key) {
if (map.containsKey(key)) {
int c = map.get(key);
if (c == 1) {
map.remove(key);
} else {
map.put(key, c - 1);
}
sum -= key;
size -= 1;
}
return false;
}
public void addKey(int key) {
++size;
sum += key;
map.put(key, map.getOrDefault(key, 0) + 1);
}
public int firstKey() {
return map.firstKey();
}
public int lastKey() {
return map.lastKey();
}
}
public long minimumCost(int[] nums, int k, int dist) {
long res = Long.MAX_VALUE;
CustomMap effective = new CustomMap(), nonEffective = new CustomMap();
int secondGroupStart = 1;
for (int i = 1; i < nums.length; ++i) {
nonEffective.addKey(nums[i]);
giveUpFirstKey(effective, nonEffective);
if (i - secondGroupStart > dist) {
if (!nonEffective.removeKey(nums[secondGroupStart])) {
effective.removeKey(nums[secondGroupStart]);
giveUpFirstKey(effective, nonEffective);
}
++secondGroupStart;
}
while (effective.size > k - 1) {
giveLastKey(effective, nonEffective);
}
if (effective.size == k - 1) {
res = Math.min(res, effective.sum + nums[0]);
}
}
return res;
}
private void giveUpFirstKey(CustomMap effective, CustomMap nonEffective) {
if (!nonEffective.map.isEmpty()) {
int firstKey = nonEffective.firstKey();
effective.addKey(firstKey);
nonEffective.removeKey(firstKey);
}
}
private void giveLastKey(CustomMap effective, CustomMap nonEffective) {
int lastKey = effective.lastKey();
effective.removeKey(lastKey);
nonEffective.addKey(lastKey);
}
}