开发笔记:程序员面试修炼01|腾讯2017笔试题

篇首语：本文由编程笔记#小编为大家整理，主要介绍了程序员面试修炼01 | 腾讯2017笔试题相关的知识，希望对你有一定的参考价值。

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子:

abcda 
google

输出例子:

2 
2

解题思路

本题可以转换为求该字符串与其反序字符串的最长公共子序列问题，即利用LCS算法求解。

例如：abcda的反序字符串为adcba，最长公共子序列为aba，其公共子序列必为回文序列，然后可求出最少删除多少个字节使其成为回文字符串。

本题采用动态规划来求解问题，下面看看模拟的推导过程。

状态转移方程为：(令A为输入字符串，B为其反序字符串，num[][]记录当前最长公共子序列的长度) 

if&＃x3000;(A[i]==B[j])&＃x3000;num[i][j]=num[i&＃x2212;1][j&＃x2212;1]+1" role="presentation">
if　(A[i]==B[j])　

num[i][j]=num[i−1][j−1]+1

i


f



　



(


A


[


i


]


==


B


[


j


]


)



　



n


u


m


[


i


]


[


j


]


=


n


u


m


[


i


−


1


]


[


j


−


1


]


+


1

else　

num[i][j]=max(num[i−1][j], num[i][j-1])

下面来看解题代码（如果代码页面超出可以左右上下移动）：

#include
#include <iostream>
#include
#include
#include
using namespace std;
int main(){    
   string s;    
   while(cin>>s){        
       int len = s.length();        
       int maxlen = 0;        
       vector<vector<int> > Vec;      
        for(int i = 0 ; i 1 ; i++){          
           vector<int> temp(len+1,0);
           Vec.push_back(temp);
       }        
       for(int i = 1; i1 ; i++){            
            for(int j = 1 ; j 1;j++){                
                if(s[i-1]==s[len-j]){
                   Vec[i][j] = Vec[i-1][j-1]+1;
               }                
                else {
                   Vec[i][j] = max(Vec[i-1][j],Vec[i][j-1]);
               }
           }
       }        
        cout<    }
}

刚刚考完腾讯笔试的不要灰心，全力刷题，备战下一次的笔试以及面试。