算法笔试模拟题精解之“字符配对”-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

算法笔试模拟题精解之“字符配对”

简介: 本题可以使用动态规划来解决,对于第i个字符,有选和不选两种,如果选,则和第i-1个字符组合创造权值,如果不选,就单独出来没有权值,取两者中加权最大的选择。
+关注继续查看

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。点击链接开始体验:https://developer.aliyun.com/coding

本文为大家介绍其中的第73题:字符配对 的题目解析,具体如下:

题目描述

题目等级:中等
知识点:DP

查看题目:字符配对 给你一个字符串,字符串中仅包含"A","B",现在有四种字符串"AA","AB","BA","BB",每种字符串都有他们的权值,问从给出的字符串中能够得到的最大权值为多少(一个字符只能属于一个子字符串)?

输入一个字符串s(1 <= |s| <=10^6);
再输入一个数组,数组中包含四个数字a,b,c,d,依次表示字符串"AA","AB","BA","BB"的权值(1 <= a,b,c,d <= 100)。

输出权值的最大值。

示例1
输入:
"ABA"
[1 ,2, 3, 4]
输出:
3

解题方法:DP

大致思路:动态规划问题,对于第i个字符,有选和不选两种,如果选,则和第i-1个字符组合创造权值,如果不选,就单独出来没有权值,取两者中加权最大的选择。
具体过程:定义一个字典map,key分别为"AA","AB","BA","BB",value为对应的权值。定义大小为n的数组dp,dp[i]表示前i个字符组成的最大权值,毫无疑问,dp[0]=0,dp[1]=map.get(s.substring(0, 2));

从i=2开始遍历字符串,对于dp[i],有两个选择,一种是让第i个字符独立,即此时的权值dp[i]=dp[i-1],因为第i个字符没有创造价值。

另一种选择是让第i个字符有价值,即第i-1个字符和第i个字符组合创造价值,此时dp[i]=dp[i-2]+map.get(s.substring(i-1,i+1)).针对这两个选择,取权值最大的即可。

因此,dp[n-1]为最终答案。

时间复杂度为O(n)
空间复杂度为O(n)

看完之后是不是有了想法了呢,题目直达链接:查看题目:字符配对

720-150.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
948 0
比特币系统采用的公钥密码学方案和ECDSA签名算法介绍——第一部分:原理
ECC算法是基于有限域的椭圆曲线上的数学算法。关于ECC算法基本原理的介绍,请参考《ECC加密算法入门介绍》(http://www.8btc.com/eccmath),本文重点介绍Bitcoin系统中采用的公钥密码学方案和签名算法的实现细节。
1511 0
进化算法可以不再需要计算集群,开普敦大学的新方法用一块GPU也能刷新MNIST记录
他们实验中只使用了一块GTX1070 GPU,训练时间6到24小时,就可以取得这样的成果,他们觉得非常满意。他们的研究也首次尝试了把神经进化用在一维卷积网络的创造中,用来解决情感分析、包括嵌入层的优化问题。
1297 0
算法笔试模拟题精解之“恐怖的辐射”
因为N M 和最大辐射值都不大,所以可以直接模拟辐射扩散的实际情况,最后判断是否有小于等于7的位置。
324 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4479 0
算法题——投篮比赛获胜概率问题
问题描述: 甲乙两人比赛投篮。约定甲先投篮,每人投篮投进一球,则继续投球,若投失一球,则换人投球。初始积分为1分,甲每投进一球,积分加1分;乙每投进1球,积分减1分。若积分达到N分(N>1),甲获胜;若积分减至0分,乙获胜。
733 0
合辑 | 10+笔试算法模拟题精解,带你玩转算法!
阿里云开发者社区在线编程频道部分笔试算法模拟题题目解析合辑,参与做题的同学快来对答案啦!
4357 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载