【算法】数据结构

_小羊_

发布于 2025-03-14 09:49:56

5200

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

持续更新中…

数组、链表

点击消除

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;
}