笔试题之构造回文（lcs问题）2017腾讯暑假校招(代码片段)

关键词：

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

abcda
google

2
2

分析：
要求删掉字符最少，也就是最长的回文串，回文串的性质是正反读起来一样，所以我们将当前字符串逆反得到一个新的字符串，然后求得这两个字符串的最长公共子序列的长度
然后字符串的总长度减去最长公共子序列的长度，就是最少需要删除的字符的个数

code：

#include<bits/stdc++.h>
using namespace std;
#define max_v 1005
#define me(a,x) memset(a,x,sizeof(a))
typedef long long LL;
int dp[max_v][max_v];//dp[i][j]表示a0.....ai和b0....bj的LCS长度
char a[max_v],b[max_v];
int main()

    while(~scanf("%s",a))
    
        int n=strlen(a);
        for(int i=n-1,k=0;i>=0;i--)
        
            b[k++]=a[i];//得到原串的逆反串
        
        me(dp,0);
        for(int i=1;i<=n;i++)
        
            for(int j=1;j<=n;j++)
            
                if(a[i-1]==b[j-1])//因为i，j是从1开始的，所以i-1,j-1
                
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                
            
        
        cout<<n-dp[n][n]<<endl;
    
    return 0;

2017腾讯秋招笔试题之编码

Description：  假定一种编码的编码范围是a~y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下：a,aa,aaa,aaaa,aaab,aaac,……,b,ba,baa,baaa,baab,baac……,yyyw,yyyx,yyyy其中a的Index为0，aa的Index为1，aaa的... 查看详情

微软2017校招笔试题2composition

题目AlicewritesanEnglishcompositionwithalengthofNcharacters.However,herteacherrequiresthatMillegalpairsofcharacterscannotbeadjacent,andif‘ab‘cannotbeadjacent,‘ba‘cannotbeadjacenteither.Inordertomeetther 查看详情

微软2017校招笔试题3registrationday

题目It‘sHUniversity‘sRegistrationDayfornewstudents.ThereareMofficesinHUniversity,numberedfrom1toM.Studentsneedtovisitsomeoftheminacertainordertofinishtheirregistrationprocedures.Theofficesareindifferent 查看详情

2018腾讯校招软件开发岗在线笔试题

不定项选择题（20道题）：1.SQL语句中，from，join,where,having,orderby,groupby,limit之间的执行顺序是怎样的？2.innerjoin与leftjoin的执行结果一样吗3.HTTP的返回代码中，200,201,301,307,403,5xx各代表什么含义4.QQ用户有8种状态(在线，忙碌，隐身.... 查看详情

小米2017校招笔试题

只过了20%...我日树的高度 时间限制：C/C++语言1000MS；其他语言3000MS 内存限制：C/C++语言65536KB；其他语言589824KB 题目描述： 现在有一棵合法的二叉树，树的节点都是用数字表示， 现在给定这棵树上所有的父子关系，求这棵树的高... 查看详情

lgyx2017校招笔试题

前言今天通知过了笔试，但总感觉有些笔试没来得及做的题不解决不舒服斯基。题目 大意就是，给你个形如a,b,c,ab,bb,cb,ac,bc,cc,aab,bab,cab,abb,bbb,cbb,acb,bcb,ccb......按某种规律排列的无限长的字符串数组，要求：1）给定一个位置，... 查看详情

网易2017年校招笔试题最大的奇约数

题目：定义函数f(x)为x的最大奇数约数，x为正整数，例如f(44)=11.现在给出一个N,需要求出f(1)+f(2)+f(3)+...+f(N)例如：N=7f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7)=1+1+3+1+5+7=21. 分析：奇数的最大约数是自身，偶数的最大约数是是除去所有偶因子之... 查看详情

笔试题合集

2017网易校招内推笔试题：http://blog.csdn.net/luoshixian099/article/details/52102841携程2017笔试题回忆录：http://blog.csdn.net/miqiong9993/article/details/52565683完美世界2017c++游戏开发：笔试题+面试题：http://blog.csdn.net/zziymt/artic 查看详情

2017腾讯实习笔试题

三道编程题在60分钟内做出来并不容易，加油吧这题做出来容易，但在规定的时间内跑出结果并不容易，参考网友的答案：#include<iostream>#include<string>usingnamespacestd;boolisCap(charc){if(c>=‘A‘&&c<=‘Z‘)returntrue;elseret... 查看详情

腾讯笔试题2017暑期实习-有趣的数字

题目：小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？输入描述:输入包含多组测试数据。对于每组测试数据：N-本组测试数据有n个数a1,a2...an-需要计算的数据保证:1<=N<=100000... 查看详情

tx2017秋招笔试题之素数对

问题描述：给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。如，输入为10,程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）输入描述:输入包括一个整数n,(3... 查看详情

tx2017秋招笔试题之编码

问题描述：假定一种编码的编码范围是a~y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下：a,aa,aaa,aaaa,aaab,aaac,……,b,ba,baa,baaa,baab,baac……,yyyw,yyyx,yyyy其中a的Index为0，aa的Index为1，aaa的Index为2... 查看详情

腾讯2017暑期实习生笔试题(有趣数字)(代码片段)

  之前准备把腾讯实习生招聘的第三道题做出来的，但是时间很紧，最终拖到今天才完成的，下午做了一个小时才弄出来的，主要是细节方面的问题。这个题意思很简单吧，给出很多数，找出“二元组”... 查看详情

2017cvte笔试题

下面是凭记忆整理的2017CVTE校招笔试题，基本上全都是我不会或很模糊的题，为了更好突出重点我以问答题的形式来描述题目。1.中序遍历是属于层次遍历、广度优先遍历、深度优先遍历中的哪一种？　答：层次遍历是指一层一... 查看详情

tx2017秋招笔试题之geohash编码

问题描述：geohash编码：geohash常用于将二维的经纬度转换为字符串，分为两步：第一步是经纬度的二进制编码，第二步是base32转码。此题考察纬度的二进制编码：算法对纬度[-90,90]通过二分法进行无限逼近（取决于所需精度，本... 查看详情

java工程师笔试题整理[校招篇]

Java工程师笔试题整理[校招篇]  隔着两个月即将开始校招了。你是不是也想借着这个机会崭露头角，拿到某些大厂的offer，赢取白富美、走上人生巅峰？当然如果你还没能打下Java基础，一定要先打好Java基础：如何一步一... 查看详情

算法题之端口（2017百度实习笔试题）

端口时间限制：C/C++语言1000MS；其他语言3000MS内存限制：C/C++语言65536KB；其他语言589824KB题目描述：为了节省信息传递的数据量，A公司内部经常用一种简单的压缩方法来处理端口地址。举例：[001011:110011:101101:000000]→[1011:110011:1011... 查看详情

腾讯2017暑期实习生编程题第一题构造回文(代码片段)

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。输入描述:输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.输出描述:对... 查看详情