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

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

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

动图描述

目录

  • 持续更新中...
    • 数组、链表
      • 点击消除
      • 环形链表
      • 环形链表 II
    • 栈、队列


持续更新中…


数组、链表

点击消除

  • 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指针指向相遇时的节点,然后让头指针headmeet指针一步步地向后走,当两指针相遇时指向的节点就是链表开始入环的第一个节点。为什么这两个指针一定会相遇在链表开始入环的第一个节点?

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

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

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

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

栈、队列


本篇文章的分享就到这里了,如果您觉得在本文有所收获,还请留下您的三连支持哦~

头像

http://www.kler.cn/a/584628.html

相关文章:

  • 饮食调治痉挛性斜颈,开启健康生活
  • 《C#上位机开发从门外到门内》2-4:Modbus协议
  • WEB-CTFyj解题视频笔记(持续更新)
  • 机器学习之距离度量方法
  • 欧姆龙PLC学习的基本步骤
  • 高并发场景下如何实现消息精准一次消费?实战Java幂等性设计
  • PyTorch中前身传播forward方法调用逻辑
  • AI赋能铁道安全巡检探索智能巡检新时代,基于YOLOv7全系列【tiny/l/x】参数模型开发构建铁路轨道场景下轨道上人员行为异常检测预警系统
  • 使用 JavaScript 和 HTML5 实现强大的表单验证
  • ClickHouse剖析:架构、性能优化与实战案例
  • LeetCode 力扣热题100 最长递增子序列
  • Anaconda conda常用命令:从入门到精通
  • Linux 常用 20 条指令,解决大部分问题
  • 关于vue ui 命令无法无法打开vue项目管理器的记录
  • PHP与数据库连接常见问题及解决办法
  • 四、子串——10. 和为 K 的子数组
  • 动态IP/静态IP
  • 基于单片机的智能电表设计(论文+源码)
  • 【Pandas】pandas Series last_valid_index
  • SQL Server的连接时发生了与网络相关或特定于实例的错误。未找到服务器或无法访问服务器