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

【算法刷题】Day30

文章目录

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

1. 汉诺塔问题

在这里插入图片描述
原题链接


题干:

在这里插入图片描述
在这里插入图片描述


算法原理:

利用递归算法

将x柱子上的一堆盘子,借助 y柱子,转移到z 柱子上面

递归函数流程:

  1. 当前问题规模为 n=1 时,直接将 A 中的最上面盘子挪到 C 中并返回
  2. 递归将 A 中最上面的 n-1 个盘子挪到 B 中
  3. 将 A 中最上面的⼀个盘子挪到 C 中
  4. 将 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. 合并两个有序链表

在这里插入图片描述

原题链接


题干:

升序 链表
新链表是通过拼接给定的两个链表的所有节点组成的
在这里插入图片描述


算法原理:

  1. 重复子问题(函数头的设计)
    合并两个有序链表

  2. 只关心一个子问题咋做什么(函数体的设计)
    选择两个头结点中较小的结点作为最终合并后的头结点,然后将剩下的链表交给递归函数去处理

  3. 递归的出口
    谁为空返回另一个


代码:

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. 从宏观角度
    1)让当前节点后面的链表先逆序,并且把头结点返回
    2)让当前节点添加到逆置后的链表的后面
  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. 初始化

  1. 辅助结点里面的值要「保证后续填表是正确的」
  2. 「下标的映射关系」

在这里插入图片描述

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. 初始化

  1. 辅助结点里面的值要「保证后续填表是正确的」
  2. 「下标的映射关系」
  3. 在这里插入图片描述

4. 填表顺序

从左往右

5. 返回值

  1. 先找到 f 表里面的最大值 -> fmax
  2. 找到 g 表里面的最小值 -> gmin
  3. 统计所有元素的和 -> sum
  4. 返回 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. 汉诺塔问题题干&#xff1a;算法原理&#xff1a;代码&#xff1a; 2. 合并两个有序链表题干&#xff1a;算法原理&#xff1a;代码&#xff1a; 3. 反转链表题干&#xff1a;算法原理&#xff1a;代码&#xff1a; 4. 最大子数组和题干&#xff1a;算法原理&#…...

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进行工作的时候&#xff0c;可以集成第三方的编辑器进行源文件编辑工作 2、 问题场景 用于解决在GHS中进行项目开发时&#xff0c;对于GHS的编辑器使用不习惯&#xff0c;想要切换到其他第三方的编辑…...

【Flutter】 search_page使用心得

https://pub.dev/packages/search_page 以上就是search_page地址。使用方法跟具有哪些功能网页都有&#xff0c;这篇文章主要讲我在使用这个插件时遇到的坑。 坑1&#xff1a;不能自己刷新界面 我在search_page中传入的builder是带有checkbox的ListTile&#xff0c;当我点击…...

前端Vue列表组件 list组件:实现高效数据展示与交互

前端Vue列表组件 list组件&#xff1a;实现高效数据展示与交互 摘要&#xff1a;在前端开发中&#xff0c;列表组件是展示数据的重要手段。本文将介绍如何使用Vue.js构建一个高效、可复用的列表组件&#xff0c;并探讨其在实际项目中的应用。 效果图如下&#xff1a; 一、引言…...

每日OJ题_哈希表⑤_力扣49. 字母异位词分组

目录 力扣49. 字母异位词分组 解析代码 力扣49. 字母异位词分组 49. 字母异位词分组 难度 中等 给你一个字符串数组&#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入…...

【Linux】-Linux下的软件商店yum工具介绍(linux和windows互传文件仅仅一个拖拽搞定!!!!)

目录 1.Linux 软件包管理器yum 1.1快速认识yum 1.2 yumz下载方式&#xff08;如何使用yum进行下载&#xff0c;注意下载一定要是root用户或者白名单用户&#xff08;可提权&#xff09;&#xff09; 1.2.1下载小工具rzsz 1.2.2 rzsz使用 1.2.2查看软件包 1.3软件的卸载 2.yum生…...

320: 鸡兔同笼(python)

题目描述 一个笼子里关了鸡和兔&#xff08;鸡有2只脚&#xff0c;兔又4只脚&#xff0c;没有例外&#xff09;。已知笼子里面脚的总数a&#xff0c;问笼子里面至少有多少只动物&#xff0c;至多有多少只动物&#xff1f; 输入 多组测试数据。第一行是测试数据的组数n&#…...

CentOS 8启动流程

一、BIOS与UEFI BIOS Basic Input Output System的缩写,翻译过来就是“基本输入输出系统”,是一种业界标准的固件接口,第一次出现在1975年,是计算机启动时加载的第一个程序,主要功能是检测和设置计算机硬件,引导系统启动。 UEFI Unified Extensible Firmware interfac…...

js【详解】原型 vs 原型链

原型 每个 class 都有显示原型 prototype每个实例都有隐式原型_proto_实例的_proto_指向对应 class 的 prototype 如下范例&#xff1a; class Student 创建了 实例 xialuo 获取属性 xialuo.name 或执行方法 xialuo.sayhi()时&#xff0c;先在自身属性和方法寻找&#xff0…...

贪心算法: 奶牛做题

5289. 奶牛做题 - AcWing题库 贝茜正在参加一场奶牛智力竞赛。 赛事方给每位选手发放 n 张试卷。 每张试卷包含 k 道题目&#xff0c;编号 1∼k。 已知&#xff0c;不同卷子上的相同编号题目的难度相同&#xff0c;解题时间也相同。 其中&#xff0c;解决第 i 道题&#xff08;…...

go语言tcp协议实现文件上传

一、客户端实现方案&#xff1a; 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特性在菜单栏添加选项按钮 特性名&#xff1a;MenuItem 命名空间&#xff1a;UnityEditor 要求&#xff1a;一定是静态方法&#xff1b;新建的这个菜单栏按钮 必须有至少一个斜杠 不然会报错 它不支持只有一个菜单…...

做伦敦银要等怎样的价格与行情?

对于不同的伦敦银投资者来说&#xff0c;合适的入市价格和好的行情机会&#xff0c;标准可能并不一样&#xff0c;因为不同人有不同的交易策略、风险偏好和盈利目标。对于喜欢做趋势跟踪的投资者来说&#xff0c;一波明显而持续的上涨或下跌趋势&#xff0c;可能就是最好的行情…...

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 默认选项&#xff0c;不返回精准匹配到的分词结果 "suggest_mode":"popular" popular 大于等于搜索词频率的返回 "suggest_mode":"always", 不做任何限制&qu…...

Linux纯命令行查看文本文件

处理超大文本文件时&#xff0c;你可能希望避免一次性加载整个文件&#xff0c;这可能会耗尽内存资源。以下是一些在命令行中查看大文本文件的方法&#xff0c;它们适用于Linux和Unix系统&#xff0c;包括Mac OS X&#xff0c;而在Windows中&#xff0c;你可以使用类似的工具或…...

解决前端项目中Node.js版本不一致导致的依赖安装错误

解决前端项目中Node.js版本不一致导致的依赖安装错误 &#x1f31f; 前言 欢迎来到我的小天地&#xff0c;这里是我记录技术点滴、分享学习心得的地方。&#x1f4da; &#x1f6e0;️ 技能清单 编程语言&#xff1a;Java、C、C、Python、Go、前端技术&#xff1a;Jquery、Vue…...

IIoT 与 IoT 之间的区别

物联网世界充满了各式各样的首字母缩写词&#xff0c;从LPWAN到MQTT&#xff0c;再到广为人知的IoT。然而&#xff0c;这仅仅是冰山一角&#xff0c;物联网领域还有更多的变化等待我们去探索&#xff0c;其中就包括IIoT&#xff0c;即工业物联网。那么&#xff0c;你可能会问&a…...

spring boot3token拦截器链的设计与实现

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《spring boot实战》 &#x1f30a;山高路远&#xff0c;行路漫漫&#xff0c;终有归途。 目录 写在前面 流程分析 需要清楚的 实现步骤 1.定义拦截器 2.创建拦截器链配置类 3.配置拦截器链顺序 4.配置拦截…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...