【算法刷题】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.配置拦截…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
