【算法】数据结构

devtools/2025/3/14 6:14:22/
头像
⭐️个人主页:@小羊
⭐️所属专栏: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.ppmy.cn/devtools/166947.html

相关文章

OSPF的LSA详解(报文分析+具体例子)

OSPF LSA 要点掌握: 名称 携带的内容 作用 传播的范围 由谁产生 LSA报头格式 所有的LSA都有相同的报文头 LS age&#xff1a;LSA产生后所经过的时间&#xff0c;以秒为单位。LSA在本路由器的LSDB中会随时间老化&#xff08;每秒钟加1&#xff09;&#xff0c;但在网络的…

中级软件设计师2004-2024软考真题合集下载

中级软件设计师2004-2024软考真题合集下载 &#x1f31f; 资源亮点&#x1f3af; 适用人群&#x1f4a1; 资源使用指南&#x1f4cc; 资源获取方式 &#x1f31f; 资源亮点 「中级软件设计师历年真题及答案解析&#xff08;2004-2024&#xff09;」 是全网最全、最新的备考资料…

【每日学点HarmonyOS Next知识】tab拦截、组件方法做参数、自定义组件链式调用、多次观察者监听、横竖屏切换

1、HarmonyOS Tab组件里的tabBar点击如何拦截&#xff0c;根据情况判断是否允许切换tab&#xff1f; Tab组件里的tabBar点击如何拦截&#xff0c;根据情况判断是否允许切换tab 暂时没有tabBar点击拦截功能实现&#xff0c;可以使用TabsController自定义页签以及并在其中添加事…

LangGraph 构建的工作流调用数据库的时候怎么添加重试机制

在工作流许多使用场景中&#xff0c;我们可能希望我们的节点具有自定义的重试策略&#xff0c;例如在调用API、查询数据库或调用LLM等情况下。这里我给大家介绍一种方式叫 RetryPolicy。 from langgraph.pregel import RetryPolicy RetryPolicy()RetryPolicy(initial_interval…

聊一聊测试过程中接口不通的原因排查

目录 一、 确认网络连通性 二、DNS 解析问题 三、客户端请求配置 四、 服务端状态检查 五、 查看日志 六、 接口逻辑与参数 七、 使用工具辅助排查 八、 环境与依赖问题 九、高级场景排查 十、其他方式 在我们进行接口测试时&#xff0c;大概率会遇到接口调不通的情况…

证券行业SCA开源风险治理实践

近日&#xff0c;悬镜安全成功中标国内领先的证券公司海通证券软件成分分析工具采购项目&#xff0c;中标产品为源鉴SCA开源威胁管控平台。 海通证券作为国内领先的证券公司之一&#xff0c;当下已基本建成涵盖证券期货经纪、投行、自营、资产管理、私募股权投资、另类投资、融…

Deepseek可以通过多种方式帮助CAD加速工作

自动化操作&#xff1a;通过Deepseek的AI能力&#xff0c;可以编写脚本来自动化重复性任务。例如&#xff0c;使用Python脚本调用Deepseek API&#xff0c;在CAD中实现自动化操作。 插件开发&#xff1a;结合Deepseek进行二次开发&#xff0c;可以创建自定义的CAD插件。例如&a…

Cursor 终极使用指南:从零开始走向AI编程

Cursor 终极使用指南&#xff1a;从零开始走向AI编程 问什么是cursor? mindmaproot(Cursor核心功能)智能编码代码生成自动补全错误修复项目管理多窗口布局版本控制终端集成个性设置主题定制快捷键配置插件扩展AI协作对话编程知识检索文档生成前些天发现了一个巨牛的人工智能学…