题单介绍:
精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。
目录
题单介绍:
题目:739. 每日温度 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过过过过啦!!!!
题目:647. 回文子串 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过过过过啦!!!!
写在最后:
题目:739. 每日温度 - 力扣(Leetcode)
题目的接口:
class Solution { public: vector dailyTemperatures(vector& temperatures) { } };
解题思路:
这道题,我看一眼之后,
马上暴力开干,然后,
就超时了:
class Solution { public: vector dailyTemperatures(vector& temperatures) { vector v; for(int i = 0; i < temperatures.size(); i++) { int cnt = 0; for(int j = i + 1; j <= temperatures.size(); j++) { if(j == temperatures.size()) { v.push_back(0); break; } cnt++; if(temperatures[j] > temperatures[i]) { v.push_back(cnt); break; } } } return v; } };
然后就超时了:
实际上这道题需要用单调栈来做,
(我后来在题解看到,优化后的暴力好像也能过)
具体思路如下:
初始化返回数组的每个元素为0
遍历数组,然后入栈,保持这个单调栈处于递减状态,
如果遇到有比栈顶大的值需要入栈,就通过下标相减得到间隔天数,
然后让原先栈顶的值出栈即可。
代码如下:
代码:
class Solution { public: vector dailyTemperatures(vector& temperatures) { vector ans(temperatures.size(), 0); //返回数组元素初始化成0 stack st; for(int i = 0; i < temperatures.size(); i++) { while(!st.empty() && temperatures[i] > temperatures[st.top()]) { int top = st.top(); //记录栈顶值下标 st.pop(); //栈顶出栈 ans[top] = i - top; //下标相减得距离 } st.push(i); //遍历入栈 } return ans; } };
过过过过啦!!!!
题目:647. 回文子串 - 力扣(Leetcode)
题目的接口:
class Solution { public: int countSubstrings(string s) { } };
解题思路:
这道题一眼暴力,
暴力小王子请求出战,
结果,你还真能用暴力过啊,
看一眼题解,用的是中心扩散,
恕我直言,那不就是暴力吗,
这道题肯定是能用动态规划的,不过我不会用,
那就暴力吧,
代码如下:
代码:
class Solution { public: int countSubstrings(string s) { int cnt = 0; for(int i = 0; i < s.size(); i++) { string tmp; for(int j = i; j < s.size(); j++) { tmp += s[j]; if(isHui(tmp)) cnt++; } } return cnt; } private: bool isHui(const string& s) { int left = 0, right = s.size() - 1; while(left <= right) { if(s[left] != s[right]) return false; left++; right--; } return true; } };
过过过过啦!!!!
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~