当前位置：首页 > article >正文

【算法】数组、链表、栈、队列、树

article 2025/3/14 21:10:34

⭐️个人主页：@小羊 ⭐️所属专栏：Linux 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

持续更新中…

数组、链表

点击消除

AB5 点击消除

在这里插入图片描述
这个题很容易想到用“栈”，但是创建一个stack最后还要转换成字符串，可以用string代替栈。
string的接口很多且实用，常见的接口基本都有：

在这里插入图片描述

这个题比较坑的是它说如果字符串为空串则返回0，谁想到返回的是"0"，我试着返回0咋都过不去，最后吐了！都怪我太年轻了！

#include <iostream>
using namespace std;

int main() 
{
    string str, st;
    cin >> str;
    for (char ch : str)
    {
        if (!st.empty() && st.back() == ch)
        {
            st.pop_back();
            continue;
        }
        st.push_back(ch);
    }
    cout << (st.empty() ? "0" : st);
    return 0;
}

环形链表

Leetcode——环形链表

在这里插入图片描述

快慢指针法： 快指针和慢指针初始时指向头节点，当快指针指向和快指针指向节点内的next指针不为空时，快指针一次走两步，慢指针一次走一步，快指针入环后走N圈后慢指针入环，当快指针和慢指针相等时说明存在环，如果出循环则说明不存在环。

关键的地方是快指针一次走两步，慢指针一次走一步，如果存在环则快指针和慢指针一定会相遇。为什么一定会相遇呢？
如果存在环，假设当慢指针入环时快指针距离此时慢指针的位置为N，则接下来每当快指针追赶慢指针一次，它们的距离就减一，直到减为0，此时快慢指针就相遇了。

在这里插入图片描述

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head, *slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}

环形链表 II

Leetcode——环形链表 II

在这里插入图片描述

还是快慢指针，当快慢指针相遇时我们让meet指针指向相遇时的节点，然后让头指针head和meet指针一步步地向后走，当两指针相遇时指向的节点就是链表开始入环的第一个节点。为什么这两个指针一定会相遇在链表开始入环的第一个节点？

假设头指针距离链表开始入环的第一个节点的长度为L，meet指针相距链表开始入环的第一个节点的距离是N，环的长度为C，当慢指针入环时快指针走了x圈，因为快指针的速度是慢指针的2倍，那我们可以得到下面的等式：

2(L + N) = L + X*C + N

化简得：L = X*C - N，由这个等式可以得出head和meet相遇是必然的。
在这里插入图片描述

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast = head, *slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            struct ListNode* meet = fast;
            while (head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}