欢迎大家加QQ群：623375442，可以方便群里面交流。
100589. Transform Array by Parity
给你一个整数数组 nums。请你按照以下顺序 依次 执行操作，转换 nums：
- 将每个偶数替换为 0。
- 将每个奇数替换为 1。
- 按 非递减 顺序排序修改后的数组。
执行完这些操作后，返回结果数组。
测试样例：
输入：nums = [4,3,2,1]
输出：[0,0,1,1]
解释：
- 将偶数（4 和 2）替换为 0，将奇数（3 和 1）替换为 1。现在，nums = [0, 1, 0, 1]。
- 按非递减顺序排序 nums，得到 nums = [0, 0, 1, 1]。
解答：为了写得快，直接排序了。最好是计算一个0的个数。
class Solution {
public int[] transformArray(int[] nums) {
for (int i = 0; i < nums.length; ++i) {
nums[i] = nums[i] % 2;
}
Arrays.sort(nums);
return nums;
}
}100595. Find the Number of Copy Arrays
给你一个长度为 n 的数组 original 和一个长度为 n x 2 的二维数组 bounds，其中 bounds[i] = [ui, vi]。
你需要找到长度为 n 且满足以下条件的 可能的 数组 copy 的数量：
- 对于 1 <= i <= n - 1 ，都有 (copy[i] - copy[i - 1]) == (original[i] - original[i - 1]) 。
- 对于 0 <= i <= n - 1 ，都有 ui <= copy[i] <= vi 。
返回满足这些条件的数组数目。
测试样例：
输入：original = [1,2,3,4], bounds = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：可能的数组为：
- [1, 2, 3, 4]
- [2, 3, 4, 5]
解答：计算重叠区域
class Solution {
public int countArrays(int[] original, int[][] bounds) {
int[] mark = bounds[0];
for (int i = 1; i < original.length; ++i) {
int diff = original[i] - original[i - 1];
mark[0] += diff;
mark[1] += diff;
if (mark[1] < bounds[i][0] || bounds[i][1] < mark[0]) {
return 0;
} else {
mark[0] = Math.max(mark[0], bounds[i][0]);
mark[1] = Math.min(mark[1], bounds[i][1]);
}
}
return mark[1] - mark[0] + 1;
}
}
100587. Find Minimum Cost to Remove Array Elements
给你一个整数数组 nums。你的任务是在每一步中执行以下操作之一，直到 nums 为空，从而移除 所有元素 ：
- 从 nums 的前三个元素中选择任意两个元素并移除它们。此操作的成本为移除的两个元素中的 最大值 。
- 如果 nums 中剩下的元素少于三个，则一次性移除所有剩余元素。此操作的成本为剩余元素中的 最大值 。
返回移除所有元素所需的最小成本。
测试样例：
输入：nums = [6,2,8,4]
输出：12
解释：初始时，nums = [6, 2, 8, 4]。
- 在第一次操作中，移除 nums[0] = 6 和 nums[2] = 8，操作成本为 max(6, 8) = 8。现在，nums = [2, 4]。
- 在第二次操作中，移除剩余元素，操作成本为 max(2, 4) = 4。
移除所有元素的成本为 8 + 4 = 12。这是移除 nums 中所有元素的最小成本。所以输出 12。
解答：动态规划，直接计算保留某个数的情况下，最小成本。
class Solution {
public int minCost(int[] nums) {
if (nums.length == 1) return nums[0];
else if (nums.length == 2) return Math.max(nums[0], nums[1]);
int[] cur = {0};
for (int i = 1; i < nums.length && i + 1 < nums.length; i = i + 2) {
int[] next = new int[i + 2];
Arrays.fill(next, Integer.MAX_VALUE);
for (int j = 0; j < i; ++j) {
next[j] = Math.min(next[j], cur[j] + Math.max(nums[i], nums[i + 1]));
next[i] = Math.min(next[i], cur[j] + Math.max(nums[j], nums[i + 1]));
next[i + 1] = Math.min(next[i + 1], cur[j] + Math.max(nums[j], nums[i]));
}
cur = next;
}
if (nums.length % 2 == 0) {
int last = nums[nums.length - 1];
int res = Integer.MAX_VALUE;
for (int i = 0; i < cur.length; ++i) {
res = Math.min(cur[i] + Math.max(nums[i], last), res);
}
return res;
} else {
int res = Integer.MAX_VALUE;
for (int i = 0; i < cur.length; ++i) {
res = Math.min(cur[i] + nums[i], res);
}
return res;
}
}
}100593. Permutations IV
给你两个整数 n 和 k，一个 交替排列 是前 n 个正整数的排列，且任意相邻 两个 元素不都为奇数或都为偶数。
返回第 k 个 交替排列 ，并按 字典序 排序。如果有效的 交替排列 少于 k 个，则返回一个空列表。
测试样例：
输入：n = 4, k = 6
输出：[3,4,1,2]
解答：有点类似数位数组的逻辑，看能不能填入数字
class Solution {
private static final int[] failed = {};
public int[] permute(int n, long k) {
int[] res = new int[n];
boolean[] isUsed = new boolean[n + 1];
int odd = (n - 1) / 2 + 1, even = n / 2;
int last = 0;
for (int i = 0; i < n; ++i) {
last ^= 1;
if (i == 0 && odd == even) {
long calculate = removeOneOff(k, odd - 1, even);
for (int j = 1; j <= n; ++j) {
if (k <= calculate) {
res[i] = j;
if (res[i] % 2 == 0) {
even -= 1;
} else {
odd -= 1;
}
isUsed[j] = true;
last = res[0] % 2;
break;
} else {
k -= calculate;
}
}
} else {
int start;
if (last == 0) {
start = 2;
even -= 1;
} else {
start = 1;
odd -= 1;
}
long calculate = removeOneOff(k, odd, even);
for (int j = start; j <= n; j += 2) {
if (!isUsed[j]) {
if (k <= calculate) {
res[i] = j;
isUsed[j] = true;
break;
} else {
k -= calculate;
}
}
}
}
if (res[i] == 0) return failed;
}
return res;
}
private long removeOneOff(long k, int first, int second) {
long cur = 1;
int total = first + second;
for (int i = 0; i < total; ++i) {
if (i % 2 == 0 && first != 0) {
cur *= first;
first--;
} else if (i % 2 == 1 && second != 0) {
cur *= second;
second--;
}
if (cur > k) {
return cur;
}
}
return cur;
}
}