雙周賽 109
T1. 檢查數(shù)組是否是好的（Easy）
- 標(biāo)簽：模擬、排序
T2. 將字符串中的元音字母排序（Medium）
- 標(biāo)簽：模擬、排序
T3. 訪問數(shù)組中的位置使分?jǐn)?shù)最大（Medium）
- 標(biāo)簽：動(dòng)態(tài)規(guī)劃
T4. 將一個(gè)數(shù)字表示成冪的和的方案數(shù)（Medium）
- 標(biāo)簽：動(dòng)態(tài)規(guī)劃、01 背包
T1. 檢查數(shù)組是否是好的（Easy）
https://leetcode.cn/problems/check-if-array-is-good/
題解（模擬）
簡單模擬題。
先排序后依次驗(yàn)證，最后驗(yàn)證尾數(shù) N。
class Solution {
public:
bool isGood(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 1; i++) {
if (i + 1 != nums[i]) return false;
}
return nums[n - 1] == n - 1;
}
};
class Solution:
def isGood(self, nums: List[int]) -> bool:
return sorted(nums) == (list(range(1, len(nums))) + [len(nums) - 1])
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
瓶頸在排序；
- 空間復(fù)雜度：
排序遞歸?？臻g。
T2. 將字符串中的元音字母排序（Medium）
https://leetcode.cn/problems/sort-vowels-in-a-string/
題解（模擬 + 排序）
先抽取元音字母排序，再填充到結(jié)果數(shù)組中，如果使用桶排序，可以優(yōu)化時(shí)間復(fù)雜度到 O(n)。
class Solution {
public:
string sortVowels(string s) {
unordered_set<char>st{'a','e','i','o','u','A','E','I','O','U'};
string temp = "";
for(char c : s){
if(st.count(c)) temp += c;
}
// 排序
sort(temp.begin(), temp.end());
// 輸出
int i = 0;
for(char &c : s){ // 原地修改
if(st.count(c)) c = temp[i++];
}
return s;
}
};
桶排序：
class Solution {
public:
string sortVowels(string s) {
unordered_set<char> st {'a','e','i','o','u','A','E','I','O','U'};
// 桶排序（有序字典）
map<char, int> vowelCounts;
for (char c : s) {
if (st.count(c)) {
vowelCounts[c]++;
}
}
// 輸出
for (char& c : s) { // 原地修改
if (st.count(c)) {
c = vowelCounts.begin()->first;
if (--vowelCounts.begin()->second == 0) {
vowelCounts.erase(vowelCounts.begin());
}
}
}
return s;
}
};
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
；
- 空間復(fù)雜度：
T3. 訪問數(shù)組中的位置使分?jǐn)?shù)最大（Medium）
https://leetcode.cn/problems/visit-array-positions-to-maximize-score/
題解（動(dòng)態(tài)規(guī)劃）
比較明顯的動(dòng)態(tài)規(guī)劃問題，定義 dp[i][j] 表示到 [i] 為止的最大序列和，其中：
- dp[i][0] 表示尾數(shù)為偶數(shù)的序列
- dp[i][1] 表示尾數(shù)為奇數(shù)的序列
那么對(duì)于 nums[i] 來說：
- 如果 nums[i] 是偶數(shù)，那么它可以無成本地添加到尾數(shù)為偶數(shù)的序列 dp[i - 1][0] 中，也可以在消耗成本 x 的情況下添加到尾數(shù)為奇數(shù)的序列 dp[i - 1][1] 中；
- 如果 nums[i] 是奇數(shù)，那么它可以無成本地添加到尾數(shù)為奇數(shù)的序列 dp[i - 1][0] 中，也可以在消耗成本 x 的情況下添加到尾數(shù)為偶數(shù)的序列 dp[i - 1][1] 中。
于是有：
- dp[i][0] = Math.max(dp[i - 1][0] + nums[i], dp[i - 1][1] + nums[i] - x)
- dp[i][1] = Math.max(dp[i - 1][1] + nums[i], dp[i - 1][0] + nums[i] - x)
另外，由于題目要求起始點(diǎn)必須從 nums[0] 開始，于是我們區(qū)分兩種初始狀態(tài)：
- 如果 nums[0] 為偶數(shù)，初始狀態(tài) dp[0][0] = nums[i]，dp[0][1] = -INF，此處 INF 表示無效，在首次選擇奇數(shù)時(shí)一定會(huì)選擇從 dp[i - 1][0] 轉(zhuǎn)移的分支，確保從 nums[0] 開始；
- 如果 nums[0] 為奇數(shù)，初始狀態(tài) dp[0][0] = -INF，dp[0][1] = nums[0]，此處 INF 表示無效，在首次選擇偶數(shù)時(shí)一定會(huì)選擇從 dp[i - 1][1] 轉(zhuǎn)移的分支，確保從 nums[0] 開始；
最后，由于每次迭代只關(guān)心 i - 1 層子狀態(tài)，可以使用滾動(dòng)數(shù)組優(yōu)化空間。
class Solution {
fun maxScore(nums: IntArray, x: Int): Long {
val INF = -0x3F3F3F3FL // 減少判斷
val n = nums.size
var ret = nums[0].toLong()
// 初始狀態(tài)
val dp = if (nums[0] % 2 == 0) {
longArrayOf(nums[0].toLong(), INF)
} else {
longArrayOf(INF, nums[0].toLong())
}
// dp[i] 表示到 [i] 為止的最大序列和
for (i in 1 until n) {
if (nums[i] % 2 == 0) {
// 偶數(shù)
dp[0] = Math.max(dp[0] + nums[i], dp[1] + nums[i] - x)
} else {
// 奇數(shù)
dp[1] = Math.max(dp[1] + nums[i], dp[0] + nums[i] - x)
}
}
return Math.max(dp[0], dp[1])
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
僅使用常量級(jí)別空間。
T4. 將一個(gè)數(shù)字表示成冪的和的方案數(shù)（Medium）
https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/
題解（01 背包）
原問題等價(jià)于：求在體積為 n 的背包中可以選擇的方案數(shù)
由于題目要求方案中的數(shù)字不能存在重復(fù)數(shù)，例如 [1, 1, 1] 的方案是非法的，所以每個(gè)數(shù)最多只能選擇一次，即只有選和不選兩個(gè)狀態(tài)，這容易聯(lián)想到 01 背包模型。
- 物品：數(shù)字
- 物品體積：數(shù)字對(duì) x 的冪
- 背包大?。簄
令 dp[i][j] 表示枚舉到 [i] 為止且選擇體積為 j 的方案數(shù)，則對(duì)于 i 來說有 2 個(gè)選擇：
- 不選：
- 選：
class Solution {
fun numberOfWays(n: Int, x: Int): Int {
val MOD = 1000000007
// 預(yù)處理備選數(shù)
val nums = LinkedList<Int>()
var i = 1
while (true) {
val e = Math.pow(1.0 * i, 1.0 * x).toInt()
if (e > n) break
nums.add(e)
i++
}
val m = nums.size
// 01 背包 dp[i][j] 表示枚舉到 [i] 為止且選擇體積為 j 的方案數(shù)
val dp = Array(m + 1) { IntArray(n + 1) }
// 體積為 0 的方案數(shù)為 1
for (i in 0 .. m) dp[i][0] = 1
// 枚舉物品
for (i in 1 .. m) {
for (j in 1 .. n) {
// 不選
dp[i][j] = dp[i - 1][j]
// 選
if (j >= nums[i - 1]) dp[i][j] = (dp[i][j] + dp[i - 1][j - nums[i - 1]]) % MOD
}
}
return dp[m][n] // 枚舉到末尾且選擇體積為 n 的方案數(shù)
}
}
取消物品維度優(yōu)化空間復(fù)雜度：
class Solution {
fun numberOfWays(n: Int, x: Int): Int {
...
val m = nums.size
// 01 背包 dp[i][j] 表示枚舉到 [i] 為止且選擇體積為 j 的方案數(shù)
val dp = IntArray(n + 1)
// 體積為 0 的方案數(shù)為 1
dp[0] = 1
// 枚舉物品
for (i in 1 .. m) {
for (j in n downTo nums[i - 1]) { // 逆序（會(huì)使用子問題）
dp[j] = (dp[j] + dp[j - nums[i - 1]]) % MOD
}
}
return dp[n] // 枚舉到末尾且選擇體積為 n 的方案數(shù)
}
}
在預(yù)處理的過程直接進(jìn)行背包邏輯也可以：
class Solution {
fun numberOfWays(n: Int, x: Int): Int {
val MOD = 1000000007
val dp = IntArray(n + 1)
dp[0] = 1
// 枚舉物品
var i = 1
while (true) {
val e = Math.pow(1.0 * i, 1.0 * x).toInt()
if (e > n) break
for (j in n downTo e) { // 逆序（會(huì)使用子問題）
dp[j] = (dp[j] + dp[j - e]) % MOD
}
i++
}
return dp[n] // 枚舉到末尾且選擇體積為 n 的方案數(shù)
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
其中 m 為
，動(dòng)態(tài)規(guī)劃節(jié)點(diǎn)時(shí)間復(fù)雜度為
- 空間復(fù)雜度：
推薦閱讀
LeetCode 上分之旅系列往期回顧：
