对最近的刷题做一个小总结(关于动态规划和贪心)

文章目录

  • 1. 小总结
  • 2. 两道算法题
    • 2.1 数组中两个字符串的最小距离
    • 2.2 孩子们的游戏

1. 小总结

最近刷了很多算法题,真正了解到的算法应是dfs,多元dfs,以及动态规划和贪心。

dfs和多元dfs目前并没有真正深入研究过,不过熟悉套路之后,整体的编写还是挺简单的。

对于动态规划,整体的逻辑还是很简单的,难就难在有些题,你看不出来可以用动态规划,比如“约瑟夫环”的问题,而且就算看出来是动态规划,如何确定状态表示,是从这里开始,还是到这里结束,是这两者都可以,还是只有一个可以,这些都是有讲究的,自己还需要再多刷一些动态规划的题目。不过,就我现在的感受而言,动态规划其实跟递推,函数递归等都很类似,本质上都是解决重复子问题。

至于贪心,贪心算法确实是没有那么好get到的,它的原理很简单,关键在于想清楚该怎么“贪”,并且要能够确保这样子“贪”,是正确的,能够从局部最优得到全局最优,这个确定还是比较复杂的。


2. 两道算法题

来看一道双指针和一道动态规划的问题。

2.1 数组中两个字符串的最小距离

题目描述:给定给定两个字符串str1和str2,再一个字符串数组strs,返回在strs中str1和str2的最小距离,如果str1或str2为null,或不在strs中,返回-1。
输入描述:输入包含有多行,第一输入一个整数n(1 <= n <= 100000),代表数组strs的长度,第二行有两个字符串分别代表str1和str2,接下来n行,每行一个字符串,代表数组strs(保证题目中出现的所有字符串长度均小于等于10)
输出描述:输出一行,包含一个整数,代表返回的值。
补充说明:时间复杂度O(n),额外空间复杂度O(1)

OJ链接

这道题,是在一个给定的字符数组中,找出两个字符串之间的最小距离。
考虑到,时间复杂度为O(n),所以暴力的O(n ^ 2)遍历肯定是不行的,这题显然应该在给定的原字符数组中用双指针来实现,这样能够满足时空复杂度的要求。

而要想做到使用双指针进行解决,必须找到一定的规律。

在这里插入图片描述
在上图中,如果想要找到两个字符串中的最小距离,有一点是很明确的:对于编号为4的“def”,编号为1的“abc”其实与之相距不可能是最小的,因为前面还有一个编号为2的"def",也就是说,以编号为4的"def"为基准时,另外一个指针没必要从头开始找,而这一点就是本题可以使用双指针的规律所在。

我们代码的整体逻辑就是:

  1. 先找到两个对应的字符串,然后根据下标,确定两个字符串的先后关系。
  2. 靠后的字符串先不动,靠前的字符串接着循环去找下一个与自身相同的字符串,在这个过程中,不断更新距离,直到这个字符串在原先靠后的字符串之后为止。
  3. 继续重复2中的逻辑,直到整个字符数组都被遍历完,跳出循环,此时得到的距离便是两个字符串在整个字符数组中,对应的最小距离。

具体I/O代码如下:

#include <iostream>
#include <vector>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;string s1,s2;cin >> n >> s1 >> s2;vector<string> arr;arr.reserve(n);string tmp;while(cin >> tmp){arr.push_back(tmp);}if(s1.empty() || s2.empty())printf("-1");int i = 0,j = 0,sz = arr.size();int distance = INT_MAX;while(i < sz && j < sz){while(i < sz &&  arr[i] != s1)i++;while(j < sz && arr[j] != s2)j++;if(i < sz && j < sz){distance = min(distance,abs(j - i));if(i < j){i++;while(i < sz && arr[i] != s1)i++;}else{j++;while(j < sz && arr[j] != s2)j++:}}}if(distance == INT_MAX)printf("-1");elseprintf("%d",distance);return 0;
}

2.2 孩子们的游戏

每年六一儿童节,牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中,有个游戏是这样的:首先,让 n 个小朋友们围成一个大圈,小朋友们的编号是0~n-1。然后,随机指定一个数 m ,让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0… m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客礼品,请你试着想下,哪个小朋友会得到这份礼品呢?

在这里插入图片描述
要求时间复杂度为O(n),空间复杂度为O(n)。
OJ链接

这是一道非常经典的约瑟夫环问题。

约瑟夫环问题大致有两种解法:

  1. 模拟实现约瑟夫环。使用循环链表可以对约瑟夫环进行很好地模拟,使用数组也可以模拟,不过没有循环链表那么方便,但是模拟的时间复杂度为O(m * n) ,空间复杂度为O(n),在这道题中,通过模拟实现约瑟夫环来解决问题是不合题意的。
  2. 使用动态规划解决约瑟夫环。使用动态规划解决约瑟夫环,寥寥几行代码便可以解决一个较为复杂的问题,是“四两拨千斤”的典范,且时空复杂度满足题意,故使用这种做法。

如何用动态规划解决约瑟夫环。

状态表示:dp[n]表示有n个人,最后留下来的那个人的编号

状态转移方程:这里状态转移方程的确定是一个难点,状态转移方程应为:dp[n] = (dp[n - 1] + m) % n。这里的+m是映射回去时所加,模上一个n是防止加上m之后,编号超过n - 1。

在这里插入图片描述
初始化:此处的动态规划只需用到前面一个的值,因此初始化dp[1]即可,dp[1]显然应该为0.
填表顺序:一维dp,用到前面的值,因此从左往右填表。
返回值:返回dp[n]即可。

不过,由于此题中要求空间复杂度为O(1),因此不能直接用dp表,而使用滚动数组进行空间复杂度的优化。

具体代码如下:

class Solution {
public:int LastRemaining_Solution(int n, int m) {int ret = 0;for(int i = 2;i <= n;i++)ret = (ret + m) % i;return ret;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/33349.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

jmeter分布式原理及实例

一、执行原理 二、相关注意事项 关闭防火墙所有上网控制机、代理机、服务器都在同一个网络上所有机器的jmeter和java版本必须一致关闭RMI.SSL开关 三、配置和执行 配置&#xff1a; 修改bin/jmeter.properties文件&#xff1a; 代理机&#xff1a; 修改服务端口&#xff1…

C++ STL 详解 ——vector 的深度解析与实践指南

一、vector 的核心概念与底层机制 1.1 动态数组的本质 连续内存存储&#xff1a;与普通数组相同&#xff0c;vector 使用连续的内存空间&#xff0c;支持 O (1) 时间复杂度的随机访问。动态扩容特性&#xff1a;通过push_back等操作自动调整容量&#xff0c;无需手动管理内存…

【SpringBoot】——在做一些项目中所学到的新的技术栈和一些小技巧(主要为MQ,详细请看目录和文章)

&#x1f3bc;个人主页&#xff1a;【Y小夜】 &#x1f60e;作者简介&#xff1a;一位双非学校的大三学生&#xff0c;编程爱好者&#xff0c; 专注于基础和实战分享&#xff0c;欢迎私信咨询&#xff01; &#x1f386;入门专栏&#xff1a;&#x1f387;【MySQL&#xff0…

0经验cursor开发一款跨端app

设备&#xff1a;mac电脑cursor 1.输入诉求 我要实现一个跨端的地址应用&#xff0c;使其可以在ios、安卓、小程序和网页端都可以使用。这是一个demo的项目&#xff0c;功能不必要太过复杂&#xff0c;下面需要你和我多次沟通完成这个任务。你先根据我的内容输入&#xff0c…

Element Ui - 编辑时表单校验信息未清空问题处理

Element Ui 关闭对话框清空验证消息&#xff0c;清除form表单的操作 首先在对话框 取消按钮 添加 click事件&#xff0c;例如&#xff1a;&#xff08;ps&#xff1a;callOf 里面的addGroupData和ref - - &#xff09; <div slot"footer" class"dialog-foo…

OpenCV图像加权函数:addWeighted

1 addWeighted函数 在OpenCV 里&#xff0c;addWeighted 函数的作用是对两个图像进行加权求和&#xff0c;常用于图像融合、图像过渡等场景。函数如下&#xff1a; cv2.addWeighted(src1, alpha, src2, beta, gamma[, dst[, dtype]])2 参数解释 src1&#xff1a;第一个输入图…

Science Robotics 利用机器学习进行鳐鱼的仿生设计

对于海洋生物而言&#xff0c;生物力学和流体动力学力都会对游泳速度施加物理限制&#xff0c;促使游泳策略和鳍形状的趋同进化。鉴于这些限制是与尺度相关的&#xff0c;如雷诺数&#xff08;Re&#xff09;&#xff0c;这就产生了自然运动缩放定律&#xff0c;该定律根据生物…

基于ssm的一家运动鞋店的产品推广网站的设计

项目简介 一家运动鞋店实现了以下功能&#xff1a; 实现了用户在线选择试题并完成答题&#xff0c;在线查看考核分数。管理员管理收货地址管理、购物车管理、字典管理、留言版管理、新闻信息管理、产品管理、产品收藏管理、产品评价管理、产品订单管理、单页数据管理、用户管…

什么是后训练?大语言模型训练后优化方法综述,87页pdf

大语言模型&#xff08;LLMs&#xff09;的出现彻底改变了自然语言处理领域&#xff0c;使其在从对话系统到科学探索的各个领域中变得不可或缺。然而&#xff0c;其预训练架构在特定场景中往往表现出局限性&#xff0c;包括推理能力受限、伦理不确定性以及领域特定性能欠佳等问…

python开发订单查询功能(flask+orm bee)

1. 搭建python环境。 可以参考其它文档。 此处python使用 3.12 IDE随意&#xff0c;PyCharm 或 Eclipse PyDev也可以。 2. Flask 2.1 安装Flask pip install Flask 2.2 一个最简单的flask实例 创建一个工程&#xff0c; 新建一个 main.py文件&#xff0c; 输入以下内容…

工作记录 2017-01-11

工作记录 2017-01-11 序号 工作 相关人员 1 协助BPO进行Billing的工作。 修改邮件上的问题。 更新RD服务器。 郝 更新的问题 1、修改了Patient Insurance的文件上传。 1.1 文件存储改为MedI“EHRWfs”Account“patientInfo”MRN 1.2 “Upload Files” to “Upload/Vie…

基于javaweb的SpringBoot个人健康管理系统小程序微信小程序设计与实现(源码+文档+部署讲解)

技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论…

b站视频下载工具软件怎么下载

自行配置FFMPEG环境 请优先选择批量下载&#xff0c;会自处理视频和音频文件。 如果要下载更高质量请登陆。 没有配置FFMPEG下载后会有报错提示&#xff0c;视频音频文件无法合并生成mp4文件 更新批量下载标题&#xff0c;只取视频原标题&#xff0c;B站反爬机制登陆后下载多了…

简单的模拟法

1. 鸡兔同笼问题&#xff0c;鸡有2只脚 &#xff0c;兔有4只脚&#xff0c;已知脚数求最多有几只动物 #include <stdio.h>void feet(int x){if(x%2 0){if(x%4 0) printf("max%d,min%d",x/2,x/4);else printf("max%d,min%d",x/2,(x-2)/41);}else …

【python爬虫】酷狗音乐爬取练习

注意&#xff1a;本次爬取的音乐仅有1分钟试听&#xff0c;仅作学习爬虫的原理&#xff0c;完整音乐需要自行下载客户端。 一、 初步分析 登陆酷狗音乐后随机选取一首歌&#xff0c;在请求里发现一段mp3文件&#xff0c;复制网址&#xff0c;确实是我们需要的url。 复制音频的…

概率论的基本知识

逆概率还不懂&#xff0c;改天再想想。 联合概率 联合概率&#xff08;Joint Probability&#xff09; 是概率论中的一个重要概念&#xff0c;用于描述多个随机变量同时取某些值的概率。联合概率可以帮助我们理解多个变量之间的关系。

Ceph(1):分布式存储技术简介

1 分布式存储技术简介 1.1 分布式存储系统的特性 &#xff08;1&#xff09;可扩展 分布式存储系统可以扩展到几百台甚至几千台的集群规模&#xff0c;而且随着集群规模的增长&#xff0c;系统整体性能表现为线性增长。分布式存储的水平扩展有以下几个特性&#xff1a; 节点…

Pytest自动化测试框架pytest-xdist分布式测试插件

平常我们功能测试用例非常多时&#xff0c;比如有1千条用例&#xff0c;假设每个用例执行需要1分钟&#xff0c;如果单个测试人员执行需要1000分钟才能跑完&#xff1b; 当项目非常紧急时&#xff0c;会需要协调多个测试资源来把任务分成两部分&#xff0c;于是执行时间缩短一…

在openEuler-22.03-LTS上利用Ansible轻松部署MySQL 5.7

一、需求 使用ansible自动化部署mysql二进制部署mysql部署mysql并创建JDBC用户 二、环境信息 本文涉及的代码&#xff0c;配置文件地址&#xff1a; 链接&#xff1a;百度网盘 请输入提取码 提取码&#xff1a;1g6y 软件名称版本备注Ansible2.9.27All modules — Ansible Doc…

使用GitHub Actions实现Git推送自动部署到服务器

将网站一键部署到服务器的方案很多&#xff0c;比如纯Shell脚本结合SSH、Jenkins等工具。本文将介绍如何利用GitHub Actions这一免费且轻量的CI/CD工具&#xff0c;实现代码推送后自动部署到云服务器。 之前一直在使用github的工作流&#xff0c;确实是一个比较好用的工具。 我…