LeetCode.844.986.11(双指针)

844.比较含退格的字符串

class Solution {
  public:
    bool backspaceCompare(string S, string T) {
        int sSkipNum = 0; // 记录S的#数量
        int tSkipNum = 0; // 记录T的#数量
        int i = S.size() - 1;
        int j = T.size() - 1;
        while (1) {
            while (i >= 0) { // 从后向前，消除S的#
                if (S[i] == '#')
                    sSkipNum++;
                else {
                    if (sSkipNum > 0)
                        sSkipNum--;
                    else
                        break;
                }
                i--;
            }
            while (j >= 0) { // 从后向前，消除T的#
                if (T[j] == '#')
                    tSkipNum++;
                else {
                    if (tSkipNum > 0)
                        tSkipNum--;
                    else
                        break;
                }
                j--;
            }
            // 后半部分#消除完了，接下来比较S[i] != T[j]
            if (i < 0 || j < 0)
                break; // S 或者T 遍历到头了
            if (S[i] != T[j])
                return false;
            i--;
            j--;
        }
        // 说明S和T同时遍历完毕
        if (i == -1 && j == -1)
            return true;
        return false;
    }
    // 113/113 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 70.37 % of cpp submissions (6.1 MB)
    //*一样的方法 这比怎么这么快  加了函数就慢是吧
    /*char getchar(int pos, string s) {
        if (pos < 0)
            return ' ';
        else
            return s[pos];
    }
    bool backspaceCompare(string s, string t) {
        int sDel = 0, tDel = 0;
        for (int si = s.size() - 1, ti = t.size() - 1; si >= 0 || ti >= 0;) {
            while (getchar(si, s) == '#') {
                si--;
                sDel++;
            }
            while (sDel && getchar(si, s) != '#') {
                si--;
                sDel--;
            }
            while (getchar(ti, t) == '#') {
                ti--;
                tDel++;
            }
            while (tDel && getchar(ti, t) != '#') {
                ti--;
                tDel--;
            }
            if (getchar(ti, t) == '#' || getchar(si, s) == '#')
                continue;
            else if (getchar(ti, t) == getchar(si, s)) {
                ti--;
                si--;
            } else
                return false;
        }
        return true;
    }*/
    // 113/113 cases passed (4 ms)
    // Your runtime beats 16.57 % of cpp submissions
    // Your memory usage beats 5.22 % of cpp submissions (9.7 MB)
};

986.区间列表的交集

class Solution {
  public:
    vector<vector<int>> intervalIntersection(vector<vector<int>> &firstList, vector<vector<int>> &secondList) {
        if (firstList.empty() || secondList.empty())
            return {};
        vector<vector<int>> ans;
        int f = 0, s = 0;
        while (f <= firstList.size() - 1 && s <= secondList.size() - 1) {
            int max0 = max(firstList[f][0], secondList[s][0]);
            int min1 = min(firstList[f][1], secondList[s][1]);
            if (max0 <= min1) {
                ans.push_back({max0, min1});
            }
            if (firstList[f][1] < secondList[s][1])
                f++;
            else if (firstList[f][1] > secondList[s][1])
                s++;
            else {
                f++;
                s++;
            }
        }
        return ans;
        // 85/85 cases passed (20 ms)
        // Your runtime beats 98.57 % of cpp submissions
        // Your memory usage beats 89.29 % of cpp submissions (18.1 MB)
    }
};

11.盛最多水的容器

class Solution {
  public:
    int maxArea(vector<int> &height) {
        int maxsize = 0;
        int left = 0, right = height.size() - 1;
        while (right > left) {
            if (height[left] <= height[right]) {
                maxsize = max(maxsize, height[left] * (right - left));
                left++;
            } else {
                maxsize = max(maxsize, height[right] * (right - left));
                right--;
            }
        }
        return maxsize;
        // 60/60 cases passed (60 ms)
        // Your runtime beats 96.63 % of cpp submissions
        // Your memory usage beats 63.41 % of cpp submissions (57.6 MB)
    }
};