前言：

记录一下对左程云系列算法课程--算法讲解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位置起依次迭代了。

学习算法是漫长且痛苦的过程，且可能长期伴随着焦虑。但这是始终要面对的，毕竟是自己选择的路。算法难吗？难。需要天赋吗？需要一点。自己有天赋没？不知道。在我看来，天赋只有在经历过无数努力且踩在巨人的肩膀上才能体现的东西。更何况天赋的高山永无顶点，只要实现自我超越，就是有价值的。愿自己能在学习技术和算法的路上一直走下去。