剑指offer经典题目(七)
目录
动态规划
字符串相关
排序思想相关
链表相关
动态规划
题目1:输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,子数组最小长度为1。求所有子数组的和的最大值。OJ地址
图示如下。
题目解析: 如果单纯的从如何求解最大值这一点出发,依次的去累加连续的值并进行比较,这个题目实际上是非常复杂的,因为我们要遍历出所有可能得的子数组,然后依次的比较每个字数组的和,最终找出最大的子数组,这样去解决这个问题会比较麻烦,所以我们可以采用动态规划的方法去解决这道题。
动态规划分为三步。
- 定义状态。
- 列状态转移方程。
- 设置初始值。
定义状态。
我们认为,f(i) 就表示,以 i 下标,包含 i 下标结尾的子数组的最大值,比如 f(2) 就表示以下标为 2 的元素作为结尾的子数组的最大值。
列状态转移方程。
f(i) = max ( f(i-1) + arr[i] , arr[i] )
子数组可能只包含一个元素,也可能包含多个元素,所以以当前下标结尾的子数组的最大值,就可以认为是以前一个下标结尾的子数组的最大值加上当前元素的值之后与当前下标的元素进行比较的较大值。
设置初始值。
f(0) = arr[0]
以 0 下标结尾的子数组的最大值就是数组的第一个元素。
编码如下。
#include <algorithm>
class Solution {public:int FindGreatestSumOfSubArray(vector<int>& array) {if (array.size() == 0) {return 0;}int* dp = new int[array.size()];//dp[i]表示以下标i结尾的子数组的最大值dp[0] = array[0];int max_value = dp[0];for (int i = 1; i < array.size(); i++) {//状态转移方程dp[i] = max(dp[i - 1] + array[i], array[i]);if (max_value < dp[i]) {max_value = dp[i];}}delete []dp;return max_value;}
};
字符串相关
题目2:给定一个仅由小写字母组成的字符串。现在请找出一个位置,删掉那个字母之后,字符串变成回文。请放心总会有一 个合法的解。如果给定的字符串已经是一个回文串,那么输出-1。OJ地址
题目图示如下。
题目解析: 题目已经告诉了我们,如果这个字符不是一个回文串,那么就有且一个字符导致了这个字符不是一个回文串,所以只要删除了这个字符,那么删除这个字符之后的字符串一定是一个回文串。这便是此题的核心切入点。我们可以通过判断这个字符串是不是回文串,如果这个字符不是一个回文串,找到两个字符不相等的下标,然后删除一个下标对应的字符,如果删除之后对应的字符串是回文串,那么这个下标对应的字符其实就是我们要找的字符,最终返回该字符对应下标即可,如果不是返回另一个字符对应的下标即可,需要注意的就是我们得提前保存好对应字符的下标,具体操作看下述代码。
编码如下。
#include <iostream>
using namespace std;
#include<vector>
#include<string>static bool IsPalind(const string& str, int& start, int& end) {while (start < end) {if (str[start] != str[end]) {return false;} else {start++;end--;}}return true;
}int main() {int num;cin >> num;while (num) {num--;string s;cin >> s;int start = 0;int end = s.size() - 1;if (IsPalind(s, start, end)) {cout << -1 << endl;} else {int result1 = start;int result2 = end;s.erase(start, 1);start = 0;end = s.size() - 1;if (IsPalind(s, start, end)) {cout << result1 << endl;} else {cout << result2 << endl;}}}return 0;
}
排序思想相关
题目3:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。OJ地址
题目图示如下。
先问大家一个问题,求组合的最小的数,一定是将数组中的数从小到大组合吗?
这是我们普遍的一个误区,如果直接按照整型的大小进行组合,组合出的数不一定是组合最小的数。所以在进行组合时,我们是按照整数转为字典序之后进行比较,然后根据字符串比较的结果进行组合,此时组合的数才是整个数组组合之后的最小的数。
题目解析:将数组中的相邻两个整型转为字符串之后进行拼接,然后根据不同的顺序,保留最终字典序小的组合,然后根据这个组合调整数组中每个元素的位置。
编码如下。
#include <string>
class Solution {public:static bool comp(int x, int y) {//x,y构成的序列,小的放在前面string xs=to_string(x);string ys=to_string(y);string s1=xs;s1+=ys;string s2=ys;s2+=xs;return s1<s2;}string PrintMinNumber(vector<int>& numbers) {if (numbers.size() == 0) {return "";}sort(numbers.begin(), numbers.end(), comp);\string result;for(int i=0;i<numbers.size();i++){result+=to_string(numbers[i]);}return result;}
};
链表相关
题目4:输入两个链表,找出它们的第一个公共结点。
图示如下。
题目解析: 先统计出每个链表的节点的个数,然后计算出两个链表的节点的个数的差值,然后让链表的节点多的那个链表先让它的指针往后走差值步,然后让两个链表同时向后进行遍历,当两个链表遍历到相同的节点时,就证明这个节点就是两个链表的第一个公共节点。
编码如下。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {public:static int GetLength(ListNode* head) {int count = 0;while (head) {count++;head = head->next;}return count;}ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {if (pHead1 == nullptr || pHead2 == nullptr) {return nullptr;}//计算每个链表的长度int length1 = GetLength(pHead1);int length2 = GetLength(pHead2);int step = abs(length1 - length2);if (length1 > length2) {while (step) {pHead1 = pHead1->next;step--;}} else {while (step) {pHead2 = pHead2->next;step--;}}while (pHead1 && pHead2) {if (pHead1 == pHead2) {return pHead1;}pHead1 = pHead1->next;pHead2 = pHead2->next;}return nullptr;}
};
以上便是本期的所有内容。
本期内容到此结束^_^
相关文章:
剑指offer经典题目(七)
目录 动态规划 字符串相关 排序思想相关 链表相关 动态规划 题目1:输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,子数组最小长度为1。求所有子数组的和的最大值。OJ地址 图示如下。 题目解析:…...
[RoarCTF 2019]Easy Calc 详解
[RoarCTF 2019]Easy Calc 1 ajax 是进行前后端交互的 但是我们发现一个waf 就是他提示的"calc.php?num"encodeURIComponent($("#content").val()) ?num 的值必须是数字审计一下 foreach 发现了num的限制但是eval是rce的标志所以我们首选的就是使用命令…...
AI日报 - 2025年04月29日
🌟 今日概览(60秒速览) ▎🤖 AGI突破 | 巨头CEO预测AGI时间线,5年内或达人类认知水平;Yann LeCun强调多模态训练重要性。 关于AGI定义和实现时间的讨论升温,对超越纯文本训练的需求成为共识。 ▎💼 商业动向…...
Kubernetes的错误信息处理
报错信息 E0428 13:18:25.531614 3193818 memcache.go:287] couldn’t get resource list for metrics.k8s.io/v1beta1: the server is currently unable to handle the request 以下是处理该 Kubernetes 指标服务报错的系统化解决方案: 错误诊断流程 # 1. 检查 …...
杰理-安卓通过map获取时间的时候,部分手机切换sbc和aac时候单耳无声音
杰理-安卓通过map获取时间的时候,部分手机切换sbc和aac时候单耳无声音 #if USER_SUPPORT_PROFILE_MAPif(tws_api_get_role()0){ //主机才获取,否则切换sbc 和 aac 的时候影响单耳无声音user_send_cmd_prepare(USER_CTRL_MAP_READ_TIME,0,NULL);} #endif…...
基于 Python 的实现:居民用电量数据分析与可视化
基于 Python 的实现:居民用电量数据分析与可视化 本文将介绍如何利用 Python 技术栈(包括 pymysql、pandas、matplotlib 等库)对居民用电量数据进行分析和可视化,以帮助我们更好地理解用电行为模式。 数据准备 在MySQL数据库中创建数据,,数据库表结构如下: date:记录…...
el-transfer穿梭框数据量过大的解决方案
一:背景 我们这个穿梭框获取的是项目的全量数据,在左边大概有5000条,自己测试了一下5000条数据的效果,发现异常的卡顿,本来打算像el-select一样去解决的(只显示一部分,在搜索的时候去全量搜索&a…...
【3D基础】深入解析OBJ与MTL文件格式:Blender导出模型示例及3D开发应用
引言 在3D模型开发和3D引擎加载过程中,OBJ格式是最基础、最常见的标准之一。即便在今天流行的GLTF、USDZ格式出现后,OBJ依然是建模软件和渲染引擎普遍支持的基本格式。 本文以Blender导出的立方体模型为例,详细讲解OBJ与MTL文件每一部分的含…...
Fiddler+Yakit实现手机流量抓包和小程序抓包
文章目录 一、小程序抓包1、配置Fiddler2、配置Yakit 二、手机流量抓包1、配置Fiddler2、手机连接电脑热点并配置代理服务器3、手机安装证书4、配置Yakit 三、总结 操作工具:Yakit Fiddler 一、小程序抓包 1、配置Fiddler 点击Tools—>Options进入如下配置页面…...
C++实时统计数据均值、方差和标准差
文章目录 1. 算法原理2. 类设计3. 完整代码实现4. 总结 本文采用了一种递推计算方法(Welford 算法)实时更新数据的均值、方差和标准差,其算法原理及实现如下。 1. 算法原理 Welford算法是由B.P.Welford于1962年提出的,用于计…...
【广州华锐视点】AR 远程协同:突破时空限制的利器
AR 远程协同,简单来说,就是利用增强现实(AR)技术,打破地理空间的束缚,让身处不同地方的人们能够在同一虚拟空间中进行实时协作。它就像是为人们搭建了一座无形的桥梁,将现实与虚拟紧密相连,让沟通和协作变得…...
【Docker】——在Docker工具上安装创建容器并完成项目部署
🎼个人主页:【Y小夜】 😎作者简介:一位双非学校的大三学生,编程爱好者, 专注于基础和实战分享,欢迎私信咨询! 🎆入门专栏:🎇【MySQL࿰…...
9. 使用Gazebo和Rviz显示机器人(包括运动控制,雷达,摄像头仿真以及显示)
概述:通过Gazebo和Rviz集成机器人,机器人的组件包括底盘,雷达,摄像头,可以在Gazebo中仿真和显示。并且能够订阅运动控制话题,雷达话题,摄像头话题在Rviz中仿真和显示。 1.新建功能包和导入依赖 …...
跨语言哈希一致性:C# 与 Java 的 MD5 之战?
在跨平台或异构系统集成的场景中,我们经常需要在不同的编程语言之间交换数据或验证数据一致性。MD5 作为一种广泛使用的哈希算法,就常常扮演着生成唯一标识或校验数据完整性的角色。然而,不少开发者可能会遇到这样一个令人困惑的问题…...
赋能航天教育:高校卫星仿真教学实验平台解决方案
随着全球航天事业的飞速发展,对高素质航天人才的需求日益增长。如何在高校阶段提前锻炼学生的航天工程实践能力,成为教育界的重要命题。作为领先的通信与网络技术供应商,IPLOOK基于自身在5G核心网、卫星通信及仿真平台领域的深…...
H指数(中等)
可以先对数组从小到大排序,然后数组后面往前遍历,计算h的值。 如果从后往前遍历,当前位置的数,如果大于h,就说明又找到了一个引用次数大于h的文献,h指数可以加一了。 class Solution {public int hIndex(…...
推荐 1 款 9.3k stars 的全景式开源数据分析与可视化工具
Orama 是一个开源的数据分析与可视化项目,由askorama团队开发和维护。该项目旨在为用户提供一套强大而易用的工具集,帮助用户轻松处理和理解大规模数据,通过创建交互式且引人入胜的数据可视化图表,揭示隐藏在数据背后的深层次洞察…...
无人船 | 图解基于LQR控制的路径跟踪算法(以全驱动无人艇WAMV为例)
目录 1 最优控制线性二次型问题2 LQR的价值迭代推导3 基于全驱动无人船动力学的LQR4 跟踪效果分析 1 最优控制线性二次型问题 最优控制理论是一种数学和工程领域的理论,旨在寻找如何使系统在给定约束条件下达到最佳性能的方法。它的基本思想是通过选择合适的控制输…...
检查IBM MQ SSL配置是否成功
使用 DISPLAY 命令检查任务是否已成功完成。 如果任务成功,那么生成的输出类似于以下示例中显示的输出。 从队列管理器 QM1,输入以下命令: DISPLAY CHS(QM1.TO.QM2) SSLPEER SSLCERTI 生成的输出类似于以下示例: DISPLAY CHSTATUS(QM1.TO.QM2) SSLPE…...
EasyRTC嵌入式音视频通信SDK智能安防与监控系统的全方位升级解决方案
一、方案背景 随着安全防范意识的提升以及物联网、人工智能技术的发展,智能安防与监控系统在各领域的应用愈发广泛。传统监控系统多以单向视频传输为主,缺乏实时交互能力。EasyRTC凭借其低延迟、高可靠的实时音视频通信技术,能为智能安防与…...
Meta 推出 WebSSL 模型:探索 AI 无语言视觉学习,纯图训练媲美 OpenAI CLIP
Web-SSL 探索了视觉自监督学习(SSL)在网络规模数据上的扩展潜力。通过调整模型大小和训练数据,我们证明了纯视觉模型可以与 CLIP 等语言监督方法相媲美,甚至超越它们,从而对 "语言监督是学习多模态建模所需的强大…...
node.js puppeteer 实践
puppeteer 介绍 Puppeteer 是 Google 推出的一个 Node.js 库,它通过 Chromium 提供了一个高效、简洁的 API,用于操作无头浏览器或具有 UI 的完整浏览器。它广泛应用于 自动化测试、数据抓取、页面性能分析和 UI 测试等领域。 Puppeteer 是一个 Node 库&…...
【现代深度学习技术】循环神经网络07:通过时间反向传播
【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈PyTorch深度学习 ⌋ ⌋ ⌋ 深度学习 (DL, Deep Learning) 特指基于深层神经网络模型和方法的机器学习。它是在统计机器学习、人工神经网络等算法模型基础上,结合当代大数据和大算力的发展而发展出来的。深度学习最重…...
如何在idea中写spark程序
一、环境准备 1. 安装 IntelliJ IDEA: 下载并安装 IntelliJ IDEA(推荐使用 Community 版本,它已经支持 Scala 和 Spark 开发)。 官方下载地址:[JetBrains IntelliJ IDEA](https://www.jetbrains.com/idea/downlo…...
硬件加密+本地部署,大模型一体机如何打造AI安全护城河?
2025年,大模型技术加速渗透千行百业,但随之而来的安全风险也引发广泛关注。数据显示,近九成企业部署的大模型服务器存在“裸奔”隐患,数据泄露、模型篡改、算力劫持等问题频发。 在此背景下,大模型一体机凭借“开箱即…...
在另外一台可以科学下载的电脑用ollama下载模型后,怎么导入到另外一台服务器的ollama使用
环境: Win10专业版 Ubuntu20.04 问题描述: 在另外一台可以科学下载的电脑用ollama下载模型后,怎么导入到另外一台服务器的ollama使用,原电脑win10上的ollama下载的模型,复制到ubuntu20.04的ollama上推理 解决方案:…...
鼠标滚动字体缩放
在VsCode中编辑文件时,有时候发现Ctrl鼠标滚轮并不能缩放字体,下面是启用这个功能的方法。 第一步: 进入设置,可以从左下角按钮菜单进入,也可以使用【Ctrl,】。 第二步: 启用鼠标滚轮缩放功能 第三步&…...
什么是VR相机?VR相机的发展历史
VR相机:沉浸式体验的未来科技 VR相机,全称为虚拟现实相机,是专门用于捕捉和记录三维空间和场景的设备,能够拍摄360度全景照片和视频。通过模拟人的双眼视觉差异,利用多个镜头和传感器同时捕捉周围环境的图像ÿ…...
Java面试:Spring及Spring Cloud技术深度剖析
Spring及Spring Cloud技术深度剖析 前言 在Java开发领域,Spring框架一直是企业级应用开发的中流砥柱,而Spring Boot的出现更是极大地简化了Spring应用的开发过程。同时,Spring Cloud为构建分布式系统提供了强大的支持。本文将围绕Spring及S…...
论文阅读_Search-R1_大模型+搜索引擎
英文名称:Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning 中文名称:Search-R1:训练大型语言模型进行推理并利用搜索引擎的强化学习 链接: http://arxiv.org/pdf/2503.09516v2 代码: https://g…...
零成本AI抠图终极指南:蓝耘元生代AIDC OS+ComfyUI实现商业级效果
引言:AI抠图革命已经到来 在数字内容创作爆炸式增长的今天,高质量的图像处理已成为刚需。无论是电商平台的商品展示、自媒体博主的封面设计,还是摄影爱好者的后期处理,抠图都是最基础也是最繁琐的工作之一。 传统抠图方式面临三…...
深入理解CSS3:Flex/Grid布局、动画与媒体查询实战指南
引言 在现代Web开发中,CSS3已经成为构建响应式、美观且高性能网站的核心技术。它不仅提供了更强大的布局系统(Flexbox和Grid),还引入了令人惊艳的动画效果和精准的媒体查询能力。本文将深入探讨这些关键技术,帮助您提…...
VLM-E2E:通过多模态驾驶员注意融合增强端到端自动驾驶——论文阅读
《VLM-E2E Enhancing End-to-End Autonomous Driving with Multimodal Driver Attention Fusion》2025年2月发表,来自香港科大广州分校、理想汽车和厦门大学的论文。 一、核心问题与动机 现有端到端(E2E)自动驾驶系统直接从传感器输入映射到…...
蓝牙BLE
1、简介 蓝牙BR/EDR和BLE是蓝牙技术的两个重要分支,它们各自具有独特的特点和应用场景。 1.1、蓝牙BR/EDR 蓝牙BR(Basic Rate) 定义:蓝牙技术的首个开发版本,采用高斯频移键控(GFSK)调制技术…...
在VS2022中使用Lua与c交互(二)
一、核心交互机制:Lua 虚拟栈 Lua 与 C 的交互通过一个 虚拟栈(Stack) 完成,所有数据传递、函数调用均通过此栈实现。栈的每个元素可以是任意 Lua 类型(如数字、字符串、表、函数等)。 栈的结构与…...
论文阅读_Citrus_在医学语言模型中利用专家认知路径以支持高级医疗决策
英文名称:Citrus: Leveraging Expert Cognitive Pathways in a Medical Language Model for Advanced Medical Decision Support 中文名称:Citrus:在医学语言模型中利用专家认知路径以支持高级医疗决策 链接: http://arxiv.org/pdf/2502.18…...
浅谈PCB传输线(一)
前言:浅谈传输线的类型,以及传输线的一些行为特性。 1.传输线的种类 2.互连线被视为传输线的场景 3.传输线的行为特性*** 1.传输线的种类 PCB 中的信号传输线通常有两种基本类型: 微带线和带状线。此外,还有第三种类型–共面线(没有参考平面…...
Spring-全面详解(学习总结)
一:概述 1.1 为什么学 解决了两个主要问题 1. 2 学什么 1.3 怎么学 二:系统架构 作用:web开发、微服务开发、分布式系统开发 容器:用于管理对象 AOP:面向切面编程(不惊动原始程序下对其进行加强) 事…...
突破JVM边界:类加载三重门与栈帧的生存法则
类加载子系统 文件验证阶段 类加载子系统在加载Class文件时,首先会验证文件格式规范,检查文件开头的魔数标识,确保这是一个合法的JVM字节码文件。 职责边界 该子系统仅负责将Class文件加载到内存中,并不关心后续能否成功执行—…...
VSCode 查看文件的本地修改历史
1. 使用时间线视图(Timeline) 新版 VSCode 内置了一个叫 Timeline(时间线) 的功能,可以查看: 本地文件修改记录(包括保存历史)Git 提交历史(如果仓库是 Git 管理的&…...
在QGraphicsView中精确地以鼠标为锚缩放图片
在pyqt中以鼠标所在位置为锚点缩放图片-CSDN博客中的第一个示例中,通过简单设置: self.setTransformationAnchor(QGraphicsView.AnchorUnderMouse) 使得QGraphicsView具有了以鼠标为锚进行缩放的功能。但是,其内部应当是利用了滚动条的移动来…...
【Python数据驱动决策】数据分析与可视化全流程实战指南
目录 前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比二、实战演示环境配置要求核心代码实现案例1:销售数据清洗案例2:月度销售趋势分析案例3:产品关联分析(热力图)运行结果验证三、性能对…...
报错解决:ModuleNotFoundError: No module named ‘triton.ops‘
报错原因:2024.5.21之后, triton.ops 被移动到另一个工程 triton-lang/kernels中。 参考链接:官方解释 解决方案:换用2024.5.21之前发布的版本。 pip3 install triton2.3.0...
相机-IMU联合标定:相机-IMU外参标定
文章目录 📚简介🚀标定工具kalibr🚀标定数据录制🚀相机-IMU外参标定📚简介 在 VINS(视觉惯性导航系统) 中,相机-IMU外参标定 是确保多传感器数据时空统一的核心环节,其作用可概括为以下关键点: 坐标系对齐(空间同步),外参误差会导致视觉特征点投影与IMU预积…...
Qt C++数据库实验
一、实验目的和要求 1、掌握Qt中数据库SQL类数据库的查询、插入和更新操作。 2、熟悉Qt界面设计中常用的控件。 3、了解数据库相关类。 二、实验内容 1、设计一个数据库操作软件,完成数据库的相关操作。 2、建立按钮的信号与槽函数,实现点击按钮进…...
相机-IMU联合标定:IMU标定
文章目录 📚 简介🚀标定工具安装📌 IMU标定工具 code_utils📌 IMU标定工具 imu_utils:🚀标定数据录制🚀IMU标定📚 简介 在 VINS(Visual-Inertial Navigation System,视觉惯性导航系统) 中,IMU标定 是确保系统高精度运行的关键环节。IMU(惯性测量单元)本身…...
榕壹云信用租赁系统:基于ThinkPHP+MySQL+UniApp的全链路免押租赁解决方案
信用租赁时代的全流程数字化革新 随着共享经济与信用体系的深度融合,传统租赁行业正面临效率与信任的双重挑战。榕壹云信用租赁系统依托ThinkPHP高性能框架、MySQL数据库与UniApp跨平台开发技术,构建了一套覆盖设备租赁全生命周期的数字化解决方案。通过整合多因子身份认证、…...
C语言中的指针详解
指针是C语言中非常强大且复杂的特性之一,它为我们提供了更灵活的内存管理方式,使得程序能够直接操作内存,提升效率和性能。尽管指针非常强大,但如果不理解它的概念和使用方式,很容易出现错误。因此,理解指针…...
NIPS2021 | 视觉 Transformer 的有趣特性
Intriguing Properties of Vision Transformers 摘要-Abstract引言-Introduction相关工作-Related Work视觉Transformer的有趣特性-Intriguing Properties of Vision Transformers视觉Transformer对遮挡具有鲁棒性吗?-Are Vision Transformers Robust to Occlusions…...
贪心算法-2208.将数组和减半的最小操作数-力扣(LeetCode)
一、题目解析 这里要注意恰好这个字眼,说明对任意数减小一半是不需要向上取整的,所以我们需要定义double类型的数据。 二、算法解析 我们需要将数组和减小为一半的次数最少,所以根据贪心算法,我们需要取数组中最大的数进行减半操…...