YifanChen's Blog

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数
};

treversal(cur->left, vec); // 左
vec.push_back(cur->val); // 中
treversal(cur->right, vec); // 右

treversal(cur->left, vec); // 左
treversal(cur->right, vec); // 右
vec.push_back(cur->val); // 中

vector<int> function(TreeNode* root)
{
    stack<TreeNode*> st; // 栈
    vector<int> res; // 结果数组
    
    st.push(root); // 中节点入栈
    // 栈不为空，则执行以下逻辑
    while (!st.empty())
    {
        // 将中节点从栈中弹出，加入到结果数组中
        TreeNode* node = st.top();
        st.pop();
        if (node != NULL) // 特判：中节点是否为空
            res.push_back(node->val);
        else continue; // 若中节点为空，进入下一次循环
        
        // 将中节点的左右孩子放入栈中，先将右孩子入栈，再将左孩子入栈，这样出栈时才是先左后右的顺序
        st.push(node->right); // 右
        st.push(node->left); // 左
    }
    return res;
}

vector<int> function(TreeNode* root)
{
    stack<TreeNode*> st;
    vector<int> res;
    
    st.push(root);
    while (!st.empty())
    {
        // 中
        TreeNode* node = st.top();
        st.pop();
        if (node != NULL)
        	res.push_back(node->val);
        else continue;
        
        st.push(root->left); // 左
        st.push(root->right); // 右
    }
    reverse(res.begin(), res.end());
    return res;
}

vector<int> traversal(TreeNode* root)
{
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root; // 用于遍历二叉树的指针，一开始指向根节点
    
    // cur为空且栈也为空时，遍历终止
    while (cur != NULL || !st.empty())
    {
        // 栈用于记录指针访问过的元素
        if (cur != NULL) 
        {
            st.push(cur);
            cur = cur->left; // 指针一路向左访问
        }
        // 指针一路向左，遇到某个节点的左指针为空
        // 则从栈中取出该节点并放入结果数组中
        else 
        {
            cur = st.top();
            st.pop();
            res.push_back(cur->val);
            
            // 看当前指针的右孩子是否为空
            // 若为空，则从栈中弹出顶部节点，并将其加入到结果数组中
            // 若不为空，则将右孩子入栈
            cur = cur->right;
        }
    }
    return res;
}

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;

        // 根节点非空才将其放入栈中
        if (root != NULL) st.push(root);

        // 循环条件：栈不为空
        while (!st.empty())
        {
            // 弹出栈顶元素
            TreeNode* node = st.top();
            st.pop();

            // node不为空，则按照右中左的顺序访问节点
            if (node != NULL)
            {
                if (node->right) st.push(node->right); // 右节点
                st.push(node); // 中节点
                st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记
                if (node->left) st.push(node->left); // 左节点
            }
            // 只有遇到空节点的时候，才处理节点（将下一个节点放进结果集）
            else
            {
                // 将空节点弹出，重新取出栈中的元素
                node = st.top();
                st.pop();
                res.push_back(node->val); // 加入到结果集中
            }
        }
        return res;
    }
};

class Solution {
public:
    // 前序遍历递归写法的核心函数
    void traversal(TreeNode* root, vector<int> &vec) // 递归函数的参数和返回值
    {
        if (root == NULL) return; // 确定终止条件
        
        vec.push_back(root->val); // 中
        traversal(root->left, vec); // 左
        traversal(root->right, vec); // 右
    }

    // 相当于主函数，调用核心函数
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;

        traversal(root, res); // 调用核心函数
        return res;
    }
};

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& res) {
        if (root == NULL) return;
        res.push_back(root->val);
        traversal(root->left, res);
        traversal(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root, res);
        return res;
    }
};

int main() {
    // 构建树的示例代码，需要根据实际情况调整
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node2 = new TreeNode(2, node3, nullptr);
    TreeNode* root = new TreeNode(1, nullptr, node2);

    Solution solution;
    vector<int> res = solution.preorderTraversal(root);

    // 打印结果
    for (int val : res) {
        cout << val << " ";
    }
    cout << endl;

    // 释放分配的内存（在实际使用中，考虑使用智能指针自动管理内存）
    delete node3;
    delete node2;
    delete root;

    return 0;
}

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& res)
    {
        if (root == NULL) return;

        traversal(root->left, res); // 左
        traversal(root->right, res); // 右
        res.push_back(root->val); // 中
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;

        traversal(root, res);
        return res;
    }
};

class Solution {
public:
    void traversal(TreeNode* root, vector<int>& res)
    {
        if (root == NULL) return;

        traversal(root->left, res); // 左
        res.push_back(root->val); // 中
        traversal(root->right, res); // 右
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;

        traversal(root, res);
        return res;
    }
};

// 顺序为中左右，因为栈的先入后出的特性，所以代码顺序调整为中右左
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st; // 用栈实现迭代，模拟递归
        vector<int> res; // 结果数组

        st.push(root);

        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();
            if (node != NULL)
                res.push_back(node->val);
            else continue;

            st.push(node->right); // 右
            st.push(node->left); // 左
        }
        return res;
    }
};

// 后序遍历：左右中。前序遍历：中左右 
// 中左右->中右左->左右中
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;

        st.push(root);

        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();
            if (node != NULL) res.push_back(node->val);
            else continue;

            st.push(node->left); // 左
            st.push(node->right); // 右
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

// 中序遍历的迭代写法，参见总结部分的精髓即可写出以下的代码
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        TreeNode* cur = root;

        // 终止条件：指针和栈都为空
        while (cur != NULL || !st.empty())
        {
            // 指针不为空，则将指针指向的节点放入栈中，指针向左走
            if (cur != NULL)
            {
                st.push(cur);
                cur = cur->left;
            }
            // 指针为空，则将栈顶元素弹出并放入结果数组中，指针向右走
            else
            {
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;

        // 将非空的头节点插入栈中
        if (root != NULL) st.push(root);

        // 循环终止条件：栈为空
        while (!st.empty())
        {
            // 弹出栈顶元素
            TreeNode* node = st.top();
            st.pop();

            // 若node不为空，则按照右中左的顺序访问节点
            if (node != NULL)
            {
                if (node->right) st.push(node->right); // 访问右节点
                st.push(node); // 访问中节点
                st.push(NULL); // 只访问没处理，在中结点上面添加NULL来标记
                if (node->left) st.push(node->left); // 访问左节点
            }
            // 若node为空，则处理该节点下面的节点，将其加入到res中
            else
            {
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;

        if (root != NULL) st.push(root);

        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();

            // node不为空，访问节点
            if (node != NULL)
            {
                if (node->right) st.push(node->right); // 右
                if (node->left) st.push(node->left); // 左
                st.push(node); // 中
                st.push(NULL); // 中节点后面插入NULL
            }
            // node为空，处理节点
            else
            {
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};

// 统一迭代写法
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;

        if (root != NULL) st.push(root);

        while (!st.empty())
        {
            TreeNode* node = st.top();
            st.pop();

            // 节点不为空，则访问节点，顺序为中右左
            if (node != NULL)
            {
                st.push(node);
                st.push(NULL);
                if (node->right) st.push(node->right);
                if (node->left) st.push(node->left);
            }
            // 节点为空，则处理节点
            else
            {
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};

class Solution {
public:
    // 得出队列中的最大值
    int queuemax(queue<int> q)
    {
        int max = q.front();
        while (q.size())
        {
            q.pop();
            int tmp = q.front();
            if (max < tmp) max = tmp;
        }
        return max;
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        queue<int> q;
        vector<int> res;

        for (int i = 0; i < nums.size(); i ++ )
        {
            if (q.size() < k) q.push(nums[i]);
            else if (q.size() == k)
            {
                res.push_back(queuemax(q));
                q.push(nums[i]);
                q.pop();
            }
        }
        res.push_back(queuemax(q));
        return res;
    }
};

deque<int> que; // cpp中队列默认用deque双向队列来实现，双向队列的首尾都可以出元素和入元素

void pop(int val) 
{
    // 只有当需要pop的元素和队首元素（单调队列中目前的最大值）相同时，才弹出队首元素
    // 例如上图的倒数第二行到最后一行的操作（532->321）
    // 若需要pop的元素小于队首元素，那么在push时该元素已经被删除了
    // 例如上图中的-1-35->-353，本来需要手动删除-1，但由于-1<5，因此在push(5)时-1已经被删除了
    if (!que.empty() && val == que.front())
        que.pop_front();
}

void push(int val)
{
    // 当队列不为空且要插入的值val > 队列中的最后一个元素时，持续从队尾弹出元素
    // 例如上图中的3-1-3->-1-35，要插入5，持续从队尾弹出比5小的元素，然后再插入5
    while (!que.empty() && val > que.back()) que.pop_back();
    que.push_back(val);
}

int getMaxValue(deque<int> que)
{
    return que.front();
}

class Solution {
private:
    class MyQueue
    {
    public:
        deque<int> que;
            // 单调队列中只维护当前队列中的最大值，作为队首元素
            // 故窗口滑动时只需要在滑出最大值时手动删除最大值即可
            // 其他值都会在push时被删除
        void pop(int val)
        {
            if (!que.empty() && val == que.front()) que.pop_front();
        }

            // 保证单调队列从队首到队尾是单调递减的
            // 新插入的元素若大于当前队列中的最大值，则删除当前队列，将插入的元素放在队列的首部
        void push(int val)
        {
            while (!que.empty() && val > que.back()) que.pop_back();
            que.push_back(val);
        }

            // 当前队列中的最大值为队首元素，故返回队首元素即可
        int getMaxValue()
        {
            return que.front();
        }
    };
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> res;

        for (int i = 0; i < k; i ++ )
            que.push(nums[i]);

        res.push_back(que.getMaxValue());

        for (int i = k; i < nums.size(); i ++ )
        {
            que.pop(nums[i - k]);
            que.push(nums[i]);
            res.push_back(que.getMaxValue());
        }
        return res;
    }
};

class Solution {
public:
    class compare
    {
    public: 
        // 为定义小顶堆重载运算符，这里的函数名为operator()，而非operator
        // 对大顶堆，本来应该是右边的元素>左边的元素，对小顶堆，则与此相反
        bool operator() (pair<int, int> lhs, pair<int, int> rhs)
        {
            return lhs.second > rhs.second; // 比较的是元素出现的次数，而非元素的值
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;

        // nums[i]作为key, 出现此处作为value存入map中
        for (int i = 0; i < nums.size(); i ++ )
            map[nums[i]] ++ ;
        
        // 定义小顶堆，其中的元素类型是pair<int, int>，底层实现是vector<pair<int, int>>
        priority_queue<pair<int,int>, vector<pair<int, int>>, compare> q;

        // 遍历map，不断将map中的元素插入小顶堆中，小顶堆不断弹出根节点处最小的元素
        // 最后剩下的k个元素是出现频次最高的k个元素
        for (auto it = map.begin(); it != map.end(); it ++ )
        {
            q.push(*it);
            if (q.size() > k) q.pop();
        }

        vector<int> res(k);

        // 根节点处是最小的元素，越往下元素越大，因此将小顶堆中的k个元素倒着插入res中
        for (int i = k - 1; i >= 0; i -- )
        {
            res[i] = q.top().first; // 插入res的是key, 即nums[i]
            q.pop();
        }
        return res;
    }
};

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (st.empty()) st.push(s[i]);
            else if (s[i] == st.top()) st.pop();
            else st.push(s[i]);
        }
        string out;
        while (st.size())
        {
            out += st.top();
            st.pop();
        }
        reverse(out.begin(), out.end());
        return out;
    }
};

class Solution {
public:
    bool isValid(string s) {
        stack<int> st; // stack<int>和stack<char>都可以

        // 剪枝：字符串长度为奇数，一定不匹配
        if (s.size() % 2) return false;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '[') st.push(']');
            else if (s[i] == '{') st.push('}');
            // 不匹配的两种情况：多出右括号和括号类型不匹配
            // 两个判据不可颠倒，否则可能会出现栈为空但依然试图取栈顶元素的情况，编译器会报错
            else if (st.empty() || s[i] != st.top()) return false;
            // 栈不为空且栈的顶元素和s[i]相同，则弹出st的顶元素，两两抵消
            else st.pop();
        }
        // 不匹配的情况：多出左括号
        return st.empty();
    }
};

class Solution {
public:
    string removeDuplicates(string s) {
        string out;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (out.empty()) out.push_back(s[i]);
            else if (s[i] == out.back()) out.pop_back();
            else out.push_back(s[i]);
        }
        return out;
    }
};

class Solution {
public:
    string removeDuplicates(string s) {
        string res;

        for (int i = 0; i < s.size(); i ++ )
        {
            // 字符串为空或者字符串尾部的元素与s[i]不同时，直接在字符串的尾部插入s[i]
            if (res.empty() || res.back() != s[i]) res.push_back(s[i]);
            // 否则，意味着字符串尾部的元素和s[i]相同，则两两抵消，弹出字符串尾部的元素
            else res.pop_back();
        }
        return res;
    }
};

class Solution {
public:
    int evalRPN(vector<string>& s) {
        stack<long long> st;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/")
            {
                // 注意采用long long类型
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                // 注意是先num2再num1
                if (s[i] == "+") st.push(num2 + num1);
                else if (s[i] == "-") st.push(num2 - num1);
                else if (s[i] == "*") st.push(num2 * num1);
                else st.push(num2 / num1);
            }
            else
                st.push(stoll(s[i])); // stoi可以将字符串转换为int, stoll可以将字符串转换为long long
        }
        int res = st.top();
        st.pop(); // 释放内存
        return res;
    }
};

// 第一个参数int：指定了栈中元素的类型
// 第二个参数std::vector<int>：指定了底层容器的类型及其元素类型。即使用一个整型向量来存储栈中的元素。
std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

class MyQueue {
public:

    stack<int> inStack; // 入栈
    stack<int> outStack; // 出栈

    MyQueue() {
    }
    
    void push(int x) {
        // 向入栈中插入元素即可
        inStack.push(x);
    }
    
    int pop() {
        // 若出栈为空，则将入栈中的所有元素全部加入到出栈中
        // 如果没有把入栈中的所有元素加入到出栈中，则弹出元素的顺序会发生错误
        // 若出栈不为空，则跳过if判断部分，直接执行本函数最后三行代码
        if (outStack.empty())
        {
            while (inStack.size())
            {
                int tmp = inStack.top();
                inStack.pop();
                outStack.push(tmp);
            }
        }

        // 返回出栈顶部的元素并将该元素弹出
        int res = outStack.top();
        outStack.pop();
        return res;
    }
    
    int peek() {
        // 复用上面实现的pop函数
        int res = this->pop();
        // 由于pop函数弹出了出栈顶部的元素，peek函数只需要查询出栈顶部的元素，不需要弹出
        // 因此将该元素插入回出栈中
        outStack.push(res);
        return res;
    }
    
    bool empty() {
        // 入栈和出栈同时为空时，队列才为空
        // 若只有入栈为空，则出栈中依然有元素没有弹出，说明队列还可以弹出元素，不为空
        // 若只有出栈为空，则入栈中依然有元素可以加入出栈中，之后出栈还可以继续弹出元素，故队列也不为空
        if (inStack.empty() && outStack.empty()) return true;
        else return false;
    }
};

class MyStack {
public:
queue<int> q;

    MyStack() {     
    }
    
    void push(int x) {
       q.push(x); 
    }
    
    int pop() {
        int count = q.size(); // 队列中有size个元素
        // 循环(size - 1)次
        // 先弹出队首的元素，再将其加入到队尾中
        while (count > 1) 
        {
            int tmp = q.front();
            q.pop();
            q.push(tmp); 
            count -- ;        
        }
        // 弹出队首的元素，即为最后插入的元素
        int res = q.front();
        q.pop();
        return res;
    }
    
    // 复用pop函数，但是由于本函数只需要实现查询元素的功能，要记得将弹出的元素插入回去
    // 也可直接return q.back()。因为栈顶的元素就是队列尾部的元素（队列中，从front弹出元素，从back插入元素）
    int top() {
        int res = this->pop();
        q.push(res);
        return res;
    }
    
    // 队列为空，则栈也为空
    bool empty() {
        return q.empty();
    }
};

class MyStack {
public:
queue<int> q;

    MyStack() {
        
    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size();
        size -- ;
        while (size -- )
        {
            q.push(q.front());
            q.pop();
        }
        int res = q.front();
        q.pop();
        return res;
    }
    
    int top() {
        return q.back();
    }
    
    bool empty() {
        return q.empty();
    }
};

class MyStack {
public:
queue<int> q1;
queue<int> q2;

    MyStack() {
        
    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        // 将除去队尾的元素的其他元素全部加入到q2中
        int size = q1.size();
        size -- ;
        while (size -- )
        {
            q2.push(q1.front());
            q1.pop();
        }
        // 收获答案
        int res = q1.front();
        // 将q2赋给q1
        q1 = q2;
        // 清空q2
        while (q2.size()) q2.pop();
        return res;
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.empty() && q2.empty();
    }
};

// 传入的参数：next数组，我们需要对其进行赋值，模式串s
void getNext(vector<int> next, string s)
{
    // 初始化
    // 指针i：指向后缀末尾位置
    // 指针j：指向前缀末尾位置，还代表着i之前（包括i）的子串的最长相等前后缀的长度
    int j = 0; // 前缀从0开始
    int next[N]; 
    next[0] = 0; // next数组初始位置为0
    
    // 比较前后缀所对应的字符是否相等，故i从1开始，这样i和j才能进行比较
    for (int i = 1; i < s.size(); i ++ )
    {
        // 处理前后缀末尾不相同的情况
        // 因为在一次循环中，i相当于是固定不动的，所以此时j回退
        // j回退到next[j - 1]指向的位置，即遇见冲突，就看next数组（即前缀表）的前一位
        // 不止回退一步，而要连续回退，不能写if，而要写while
        while ( j > 0 && s[i] != s[j]) j = next[j - 1]; // 因为要求j - 1 >= 0，因此要求j > 0
        
        // 处理前后缀相同的情况
        // j代表着i之前（包括i）的子串的最长相等前后缀的长度
        if (s[i] == s[j]) j ++ ;
        
        // 更新next数组，在其中存储i之前（包括i）的子串的最长相等前后缀的长度
        next[i] = j;
    }
}

// 传入的参数：next数组，我们需要对其进行赋值，模式串s
void getNext(vector<int> next, string s)
{
    int j = 0; // 前缀从0开始
    int next[N]; 
    next[0] = 0; // next数组初始位置为0
    
    // 比较前后缀所对应的字符是否相等，故i从1开始，这样i和j才能进行比较
    for (int i = 1; i < s.size(); i ++ )
    {
        while ( j > 0 && s[i] != s[j]) j = next[j - 1]; // 因为要求j - 1 >= 0，因此要求j > 0
        
        if (s[i] == s[j]) j ++ ;
        
        // 更新next数组，在其中存储i之前（包括i）的子串的最长相等前后缀的长度
        next[i] = j;
    }
}

int j = 0; // 因为next数组里记录的起始位置为0
for (int i = 0; i < s.size(); i++) { // i从0开始，遍历文本串
    while(j > 0 && s[i] != t[j]) { // 不匹配, j - 1 >= 0 => j > 0
        j = next[j - 1]; // j 寻找之前匹配的位置
    }
    if (s[i] == t[j]) { // 匹配，j和i同时向后移动
        j++; // i的增加在for循环里
    }
    // j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了
    if (j == t.size()) { // 文本串s里出现了模式串t
        // 返回当前在文本串匹配模式串的位置i-模式串的长度 + 1，就是文本串字符串中出现模式串的第一个位置（位置从0开始）
        return (i - t.size() + 1);
    }
}

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        // 特殊情况，模式串长度为0，则返回0，本处是一个易错点
        if (needle.size() == 0) {
            return 0;
        }
        // 定义next数组
        int next[needle.size()];
        // 填充next数组
        getNext(next, needle);
        // 用next数组做匹配
        // j指向模式串，i指向文本串
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        // 模式串匹配不上文本串，则返回-1
        return -1;
    }
};

for 子串结束位置
	for 子串与主串比较

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string ss = s + s;
        ss.erase(ss.begin());
        ss.erase(ss.end() - 1);
        
        // string::npos 是 std::string 类型的一个静态成员常量，表示字符串中不存在匹配的位置。在 find() 函数中，如果没有找到匹配的子串，则返回 string::npos。这个值通常是一个很大的无符号整数，表示找不到匹配的位置。
        if (ss.find(s) != string::npos)
            return true;
        else 
            return false;
    }
};

class Solution {
public:
    // 求next数组
    void getNext (int* next, const string& s){
        // 初始化
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            // 处理前后缀不相同的情况
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            // 处理前后缀相同的情况
            if(s[i] == s[j]) {
                j++;
            }
            // 更新next数组
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        // 核心代码
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int l = 0, r = s.size() - 1; l < r; l ++ , r -- )
        {
            // swap(s[l], s[r]);
            int tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
        }
    }
};

# include <iostream>
# include <vector>

using namespace std;

int main()
{
    string s;
    cin >> s;

    vector<char> out;

    for (int i = 0; i < s.size(); i ++ )
    {
        if (s[i] >= 48 && s[i] <= 57)
        {
            out.push_back('n');
            out.push_back('u');
            out.push_back('m');
            out.push_back('b');
            out.push_back('e');
            out.push_back('r');
        }
        else
            out.push_back(s[i]);
    }

    for (int i = 0; i < out.size(); i ++ )
        cout << out[i];
    cout << endl;
    return 0;
}

#include <iostream>
#include <string>
#include <sstream> // 引入 stringstream

using namespace std;

int main()
{
    string line;
    getline(cin, line); // 使用 getline 读取一整行

    stringstream ss(line); // 使用 stringstream 来分割字符串
    string word;
    while (ss >> word) { // 从 stringstream 中读取单词，直到结束
        cout << word << endl; // 输出单个单词
    }

    return 0;
}

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    string s1 = s.substr(s.size() - k, s.size()); // 后面k个字符
    string s2 = s.substr(0, s.size() - k); // 字符串在后面k个字符前的字符
    cout << s1 + s2 << endl;
}

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    reverse(s.begin(), s.end());
    reverse(s.begin(), s.begin() + k);
    reverse(s.begin() + k, s.end());
    cout << s << endl;
}

#include <iostream>
#include <string>

using namespace std;

// 手动实现reverse函数
void reverseString(string &s, int i, int j)
{
    for (int a = i, b = j; a < b; a ++ , b -- )
    {
        int tmp = s[a];
        s[a] = s[b];
        s[b] = tmp;
    }
}

int main()
{
    int k;
    string s;
    cin >> k >> s;
    
    reverseString(s, 0, s.size() - 1);
    reverseString(s, 0, k - 1);
    reverseString(s, k, s.size() - 1);
    cout << s << endl;
}

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size() / 2; i ++ , j -- )
            swap(s[i], s[j]);
    }
};

class Solution {
public:
    string reverseStr(string s, int k) {
        // 每隔2k个字符跳转一次，即每次取出2k个字符
        for (int i = 0; i < s.size(); i += 2 * k)
        {
            // 对2k个字符的前k个字符进行反转
            // 由于每次取2k，取若干次后。字符串的尾部剩下的字符长度l可能l < k 或 k <= l < 2k
            // 对前一种情况，需要将尾部全部反转，对后一种情况，需要反转尾部剩下字符的前k个字符
            // 先处理后一种情况，注意加上条件i + k <= s.size()，这可以避免对索引超出范围的元素进行反转
            // 至于i + k是否能取到s.size()，可以举例子：k = 3, s = {a, b, c}，由此可见可以取等于
            // 也可以从理论上分析，由于reverse的区间是左闭右开的，因此s.begin() + i + k实际上取不到，因此可以让i + k = s.size() 
            // 处理完后continue即可，除去反转2k个字符中的前k个字符的一般情况，尾部剩下的字符的长度的第一种情况和第二种情况只可能有一种发生
            if (i + k <= s.size())
            {
                reverse(s.begin() + i, s.begin() + i + k); // 左闭右开
                continue;
            }
            // 再处理前一种情况，当剩余的字符长度l < k时，反转剩余的全部字符
            reverse(s.begin() + i, s.end());
        }
        return s;
    }
};

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k );
            } else {
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};