LCP 19.秋葉收藏集
題目鏈接
演算法
動態規劃
時間復雜度O(n)
1.題目要求最終形成[紅、黃、紅]三部分，每部分數量可以不相等，問最終調整運算元量最小是多少，這道題一開始考慮暴力去做，列舉兩個分界點，即紅黃，黃紅之間的分界點的位置，但由于長度是1e5，時間復雜度為O(n^2)級別，故此法作廢，
2.通過查看官方題解，了解到這道題可以使用動態規劃去做，可以將時間復雜度優化到O(n)級別，為方便查閱復習，現結合自己的理解寫下該題解，具體如下：
可以定義一個陣列f[i][j]，表示符合要求的最小的運算元，即使leaves[]陣列從0到i的值符合題目規范的最小的運算元，i的范圍是[0,leaves.length)，j的范圍是[0,2]，其中0表示當前葉子為紅色(在黃色前面)，1表示當前葉子為黃色，2表示當前葉子為紅色(在黃色后面)，
初始時f[0][0]的值會由第一片葉子的顏色決定，下面分情況討論j的不同值的情況：
(1)當j=0時，f[i][0] = f[i-1][0] + isYellow(i)，isYellow函式會根據葉子的顏色回傳對應的布林值；同時需注意j=0這種情況下i最大為leaves.length-3，因為題目要求每部分葉子數量至少為1個；
(2)當j=1時，f[i][1] = min(f[i-1][0],f[i-1][1]) + isRed(i) ，該葉子左面的葉子的顏色可能是紅色，也可能是黃色，取形成前面兩種情況操作的最小值即可，同時需要判斷當前葉子是否黃色，在這種情況下i最大值為leaves.length-2，最小值為1；
(3)當j=2時,f[i][2] = min(f[i-1][1],f[i-1][2]) + isYellow(i);，該葉子左面的葉子的顏色可能是紅色，也可能是黃色，取形成前面兩種情況操作的最小值即可，同時需要判斷當前葉子是否為紅色，在這種情況下i最大值為leaves.length-1，最小值為2；
最侄訓傳結果為f[leaves.length - 1]，
C++代碼
//一開始是用函式呼叫的，但超時，故直接判斷
class Solution {
public:
/*
bool isYellow(string leaves, int u){
return (leaves[u] == 'y');
}
bool isRed(string leaves, int u){
return (leaves[u] == 'r');
}
*/
int minimumOperations(string leaves) {
int len = leaves.length();
vector<vector<int> > f(len, vector<int>(3, INT_MAX));
//f[0][0] = isYellow(leaves, 0);
f[0][0] = (leaves[0] == 'y');
for(int i = 1; i < len; i++){
int yellow = (leaves[i] == 'y');
int red = (leaves[i] == 'r');
if(i < len - 2){
//f[i][0] = f[i-1][0] + (int)isYellow(leaves, i);
f[i][0] = f[i-1][0] + yellow;
}
if(i >= 1 && i < len - 1){
//f[i][1] = min(f[i-1][0],f[i-1][1]) + (int)isRed(leaves, i);
f[i][1] = min(f[i-1][0],f[i-1][1]) + red;
}
if(i >= 2){
//f[i][2] = min(f[i-1][1],f[i-1][2]) + (int)isYellow(leaves, i);
f[i][2] = min(f[i-1][1],f[i-1][2]) + yellow;
}
}
return f[len - 1][2];
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/178834.html
標籤：其他