前言：

記錄一下對左程云系列算法課程--算法講解066【必備】的剩余習題的學習。本文主要簡單記錄個人學習心得和提供C++版本代碼。如需要題目的細致講解，請前往原視頻。

涉及內容：

動態規劃、三指針、

參考視頻：

左程云--算法講解066【必備】從遞歸入手一維動態規劃

題目列表：

1.Leetcode--264. 丑數 II

2.Leetcode--32. 最長有效括號

3.Leetcode--467. 環繞字符串中唯一的子字符串

4.Leetcode--940. 不同的子序列 II

題目解答：

?1.Leetcode--264. 丑數 II

題目：

解題思考：

首先可以很好的考慮到暴力求解，我們只需要從1開始，從大到小每個數字遍歷判斷其是否是丑數然后計數即可，但很顯然這會超時。

那么我們從質因子入手，因為一個丑數（除1）外，都是由其他丑數×2 | 3 | 5 得到的，那么我們可以從1出發，會得到三個丑數：2、3、5，所以1后面的丑數就是2。接著從2出發，得到三個丑數：4、6、10，算上之前得到但是沒有使用的丑數一共是：3、4、5、6、10，所以2后面的數字應該是3，之后循環即可。從上述思路知道我們需要一個優先隊列（最小堆），關于C++中priority_queue的比較器我在這里由所記錄，按需觀看。

可以優先隊列會隨著時間的推移而變大，而且在得到最終結果時，有很多用不到的數據也會被一直存儲。例如剛才我們求第三個丑數（3）時已經計算了5個數。

通過觀察，我們可以只保存三個變量，分別指代*2、*3、*5，當對應變量被使用時，我們只需要改變這一個變量即可，即優化了優先隊列的空間，還對比較的數據范圍進行縮小化。

三版的示例代碼如下。

示例代碼：

①暴力（超時）

class Solution {
public:int nthUglyNumber(int n) {int count = 0;int num = 0;while(count < n){num++;if(isUglyNumber(num)){count++;} }//count == nreturn num;}bool isUglyNumber(int n){if(n <= 0){return false;}while(n % 2 == 0){n /= 2;}while(n % 3 == 0){n /= 3;}while(n % 5 == 0){n /= 5;}if(n == 1){return true;}return false;}
};

②優先隊列（最小堆）

class Solution {
private:struct compare{bool operator()(unsigned long long a, unsigned long long b){return a > b;}};
public:int nthUglyNumber(int n) {priority_queue<unsigned long long, vector<unsigned long long>, compare> pq;unsigned long long num = 1;int count = 1;while(count != n){count++;pq.push((unsigned long long)num * 2);pq.push((unsigned long long)num * 3);pq.push((unsigned long long)num * 5);num = pq.top();while(num == pq.top()){pq.pop();}}return num;}
};

③三指針動態規劃

class Solution {
public:int nthUglyNumber(int n) {vector<int> dp(n + 1, 0);dp[1] = 1;int i2 = 1, i3 = 1, i5 = 1;for(int i = 2; i <= n; i++){int a = dp[i2] * 2;int b = dp[i3] * 3;int c = dp[i5] * 5;dp[i] = min(min(a, b), c);if(dp[i] == a) { i2++; }if(dp[i] == b) { i3++; }if(dp[i] == c) { i5++; }}return dp[n];}
};

輔助題目與示例代碼：

這里再推薦一些相關習題，只是和本題相關，與動態規劃無關。

①Leetcode--231. 2 的冪

class Solution {
public:bool isPowerOfTwo(int n) {return n > 0 && (n & (n - 1)) == 0;}
};

②Leetcode--263. 丑數

class Solution {
public:bool isUgly(int n) {if(n <= 0){return false;}while(n % 3 == 0){n /= 3;}while(n % 5 == 0){n /= 5;}return n > 0 && (n & (n - 1)) == 0;}
};

?2.Leetcode--32. 最長有效括號

題目：

解題思考：

本題的動態規劃做法中存在著KMP算法的影子。首先對于暴力求解，我們只需要枚舉以每一位為結尾的子括號串的有效括號串長度，最后求最大值即可。但很顯然這存在重復計算，那么如何利用之前已經計算過的數據，這就是該題動態規劃做法的來歷。、

如果當前位置為左括號"("，很顯然依此結尾的字串不可能有效，對應dp數組我們記作0。

如果當前位置為右括號")"，我們可以看dp[i - 1]位置對應的有效字串長度是多少，這個時候我們只需要關注p = i - dp[i - 1] - 1這個位置是否為"("。如果是，則可以在dp[i - 1]的基礎上再加上兩個字符長度。最后判斷dp[p - 1]位置有多長的有效字符串長度，再次加上即可。

此時只需要加到dp[p - 1]即可，再左邊就不用看了，因為我們按照順序求解，dp[p - 1]的值已經是最長的有效字符串長度了。

?這里還是推薦一下原視頻的，左老師模擬了一個很長的例子幫助有效理解，最后代碼如下。

示例代碼：

class Solution {
public:int longestValidParentheses(string s) {if (s == "") { return 0; }int n = s.size();vector<int> dp(n, 0);dp[0] = 0;int ans = 0;for(int i = 1; i < n; i++){if(s[i] == ')'){int p = i - dp[i - 1] - 1;if(p >= 0 && s[p] == '('){dp[i] = dp[i - 1] + 2 + (p > 0 ? dp[p - 1] : 0);}}ans = max(ans, dp[i]);}return ans;}
};

?3.Leetcode--467. 環繞字符串中唯一的子字符串

題目：

解題思考：

最容易想到的暴力解法當然是逐個位置進行枚舉，顯然，重復計算非常多。而觀察可發現長字符串是包含短字符串的，所以很自然可以聯系到狀態方程。但這里重點不在如何建立狀態方程，狀態方程只是"果"。我們要找的是字串之間的關系，即"因"。

如果我們以每個位置作為字串的開頭去判斷是否為有效字串，則從0位置開始顯然是最復雜的，那么這時可以考慮從末位置，即從右向左，但這可能寫不順手。所以我們可以使每個位置作為字串的結尾，從左向右即可。

那么從0位置入手，很顯然其對應的字串為1。在下一個位置時，我們查看上一個位置是否能連在一起構成有效字串，如果是有效字串，則以此位置結尾的有效字串最大長度為len+ 1，len用于記錄當前有效字串最大長度，而我們對26個字母都存放對應字母結尾時，可以構成的有效子串個數，最后循環完畢累加即可。可能表述不是很清楚，這里還是推薦一下左老師的原視頻。

示例代碼：

class Solution {
public:int findSubstringInWraproundString(string s) {int n = s.size();vector<int> ss(n);for(int i = 0; i < n; i++){ss[i] = s[i] - 'a';}vector<int> dp(26, 0);int len = 1;dp[ss[0]] = 1;for(int i = 1, cur, pre; i < n; i++){cur = ss[i];pre = ss[i - 1];if((pre == 25 && cur == 0) || pre + 1 == cur){len++;}else{len = 1;}dp[cur] = max(dp[cur], len);}int ans = 0;for(int x : dp){ans += x;}return ans;}
};

?4.Leetcode--940. 不同的子序列 II

題目：

解題思考：

?本題還是看原視頻吧。主要特點在于計數和去重，cnt[idx]設計的很好。

示例代碼：

class Solution {
private:int mod = 1e9 + 7;
public:int distinctSubseqII(string s) {vector<int> cnt(26, 0);int all = 1;int newAdd;for(char c : s){int idx = c - 'a';newAdd = (all - cnt[idx] + mod) % mod;cnt[idx] = (cnt[idx] + newAdd) % mod;all = (all + newAdd) % mod;}return (all - 1 + mod) % mod;}
};

最后：

關于動態規劃的總結其實左老師也講了很多。這節課最重要的學習了動態規劃是怎樣來的，即設計純遞歸、記憶化搜索、設計遞推、空間優化。其實整個過程也就是把遞歸寫成迭代的做法。另外還有對序列的操作，作為初學者的我也很容易將每個位置所為所求序列的開頭，但是這樣會陷入0位置就是最復雜位置的困難。當我們反向思考，讓每個位置最為所求序列的結尾，這樣就可以從0位置起依次迭代了。

學習算法是漫長且痛苦的過程，且可能長期伴隨著焦慮。但這是始終要面對的，畢竟是自己選擇的路。算法難嗎？難。需要天賦嗎？需要一點。自己有天賦沒？不知道。在我看來，天賦只有在經歷過無數努力且踩在巨人的肩膀上才能體現的東西。更何況天賦的高山永無頂點，只要實現自我超越，就是有價值的。愿自己能在學習技術和算法的路上一直走下去。