【算法刷题】Day30
文章目录
- 1. 汉诺塔问题
- 题干:
- 算法原理:
- 代码:
- 2. 合并两个有序链表
- 题干:
- 算法原理:
- 代码:
- 3. 反转链表
- 题干:
- 算法原理:
- 代码:
- 4. 最大子数组和
- 题干:
- 算法原理:
- 1. 状态表示:
- 2. 状态转移方程
- 3. 初始化
- 4. 填表顺序
- 5. 返回值
- 代码:
- 5. 环形子数组的最大和
- 题干:
- 算法原理:
- 1. 状态表示:
- 2. 状态转移方程
- 3. 初始化
- 4. 填表顺序
- 5. 返回值
- 代码:
1. 汉诺塔问题

原题链接
题干:


算法原理:
利用递归算法
将x柱子上的一堆盘子,借助 y柱子,转移到z 柱子上面
递归函数流程:
- 当前问题规模为 n=1 时,直接将 A 中的最上面盘子挪到 C 中并返回
- 递归将 A 中最上面的 n-1 个盘子挪到 B 中
- 将 A 中最上面的⼀个盘子挪到 C 中
- 将 B 中上面 n-1 个盘子挪到 C 中
代码:
class Solution {public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {dfs(a, b, c, a.size());}public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {if(n == 1) {c.add(a.remove(a.size() - 1));return;}dfs(a, c, b, n - 1);c.add(a.remove(a.size() - 1));dfs(b, a, c, n - 1);}
}
2. 合并两个有序链表

原题链接
题干:
升序 链表
新链表是通过拼接给定的两个链表的所有节点组成的

算法原理:
-
重复子问题(函数头的设计)
合并两个有序链表 -
只关心一个子问题咋做什么(函数体的设计)
选择两个头结点中较小的结点作为最终合并后的头结点,然后将剩下的链表交给递归函数去处理 -
递归的出口
谁为空返回另一个
代码:
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) {return l2;}if(l2 == null) {return l1;}if(l1.val <= l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;}else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}
3. 反转链表

原题链接
题干:
单链表的头节点 head ,反转链表,并返回反转后的链表

算法原理:
利用递归
- 从宏观角度
1)让当前节点后面的链表先逆序,并且把头结点返回
2)让当前节点添加到逆置后的链表的后面 - 将链表看成一棵树
仅需做一次 dfs 即可
后序遍历

代码:
class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) {return head;}ListNode newheader = reverseList(head.next);head.next.next = head;head.next = null;return newheader;}
}
4. 最大子数组和

原题链接
题干:
一个整数数组 nums
找出一个具有最大和的连续子数组
算法原理:
1. 状态表示:
dp[i] 表示:以 i 位置为结尾的所有子数组中的最大和

2. 状态转移方程

dp[i] = max(nums[i], dp[i - 1] + nums[i])
3. 初始化
- 辅助结点里面的值要「保证后续填表是正确的」
- 「下标的映射关系」

4. 填表顺序
从左往右
5. 返回值
整个dp表的最大值
代码:
class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];int ret = Integer.MIN_VALUE;for(int i = 1; i <= n; i++) {dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);ret = Math.max(ret, dp[i]);} return ret;}
}
5. 环形子数组的最大和

原题链接
题干:
长度为 n 的环形整数数组 nums
返回 nums 的非空 子数组 的最大可能和
算法原理:

1. 状态表示:

2. 状态转移方程

f[i] = max(nums[i], f[i - 1] + nums[i])

g[i] = min(nums[i], g[i - 1] + nums[i])
3. 初始化
- 辅助结点里面的值要「保证后续填表是正确的」
- 「下标的映射关系」

4. 填表顺序
从左往右
5. 返回值
- 先找到 f 表里面的最大值 -> fmax
- 找到 g 表里面的最小值 -> gmin
- 统计所有元素的和 -> sum
- 返回 sum == gmin ? fmax : max(fmax, sum - gmin)
代码:
class Solution {public int maxSubarraySumCircular(int[] nums) {int n = nums.length;int[] f = new int[n + 1];int[] g = new int[n + 1];int sum = 0;int fmax = Integer.MIN_VALUE;int gmin = Integer.MAX_VALUE;for(int i = 1; i <= n; i++) {int x = nums[i - 1];f[i] = Math.max(x, x + f[i - 1]);fmax = Math.max(fmax, f[i]);g[i] = Math.min(x, x + g[i - 1]);gmin = Math.min(gmin, g[i]);sum += x;}return sum == gmin ? fmax : Math.max(fmax, sum - gmin);}
}
相关文章:
【算法刷题】Day30
文章目录 1. 汉诺塔问题题干:算法原理:代码: 2. 合并两个有序链表题干:算法原理:代码: 3. 反转链表题干:算法原理:代码: 4. 最大子数组和题干:算法原理&#…...
docker容器镜像管理+compose容器编排(持续更新中)
目录 一、 Docker的基本组成 二、 容器和镜像的关系 2.1 面向对象角度 2.2 从镜像容器角度 三、 容器命令 3.1 使用Ubuntu 3.1.1 下载镜像 3.1.2 新建和启动容器 run 3.1.3交互式 compose编排与部署 1. docker-compose部署 2. docker-compose.yml模板 …...
【Greenhills】MULTIIDE集成第三方的编辑器进行源文件编辑工作
【更多软件使用问题请点击亿道电子官方网站查询】 1、 文档目标 在使用GHS进行工作的时候,可以集成第三方的编辑器进行源文件编辑工作 2、 问题场景 用于解决在GHS中进行项目开发时,对于GHS的编辑器使用不习惯,想要切换到其他第三方的编辑…...
【Flutter】 search_page使用心得
https://pub.dev/packages/search_page 以上就是search_page地址。使用方法跟具有哪些功能网页都有,这篇文章主要讲我在使用这个插件时遇到的坑。 坑1:不能自己刷新界面 我在search_page中传入的builder是带有checkbox的ListTile,当我点击…...
前端Vue列表组件 list组件:实现高效数据展示与交互
前端Vue列表组件 list组件:实现高效数据展示与交互 摘要:在前端开发中,列表组件是展示数据的重要手段。本文将介绍如何使用Vue.js构建一个高效、可复用的列表组件,并探讨其在实际项目中的应用。 效果图如下: 一、引言…...
每日OJ题_哈希表⑤_力扣49. 字母异位词分组
目录 力扣49. 字母异位词分组 解析代码 力扣49. 字母异位词分组 49. 字母异位词分组 难度 中等 给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入…...
【Linux】-Linux下的软件商店yum工具介绍(linux和windows互传文件仅仅一个拖拽搞定!!!!)
目录 1.Linux 软件包管理器yum 1.1快速认识yum 1.2 yumz下载方式(如何使用yum进行下载,注意下载一定要是root用户或者白名单用户(可提权)) 1.2.1下载小工具rzsz 1.2.2 rzsz使用 1.2.2查看软件包 1.3软件的卸载 2.yum生…...
320: 鸡兔同笼(python)
题目描述 一个笼子里关了鸡和兔(鸡有2只脚,兔又4只脚,没有例外)。已知笼子里面脚的总数a,问笼子里面至少有多少只动物,至多有多少只动物? 输入 多组测试数据。第一行是测试数据的组数n&#…...
CentOS 8启动流程
一、BIOS与UEFI BIOS Basic Input Output System的缩写,翻译过来就是“基本输入输出系统”,是一种业界标准的固件接口,第一次出现在1975年,是计算机启动时加载的第一个程序,主要功能是检测和设置计算机硬件,引导系统启动。 UEFI Unified Extensible Firmware interfac…...
js【详解】原型 vs 原型链
原型 每个 class 都有显示原型 prototype每个实例都有隐式原型_proto_实例的_proto_指向对应 class 的 prototype 如下范例: class Student 创建了 实例 xialuo 获取属性 xialuo.name 或执行方法 xialuo.sayhi()时,先在自身属性和方法寻找࿰…...
贪心算法: 奶牛做题
5289. 奶牛做题 - AcWing题库 贝茜正在参加一场奶牛智力竞赛。 赛事方给每位选手发放 n 张试卷。 每张试卷包含 k 道题目,编号 1∼k。 已知,不同卷子上的相同编号题目的难度相同,解题时间也相同。 其中,解决第 i 道题(…...
go语言tcp协议实现文件上传
一、客户端实现方案: package mainimport ("fmt""io""net""os" )func sendFile(filePath string, conn net.Conn) {defer conn.Close()// 获取文件名fileInfo, err : os.Stat(filePath)if err ! nil {fmt.Println("E…...
【Unity】利用二进制数据持久化 【练习学习项目/有不足之处欢迎斧正/侵删】
1.为编辑器菜单栏添加新的选项入口 通过Unity提供的MenuItem特性在菜单栏添加选项按钮 特性名:MenuItem 命名空间:UnityEditor 要求:一定是静态方法;新建的这个菜单栏按钮 必须有至少一个斜杠 不然会报错 它不支持只有一个菜单…...
做伦敦银要等怎样的价格与行情?
对于不同的伦敦银投资者来说,合适的入市价格和好的行情机会,标准可能并不一样,因为不同人有不同的交易策略、风险偏好和盈利目标。对于喜欢做趋势跟踪的投资者来说,一波明显而持续的上涨或下跌趋势,可能就是最好的行情…...
SpringBoot多数据源切换 多数据源事务解决方案 二
https://zhuanlan.zhihu.com/p/612825647?utm_id0 https://blog.csdn.net/guzhangyu12345/article/details/108559810 SpringBoot多数据源事务解决方案 https://blog.csdn.net/u013407099/article/details/124526396多数据源切换下保证事务解决方案 https://blog.csdn.net/re…...
ElasticSearch 搜索推荐
Term Suggester "suggest_mode":"missing" missing 默认选项,不返回精准匹配到的分词结果 "suggest_mode":"popular" popular 大于等于搜索词频率的返回 "suggest_mode":"always", 不做任何限制&qu…...
Linux纯命令行查看文本文件
处理超大文本文件时,你可能希望避免一次性加载整个文件,这可能会耗尽内存资源。以下是一些在命令行中查看大文本文件的方法,它们适用于Linux和Unix系统,包括Mac OS X,而在Windows中,你可以使用类似的工具或…...
解决前端项目中Node.js版本不一致导致的依赖安装错误
解决前端项目中Node.js版本不一致导致的依赖安装错误 🌟 前言 欢迎来到我的小天地,这里是我记录技术点滴、分享学习心得的地方。📚 🛠️ 技能清单 编程语言:Java、C、C、Python、Go、前端技术:Jquery、Vue…...
IIoT 与 IoT 之间的区别
物联网世界充满了各式各样的首字母缩写词,从LPWAN到MQTT,再到广为人知的IoT。然而,这仅仅是冰山一角,物联网领域还有更多的变化等待我们去探索,其中就包括IIoT,即工业物联网。那么,你可能会问&a…...
spring boot3token拦截器链的设计与实现
⛰️个人主页: 蒾酒 🔥系列专栏:《spring boot实战》 🌊山高路远,行路漫漫,终有归途。 目录 写在前面 流程分析 需要清楚的 实现步骤 1.定义拦截器 2.创建拦截器链配置类 3.配置拦截器链顺序 4.配置拦截…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
