题单介绍:
精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。
目录
题单介绍:
题目:5. 最长回文子串 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过过过过啦!!!!
题目:11. 盛最多水的容器 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过过过过啦!!!!
写在最后:
题目:5. 最长回文子串 - 力扣(Leetcode)
题目的接口:
class Solution {
public:
string longestPalindrome(string s) {
}
};
解题思路:
这道题我看很多题解都是用动态规划,
我动态规划不好,所以,我这道题用的是中心扩散的思路做的,
所以我就讲一讲中心扩散的思路:
直接遍历数组,
以遍历的时候的每个下标为中心,向两边扩散,
计算出这个回文串的大小,如果当前的回文串最长,
就更新他的:起始边界start,结束边界end,长度max_len。
最后将最长的回文串用substr截出来返回即可。
代码如下:
代码:
class Solution { public: string longestPalindrome(string s) { int len = s.size(); if(len <= 1) return s; //特殊情况直接返回 int start = 0; int end = 0; int max_len = 0; for(int i = 0; i < len; i++) { //遍历字符串 int len1 = exp_center(s, i, i); //aba情况 int len2 = exp_center(s, i, i + 1); //abba情况 max_len = max(max(len1, len2), max_len); //更新最大值 if(max_len > end - start + 1) { //如果这次是最大值,更新边界 start = i - ((max_len - 1) / 2); //考虑abba情况的下标,所以要-1 end = i + (max_len / 2); } } return s.substr(start, max_len); } private: //计算当前回文串的大小 int exp_center(const string& s, int l, int r) { while(l >= 0 && r < s.size() && s[l] == s[r]) { l--; r++; } return r - l - 1; } };
过过过过啦!!!!
题目:11. 盛最多水的容器 - 力扣(Leetcode)
题目的接口:
class Solution { public: int maxArea(vector& height) { } };
解题思路:
这道题的解题思路很巧妙,我一开始也是想不出来,
具体是这样子的:
我们通过双指针来解决,
一个指针在最左,一个指针在最右:
然后,比较两个指针指向的值的大小,
更新小的那边的指针:
然后每次更新最大的面积即可,
这个原理用通俗点的话来讲就是:
每次更新指针范围,盛水的容器长度肯定会变小,想让盛水量更多,找最大值,
只有让更矮的线更新,继续找更高的线才有可能让盛水量更多。
代码逻辑比较简单,我就不加注释了。
代码如下:
代码:
class Solution { public: int maxArea(vector& height) { int left = 0, right = height.size() - 1; int max_val = 0; while(left != right) { max_val = max(max_val, min(height[left], height[right]) * (right - left)); if(height[left] < height[right]) { left++; } else right--; } return max_val; } };
过过过过啦!!!!
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~