6930. Check if Array is Good
给你一个整数数组 nums ，如果它是数组 base[n] 的一个排列，我们称它是个 好 数组。
base[n] = [1, 2, ..., n - 1, n, n] （换句话说，它是一个长度为 n + 1 且包含 1 到 n - 1 恰好各一次，包含 n 两次的一个数组）。比方说，base[1] = [1, 1] ，base[3] = [1, 2, 3, 3] 。
如果数组是一个好数组，请你返回 true ，否则返回 false 。
注意：数组的排列是这些数字按任意顺序排布后重新得到的数组。
测试样例
输入：nums = [2,1,3]
输出：false
解释：因为数组的最大元素是 3 ，唯一可以构成这个数组的 base[n] 对应的 n = 3 。但是 base[3] 有 4 个元素，但数组 nums 只有 3 个元素，所以无法得到 base[3] = [1, 2, 3, 3] 的排列，所以答案为 false 。
解答：排序一下，测试一下当前数组是否一个好数组。
class Solution {
public boolean isGood(int[] nums) {
if (nums.length <= 1) return false;
Arrays.sort(nums);
for (int i = 0; i < nums.length; ++i) {
if (i < nums.length - 1) {
if (i + 1 != nums[i]) return false;
} else {
if (nums[i] != i) return false;
}
}
return true;
}
}6926. Sort Vowels in a String
给你一个下标从 0 开始的字符串 s ，将 s 中的元素重新 排列 得到新的字符串 t ，它满足：
- 所有辅音字母都在原来的位置上。更正式的，如果满足 0 <= i < s.length 的下标 i 处的 s[i] 是个辅音字母，那么 t[i] = s[i] 。
元音字母都必须以他们的 ASCII 值按 非递减 顺序排列。更正式的，对于满足 0 <= i < j < s.length 的下标 i 和 j ，如果 s[i] 和 s[j] 都是元音字母，那么 t[i] 的 ASCII 值不能大于 t[j] 的 ASCII 值。
请你返回结果字母串。
元音字母为 'a' ，'e' ，'i' ，'o' 和 'u' ，它们可能是小写字母也可能是大写字母，辅音字母是除了这 5 个字母以外的所有字母。
测试样例：
输入：s = "lEetcOde"
输出："lEOtcede"
解释：
'E' ，'O' 和 'e' 是 s 中的元音字母，'l' ，'t' ，'c' 和 'd' 是所有的辅音。将元音字母按照 ASCII 值排序，辅音字母留在原地。
解答: 按照题意，第一次遍历字符串将所有元音字母找出并排序。第二次遍历字符串，如果当前不是元音就直接append，否则从元音列表中寻找ASCII最小的元音。
class Solution {
private static final char[] vowels = {'a', 'e', 'i', 'o', 'u'};
public String sortVowels(String s) {
List<Character> vowels = new ArrayList<>();
for (int i = 0; i < s.length(); ++i) {
if (isVowels(s.charAt(i))) {
vowels.add(s.charAt(i));
}
}
Collections.sort(vowels);
int p = 0;
StringBuilder res = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
if (isVowels(s.charAt(i))) {
res.append(vowels.get(p++));
} else {
res.append(s.charAt(i));
}
}
return res.toString();
}
private boolean isVowels(char c) {
if (c >= 'A' && c <= 'Z') {
return isVowels((char) (c - 'A' + 'a'));
}
for (char v : vowels) {
if (c == v) return true;
}
return false;
}
}6931. Visit Array Positions to Maximize Score
给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。
你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：
- 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
- 对于你访问的位置 i ，你可以获得分数 nums[i] 。
- 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。
请你返回你能得到的 最大 得分之和。
注意 ，你一开始的分数为 nums[0] 。
测试样例：
输入：nums = [2,3,6,1,9,2], x = 5
输出：13
解释：
我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。总得分为：2 + 6 + 1 + 9 - 5 = 13 。
解答: 这道题目是最容易翻车的一道题目。首先它的返回是一个long，需要注意，不要用int了。第二nums[0]是一开始的数字，所以一定要记录0号位置。其他就比较简单了，这道题目是一道典型的动态规划。从后向前遍历数组，记录当前位置的最大maxEven和maxOdd值。
class Solution {
public long maxScore(int[] nums, int x) {
int len = nums.length;
long maxEven = 0, maxOdd = 0;
for (int i = len - 1; i >= 0; --i) {
if (i == 0) {
if (nums[i] % 2 == 0) {
return Math.max(nums[i] + maxEven, maxOdd + nums[i] - x);
} else {
return Math.max(nums[i] + maxOdd, maxEven + nums[i] - x);
}
}
if (nums[i] % 2 == 0) {
maxEven = Math.max(maxEven, Math.max(nums[i] + maxEven, maxOdd + nums[i] - x));
} else {
maxOdd = Math.max(maxOdd, Math.max(nums[i] + maxOdd, maxEven + nums[i] - x));
}
}
return -1;
}
}6922. Ways to Express an Integer as Sum of Powers
给你两个 正 整数 n 和 x 。
请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1^x + n2^x + ... + nk^x 。
由于答案可能非常大，请你将它对 10^9 + 7 取余后返回。
比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2^3 + 3^3 + 5^3 。
测试样例：
输入：n = 10, x = 2
输出：1
我们可以将 n 表示为：n = 3^2 + 1^2 = 10 。这是唯一将 10 表达成不同整数 2 次方之和的方案。
解答: 这道题目，范围非常小，每个数字也只能使用一次。利用背包动态规划就能获得结果。
class Solution {
private static final int mod = 1_000_000_007;
public int numberOfWays(int n, int x) {
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; mul(i, x) <= n; ++i) {
int tmp = mul(i, x);
for (int j = n; j >= tmp; --j) {
dp[j] = (dp[j] + dp[j - tmp]) % mod;
}
}
return dp[n];
}
private int mul(int num, int x) {
long tmp = 1;
for (int i = 0; i < x; ++i) {
tmp *= num;
}
if (tmp <= 300) {
return (int) tmp;
} else {
return 1000;
}
}
}