刷题日记
目录leetcode 算法基础 双指针
844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
一开始看到这到题就想到了栈的特点，试了一下成功AC了
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<char> st1;
stack<char> st2;
for (int i = 0; i < s.size(); i++) {
if(s[i] == '#')
{
if(!st1.empty()) {
st1.pop();
continue;
} else {
continue;
}
}
st1.push(s[i]);
}
for (int i = 0; i < t.size(); i++) {
if(t[i] == '#')
{
if(!st2.empty()) {
st2.pop();
continue;
} else {
continue;
}
}
st2.push(t[i]);
}
if (st1.size() != st2.size()){
return false;
} else {
while(!st1.empty()) {
if (st1.top() != st2.top()) {
return false;
}
st1.pop();
st2.pop();
}
return true;
}
}
};
看了看题解有另外一种双指针的解法
class Solution {
public:
bool backspaceCompare(string s, string t) {
return getRealString(s)==getRealString(t);
}
private:
string getRealString(string s){
int slowIndex = 0; // 双指针，成功搞定！
int fastIndex = 0;
for(;fastIndex < s.size();fastIndex++){
if(s[fastIndex]=='#'){
if(slowIndex > 0){
slowIndex--;
}
}
else{
s[slowIndex++] = s[fastIndex];
}
}
return s.substr(0,slowIndex);
}
};
思路也很简单 就是利用快慢指针的思路 slowIndex 代表着新字符串的结尾 当 fastIndex 所指元素 不为 # 时 slowIndex 里的内容和 fastIndex 同步更新，相同时slowIndex向前移动代表删除操作，fastIndex还是继续向前重复操作最后返回从开始到 slowIndex 的字符串。
986. 区间列表的交集
给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
vector<vector<int>> result;
int i = 0, j = 0;
while (i < firstList.size() && j < secondList.size()) {
int start = max(firstList[i][0], secondList[j][0]);
int end = min(firstList[i][1], secondList[j][1]);
if (start <= end) {
result.push_back({start, end});
}
if(start == firstList[i][0]) {
if(start == firstList[i][0] && end == firstList[i][1]) {
i++;
} else {
j++;
}
}
else if (start == secondList[j][0]) {
if (start == secondList[j][0] && end == secondList[j][1]) {
j++;
}
else {
i++;
}
}
}
return result;
}
};
参考了一下大佬的思路后自己复现
结果在判断区间向下继续的时候绕了一个大圈
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
vector<vector<int>> result;
int i = 0, j = 0;
while (i < firstList.size() && j < secondList.size()) {
int start = max(firstList[i][0], secondList[j][0]);
int end = min(firstList[i][1], secondList[j][1]);
if (start <= end) {
result.push_back({start, end});
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return result;
}
};
其实只要判断右区间就可以
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
原题
纯靠自己写的AC的中等题（哭死）
class Solution {
public:
int maxArea(vector<int>& height) {
int start = 0;
int end = height.size() - 1;
int maxArea = 0;
while (start != end) {
int Area = min(height[start], height[end]) * (end - start);
maxArea>Area? : maxArea = Area;
height[start]>height[end]?end--:start++;
}
return maxArea;
}
};
对撞指针加贪心的思路以求最大容量
