前言：
记录一下对左程云系列算法课程--算法讲解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 == n
return 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位置起依次迭代了。
学习算法是漫长且痛苦的过程，且可能长期伴随着焦虑。但这是始终要面对的，毕竟是自己选择的路。算法难吗？难。需要天赋吗？需要一点。自己有天赋没？不知道。在我看来，天赋只有在经历过无数努力且踩在巨人的肩膀上才能体现的东西。更何况天赋的高山永无顶点，只要实现自我超越，就是有价值的。愿自己能在学习技术和算法的路上一直走下去。