884.比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

方法一、用栈

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool backspaceCompare(string s, string t) {
    stack<char> stack_s, stack_t;

    // Process string s
    for (char c : s) {
        if (c != '#') {
            stack_s.push(c);
        } else if (!stack_s.empty()) {
            stack_s.pop();
        }
    }

    // Process string t
    for (char c : t) {
        if (c != '#') {
            stack_t.push(c);
        } else if (!stack_t.empty()) {
            stack_t.pop();
        }
    }

    // Compare the resulting strings
    string result_s, result_t;
    while (!stack_s.empty()) {
        result_s += stack_s.top();
        stack_s.pop();
    }
    while (!stack_t.empty()) {
        result_t += stack_t.top();
        stack_t.pop();
    }

    return result_s == result_t;
}

int main() {
    string s = "ab#c";
    string t = "ad#c";
    if (backspaceCompare(s, t)) {
        cout << "The strings are equal." << endl;
    } else {
        cout << "The strings are not equal." << endl;
    }
    return 0;
}

方法二、双指针

#include <iostream>
#include <string>

using namespace std;

bool backspaceCompare(string s, string t) {
    int i = s.size() - 1, j = t.size() - 1;
    int skipS = 0, skipT = 0;

    while (i >= 0 || j >= 0) {
        // Find position to compare in string s
        while (i >= 0) {
            if (s[i] == '#') {
                skipS++;
                i--;
            } else if (skipS > 0) {
                skipS--;
                i--;
            } else {
                break;
            }
        }

        // Find position to compare in string t
        while (j >= 0) {
            if (t[j] == '#') {
                skipT++;
                j--;
            } else if (skipT > 0) {
                skipT--;
                j--;
            } else {
                break;
            }
        }

        // Compare characters
        if (i >= 0 && j >= 0 && s[i] != t[j]) {
            return false;
        }
        
        // Check if one string has reached its end while the other hasn't
        if ((i >= 0) != (j >= 0)) {
            return false;
        }

        i--;
        j--;
    }

    return true;
}

int main() {
    string s = "ab#c";
    string t = "ad#c";
    if (backspaceCompare(s, t)) {
        cout << "The strings are equal." << endl;
    } else {
        cout << "The strings are not equal." << endl;
    }
    return 0;
}

977.有序数组平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

#include <iostream>
#include <vector>

using namespace std;

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n);
    int left = 0, right = n - 1;
    int index = n - 1; // Index to insert the largest square
    
    while (left <= right) {
        int square_left = nums[left] * nums[left];
        int square_right = nums[right] * nums[right];
        
        if (square_left > square_right) {
            result[index--] = square_left;
            left++;
        } else {
            result[index--] = square_right;
            right--;
        }
    }
    
    return result;
}

int main() {
    vector<int> nums = {-4, -1, 0, 3, 10};
    vector<int> result = sortedSquares(nums);
    
    cout << "Sorted squares: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}