面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
https://leetcode.cn/studyplan/top-interview-150/
125. 验证回文串
125. 验证回文串
STL容器
思路：
- 遍历输入的字符串，将其中的字母字符转换为小写，并保留数字字符，放入另一个字符串
s1中。- 将
s1复制给另一个字符串s2。- 将
s1反转，得到逆序字符串。- 比较原字符串
s1和逆序字符串s2是否相等，若相等则返回true，否则返回false。
class Solution {
public:
bool isPalindrome(string s) {
string s1;
for(auto &c : s) {
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
{
s1 += tolower(c);
}
else if(c >= '0' && c <= '9')
{
s1 += c;
}
}
string s2;
s2=s1;
reverse(s1.begin(),s1.end());
if(s1 == s2)
return true;
else
return false;
}
};双指针
思路：
- 遍历输入的字符串，将其中的字母字符转换为小写，并保留数字字符，放入另一个字符串
s1中。- 初始化两个指针
left和right分别指向s1的开头和结尾。- 使用双指针方法，依次比较
left和right指向的字符，如果不相等，则返回false；如果相等，则继续向中间移动指针。- 如果遍历完成后都没有出现不相等的情况，说明该字符串是回文字符串，返回
true。
class Solution {
public:
bool isPalindrome(string s) {
string s1;
for(auto &c : s) {
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
{
s1 += tolower(c);
}
else if(c >= '0' && c <= '9')
{
s1 += c;
}
}
int left = 0;
int right = s1.length()-1;
while(left<right)
{
if(s1[left] != s1[right])
return false;
++left;
--right;
}
return true;
}
};392. 判断子序列
392. 判断子序列
思路：
- 初始化两个指针
i和j分别指向字符串s和t的起始位置。- 遍历字符串
t，当字符t[j]等于字符s[i]时，将两个指针都向后移动一位。- 如果最终
i移动到了s的末尾，说明s是t的子序列，返回true；否则，返回false。
class Solution {
public:
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
while(i<s.size()&&j<t.size())
{
if(s[i]==t[j])
i++;
j++;
}
if(i==s.size())
return true;
return false;
}
};167. 两数之和 II - 输入有序数组
167. 两数之和 II - 输入有序数组
思路：
- 使用双指针，一个指针
i指向数组的起始位置，另一个指针j指向数组的末尾位置。- 在每次迭代中，计算指针
i和指针j指向的元素之和numbers[i] + numbers[j]。- 如果和大于目标值
target，则将指针j向左移动一位，以减小和的值。- 如果和小于目标值
target，则将指针i向右移动一位，以增加和的值。- 如果和等于目标值
target，则找到了符合条件的数对，将它们的索引加1并加入结果数组中，然后退出循环。(因为只有一对正确的答案)- 最终返回结果数组。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int>res;
int i=0;int j=numbers.size()-1;
while(i<j)
{
if(numbers[i]+numbers[j]>target)
j--;
else if(numbers[i]+numbers[j]<target)
i++;
else
{
res.push_back(i+1);
res.push_back(j+1);
break;
}
}
return res;
}
};11. 盛最多水的容器
11. 盛最多水的容器
思路：
- 使用双指针，一个指针
i指向数组的起始位置，另一个指针j指向数组的末尾位置。- 在每次迭代中，计算当前容器的容量，即
(j - i) * min(height[i], height[j])。- 每次计算完容量后，更新记录的最大容量
mx，将当前容量与mx比较取较大值。- 如果
height[i] < height[j]，则移动指针i向右一位；否则移动指针j向左一位。- 重复步骤 2 到 4，直到指针
i和j相遇为止。- 返回记录的最大容量
mx。
class Solution {
public:
int maxArea(vector<int>& height) {
int i=0;
int j=height.size()-1;
int mx=0,s=0;
while(i<j)
{
s=(j-i)*min(height[i],height[j]);
mx=max(mx,s);
if (height[i] < height[j])
{
i++;
} else {
j--;
}
}
return mx;
}
};15. 三数之和
15. 三数之和
思路：
- 首先对数组进行排序，这样可以方便地使用双指针来遍历数组。
- 然后使用三个指针
i,left,right分别指向排序后数组中的每个元素、当前元素的下一个元素和数组末尾元素。- 在每一轮循环中，固定指针
i，并初始化left = i + 1和right = n - 1，其中n是数组的长度。- 在
left和right指针确定的范围内，使用双指针技巧来寻找和为 0 的两个数。- 如果找到了满足条件的三元组，则将其加入结果集中，并且需要注意去重。
- 继续遍历数组，直到
i指针到达倒数第三个元素为止。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1;
int right = n - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
res.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right - 1])
right--;
left++;
right--;
}
else if (sum < target)
{
left++;
}
else
{
right--;
}
}
}
return res;
}
};
![[C++]红黑树](https://img-blog.csdnimg.cn/direct/b39fa07b98c941d2bda8d0915e89aaf0.png)
