psd面试(最长回文子序列+动态规划);

2024-09-05 21:38

本文主要是介绍psd面试(最长回文子序列+动态规划);,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

点击打开链接

链接:https://www.nowcoder.com/acm/contest/90/D
来源:牛客网

题目描述

掌握未来命运的女神 psd 师兄在拿了朝田诗乃的 buff 后决定去实习。
埃森哲公司注册成立于爱尔兰,是一家全球领先的专业服务公司,为客户提供战略、咨询、数字、技术和运营服务及解决方案。他们立足商业与技术的前沿,业务涵盖40多个行业,以及企业日常运营部门的各个职能。凭借独特的业内经验与专业技能,以及翘楚全球的交付网络,他们帮助客户提升绩效,并为利益相关方持续创造价值。埃森哲是《财富》全球500强企业之一,目前拥有约41.1万名员工,服务于120多个国家的客户。于是psd打算去埃森哲公司投一下简历。
于是他用英文写了一篇简历,由于手速太快了以致自己都不知道写了什么。
然而面试官 xwc 一眼就看到了重点:大学打过 ACM!
xwc:“
    听说你很低袄?考你个题:
    忽略字母大小写,你这篇简历去掉最长的回文子序列后还有多长?

psd 顺手就把这个问题抛给了你。

输入描述:

多组输入,每组输入一个长度不超过 1234 的没空格的字符串,是 psd 的简历。

输出描述:

每组输出一个整数,如题。

子问题:从i为头以j为尾的子串中最长回文子序列的长度是多少;

由子问题可得状态dp[i][j]是以i为头以j为尾的子串中最长回文子序列的长度是多少;

状态转移方程:有两个决策:

1:当该子串首尾相同时,该子串的最长回文子序列的长度可由该子串不包括首尾的最长子串的最长回文子序列长度转移过来;即dp[i][j]=dp[i+1][j-1]+2;

2:当该子串的首尾不同时,该子串的最长回文子序列的长度可由该子串的最长子串(不包括该子串本身)的最长回文子序列转移过来;因为该子串的最长子串(不包括该子串本身)有两个,所以状态转移方程为 dp[i][j]=max(dp[i][j-1],dp[i+1][j]);

注意:因为dp[i][j]必须从dp[i+1][j-1]或dp[i+1][j-1]或dp[i][j-1]转移过来,所以状态dp[i+1][j-1],dp[i+1][j-1],dp[i][j-1]必须在dp[i][j]前面;所以i是递减的,j是递增的。又由i,j含义可得i<j;

代码如下

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
/*
google
输出2
示例2
输入aBc,bAd
输出2
*/
const int INF = 1240;int LongestPalindromeSubsequence(char* str,int len);void Preprocessing(char* str,int len) ;int dp[INF][INF];int main()
{char data[INF] ;while(~scanf("%s",data)){int length = strlen(data);Preprocessing(data,length);             				//预处理,使字符串统一为小写字母 int result = LongestPalindromeSubsequence(data,length);  //最长回文子序列 printf("%d\n",length-result);}return 0;
}
int LongestPalindromeSubsequence(char* str,int len)
{memset(dp,0,sizeof(dp));for(int i = len-1;i >= 0;i--){dp[i][i]=1;for(int j = i+1;j < len;j++){if(str[i] == str[j]){dp[i][j] = dp[i+1][j-1] += 2;}else{dp[i][j] = max(dp[i+1][j],dp[i][j-1]);}} }return dp[0][len-1];
}
void Preprocessing(char* str,int len) 
{for(int i = 0;i < len;i++){if(str[i] >= 'A' && str[i] <= 'Z')str[i] += 32;}
}


这篇关于psd面试(最长回文子序列+动态规划);的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1140136

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl