wordpress内容伪原创,文山seo,seo公司推广,个人怎样注册网站前言#xff1a;
记录一下对左程云系列算法课程--算法讲解066【必备】的剩余习题的学习。本文主要简单记录个人学习心得和提供C版本代码。如需要题目的细致讲解#xff0c;请前往原视频。
涉及内容#xff1a;
动态规划、三指针、
参考视频#xff1a;
左程云--算法讲…前言
记录一下对左程云系列算法课程--算法讲解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_queueunsigned long long, vectorunsigned 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) {vectorint 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();vectorint 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 1len用于记录当前有效字串最大长度而我们对26个字母都存放对应字母结尾时可以构成的有效子串个数最后循环完毕累加即可。可能表述不是很清楚这里还是推荐一下左老师的原视频。
示例代码
class Solution {
public:int findSubstringInWraproundString(string s) {int n s.size();vectorint ss(n);for(int i 0; i n; i){ss[i] s[i] - a;}vectorint 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) {vectorint 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位置起依次迭代了。
学习算法是漫长且痛苦的过程且可能长期伴随着焦虑。但这是始终要面对的毕竟是自己选择的路。算法难吗难。需要天赋吗需要一点。自己有天赋没不知道。在我看来天赋只有在经历过无数努力且踩在巨人的肩膀上才能体现的东西。更何况天赋的高山永无顶点只要实现自我超越就是有价值的。愿自己能在学习技术和算法的路上一直走下去。
