计算机学习周志十（9.7-9.14）

1.算法刷题P1551 亲戚并查集先初始化每个点是自己的父节点 然后用find函数 路径压缩求最终父节点 并对向上找过程中的节点也赋值最终父节点这样后续调用方便且不会超时 最后合并两个节点所在的树 只需要知道亲戚关系 所以根与根合并就行 合并如果想把小树合并到大树里 可以开辟一个vector数组存储每棵树的节点数 把节点少的根指向节点多的根P1536 村村通先附上自己的暴力解 先用并查集 然后双重for循环找任意两个村是否有公共祖先 没有的话就融合 路数加一 题目数据小于10000所以能过正解 求连通块个数 需要的路的条数就是连通块个数-1 比如 1-2 3-4 5这是三个连通块 需要两条路并查集解法只需要改if判断即可 O(n)DFS解法和BFS解法本质一样找到没有遍历过的点标记为连通块 再遍历这个点的邻接表把整块全部标记访问P3405 Cites and States哈希加pair注意题目来自不同的州 所以如果是 2 AAB AA AAC AA是不能配对的所以如果州名和城市前缀相同的话直接跳过 一定配对不了P4305 不重复数字哈希set什么都被卡了 没招 能拿到60分的样例点P3879 阅读理解map里嵌套一个vector存储每个字符串对应的所有短文序号需要用set去重 如果有个字符在一篇文章重复出现不能输出多次P2814 家谱字符串并查集 用哈希表存储每个字符串的祖先 找祖先用路径压缩最后输出的时候一定要输出find_root 不能输出fa[sonname] 因为有可能有某个节点他开头是# 但是他之前没有被访问到 所以用fa输出不出来P5318 查找文献用二维vector存储边之后进行排序 然后用DFS和BFSB3644 拓扑排序拓扑排序1.BFS做本质是如果有环遍历到后面就不会有入度为0的点DFS做法设三种状态三种状态 0未访问 1正在访问 2访问完毕 如果访问的时候遇到了状态为1的说明有环注意压入的位置 必须回溯压入 不能让后代在前面P3916 图的遍历建反向图从大到小往回遍历看能走到哪个点 如果正向不方便赋值往回遍历时 如果这个点没有被遍历过并且比起点小那么就被赋值并且继续往下遍历单源最短路径算法P3371 单源最短路径迪杰斯特拉算法每次找到点被标记都说明此时距离一定最短 因为找到最短的时候不可能通过其他更短的线路到达朴素迪杰斯特拉算法(点比较少不带负权值)算法核心主函数1312^31迪杰斯特拉算法的堆优化降低时间复杂度核心代码 用vis主要是减少遍历次数 前面的最短距离起点后面遍历可能还会存进去再继续遍历相当于重复了 没有意义处理负边权值的情况以上两种算法都没处理 所以要用下面两种算法来完成完整的单源最短路径算法P3385 负环贝尔曼福特算法处理负权边 每次都遍历所有点看能不能继续遍历下去更新距离最多需要n-1轮(链式情况)每次更新一个点 所以判断有无负环的核心是判断第n轮有无更新如果有说明有负环可以一直更新负环是指这个环上所有的权值加起来小于0 就可以一直更新核心代码主函数代码但此时我们发现贝尔曼福特算法有个弊端 双重for循环 复杂度为O(n^2) 对于点数较多的情况会超时所以我们需要找到一个优化算法 类似朴素迪杰斯特拉和堆优化迪杰斯特拉SPFA算法判断有无负环的核心是看边的长度是否大于n-1 因为如果有负环的话可以一直更新边的长度会不断加长优化核心:只有被更新过的点它才可能去更新别的点单源路径最短算法的四种2.FastAPI学习ORM条件查询不存在返回null查询价格大于190的图书模糊查询like 如果查询曹后面只有一个字就用曹_与或非判断也可以in的查询 查找在不在某个列表中聚合查询分页查询查询总结新增数据定义ORM对象-添加对象到事务: add(对象)- commit提交到数据库更新数据删除数据AI掘金头条新闻项目一个基于FastAPI和SQLAlchemy构建的现代化新闻系统、支持用户注册登录、新闻浏览、收藏和历史记录等功能模块化路由模块化路由就是把每个业务功能的接口拆分到独立文件里再统一挂载到主应用中项目结构更清晰、项目更易维护数据库和ORM配置把项目物料里的sql导入 里面有表和数据配置ORM获取新闻分类模块化路由定义模型类封装数据库查询方法(crud里)路由函数调用crud方法解决跨域问题跨域资源共享CORS跨域资源共享(CORS)是一种浏览器安全机制用于允许运行在一个源origin的Web应用,通过浏览器向另一个源的服务器发起跨域HTTP请求并在服务器授权的前提下获取资源同源的三个条件:协议、域名、端口CORS中间件CORS:让后端主动告诉浏览器这个前端允许访问成功访问后 前端代码运行可以看到头条项目分类八个类别全部出来了获取新闻列表查询功能3.AI应用会话管理每一个历史会话文件中 需要保存交互消息、昵称、性格、会话标识(名字唯一)文件操作读和写 写文件会新建一个文件到resource目录里资源释放防止异常时无法关闭文件json文件处理保存会话新建会话展示会话列表加载所有的会话列表信息加载会话加载指定会话最后的会话也要能新建增添了当前聊天框的时间有内容才存不存空壳垃圾文件 空会话点新建不存文件但按钮不失灵删除会话点击侧面栏的❌️按钮可以删除文件 并且如果点击的是当前会话的文件也可以删除清空界面功能优化使左边的会话历史按照时间顺序排下去 最上面的是最新的希望在会话管理和伴侣信息中间增加分割线至此AI智能伴侣项目正式完成稍后会把代码和博客发出来名字是AI智能伴侣开发博客