专栏首页aCloudDeveloper腾讯2016春招之算法编程解析

腾讯2016春招之算法编程解析

第一道题:求有删除情况的最长回文子串

题目:

解题思路:

这个题严格意义上来说,删除了字符就谈不上回文串了,既然有删除,那估计考察的不是回文串,而是其他的,但是这个东西又有回文串的特点,细想一下——那就是不连续的回文串,想到不连续,就容易使人想到最长公共子序列,把源字符串逆序之后对比两个字符串发现:我靠,这不就是求两个序列的最长公共子序列(好像跟回文串没多大关系)。

考察:回文串,动态规划,知识迁移

 1 #define M 100
 2 int dpLCS[M][M]; //设置成全局变量,自动初始化为0
 3 
 4 //动态规划法:最长回文子串,有删除,其实就是求最长公共子序列
 5 int LongestCommonSequence(string str)
 6 {
 7     size_t n = str.size();
 8     if (n == 0 || n == 1)
 9         return 1;
10     
11     string s = str;
12     reverse(s.begin(), s.end());
13 
14     for (size_t i = 1; i <= n; ++ i) {
15         for (size_t j = 1; j <= n; ++ j) {
16             if (str[i-1] == s[j-1]) 
17                 dpLCS[i][j] = dpLCS[i-1][j-1] + 1;
18             else 
19                 dpLCS[i][j] = max(dpLCS[i-1][j], dpLCS[i][j-1]); 
20         }
21     }
22     return dpLCS[n][n];
23 }

第二个题:蛇形矩阵,又叫螺旋矩阵

题目:

解题思路:

解螺旋矩阵的切入点需要知道矩阵的个数,看下面一幅图:

如果是n = odd,则中间只有一个数,不算做一个矩阵,如果n = even,则中间是一个矩阵,总的矩阵个数为n/2,知道这一点,后面的工作就是分别从外向里遍历每一个矩阵即可。

 1 void HelixMatrix(int n)
 2 {
 3     int **a = new int *[n];
 4     for (int i = 0; i < n; i ++)
 5         a[i] = new int[n];
 6 
 7     int m = 0;
 8     for (int k = 0; k < n/2; ++ k) { //n/2矩阵个数
 9         for (int i = 0; i <= n-1-k; ++ i)
10             a[k][i] = m++; //第一区块
11         for (int i = k + 1; i < n-1-k; ++ i)
12             a[i][n-1-k] = m++; //第二区块
13         for (int i = n-1-k; i > k; -- i)
14             a[n-1-k][i] = m++; //第三区块
15         for (int i = n-1-k; i > k; -- i)
16             a[i][k] = m ++; //第四区块
17         if (n%2 == 1)
18             a[n/2][n/2] = m; //n=odd,填充中间一个数
19     }
20     for (int i = 0; i < n; i ++) {
21         for (int j = 0; j < n; j ++)
22             cout << a[i][j] << " ";
23         cout << endl;
24     }
25     //释放a
26     for(int i = 0; i < n; i ++) {
27         delete [] a[i];
28     }
29     delete []a;
30 }

附:选择题部分整理

1、HTTP协议的请求类型,端口号,返回码等

2、在同一台机器上,内存访问,SATA硬盘随机访问时间分别是:(几十纳秒,几十毫秒)

3、E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)}的深度优先遍历序列

4、关于操作系统的说法正确的是:

  a、同一个线程内可以运行多个消息队列

  b、Windows中使用临界区,不需要切换到内核态

  c、互斥量可以用于多进程间对资源的安全共享

  d、信号量允许多个线程同时使用共享资源

5、页面采用click事件会存在300ms延时的原因

6、用0-9,a-z表示36进制的873085

7、冒泡排序,堆排序,归并排序,快速排序的时间复杂度

8、http的返回码101,404,502,200的含义

9、面向对象程序设计SOLID五大原则,各字母的含义

10、有关网络协议说法正确的是:   A.UDP是无连接不可靠的,TCP是连接可靠的

  B.HTTP请求的类型有get, post, put, delete,head

  C.HTTP默认端口号为80,HTTPS默认端口号为443,FTP默认端口号为21

  D.根据HTTP规范,GET请求用于信息获取,并且应该是安全的和幂等的

11、两服务器相距1500km,一次ping请求耗时多长(4,8,16,32)

12、文件系统管理的最小磁盘空间单位(扇区,簇)

13、在移动端浏览器,页面采用click事件,会存在300ms的延迟,为什么?(要预先处理一些操作,还有判断是否是双击操作)

14、A和B玩纽扣游戏,一共16个纽扣,两人轮流来取,每人每次可以选取1个或3个或6个(不允许不取),规定谁取完最后的纽扣谁赢。如果让A先取,则A的必胜策略下第一步应该取?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法导论2-9章补充几道题

    本篇博文意在对前几章中遗漏的,本人觉得有意思的习题当独拿出来练练手。 1、习题2-4,求逆序对,时间复杂度要求Θ(nlgn) 定义:对于一个有n个不同的数组A,...

    CloudDeveloper
  • Pascal三角形

    作者:bakari   时间:2012.8.4 Pascal三角形又称杨辉三角形,是多项式系数的一种规律展示,最早是由我国数学家杨辉发现,比Pascal早200...

    CloudDeveloper
  • 算法导论第二章小试牛刀

    Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

    CloudDeveloper
  • 04:最匹配的矩阵

    04:最匹配的矩阵 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个m*n的矩阵A和r*s的矩阵B,其中0 < r ≤ m, 0 < s...

    attack
  • PTA 输出全排列(20 分)

    7-2 输出全排列(20 分) 请编写程序输出前n个正整数的全排列(n<10),并通过9个测试用例(即n从1到9)观察n逐步增大时程序的运行时间。 输入格式: ...

    Kindear
  • codeForces #575 div3

    A - Three Piles of Candies 题意:就是给了三堆糖,两个人,每人哪一堆,然后第三堆用来补充,最终要达到两个人的糖的数量一样多。 思路...

    用户7727433
  • 【CodeForces 699B】One Bomb

    枚举每个位置如果c[i]+r[j]-(本身是不是*)==总*数,则该位置即为答案。

    饶文津
  • Educational Codeforces Round 65 (Rated for Div. 2) A-D

    rank是能够通知到的人的个数,比较当前这两个人谁能通知到的人较少,然后把能通知到的人较少的那个人的指向pre[a]指向b(假设a能通知到的人较少),这样是为了...

    用户2965768
  • PAT(乙级)1005

    卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里,情况稍微有些复杂。

    zy010101
  • 2017百度之星初赛(A)

     假设P进制下有个数(abc)~P~,若这个数满足:(abc)~P~ % B == 0,则以下两个等式一定成立:

    mathor

扫码关注云+社区

领取腾讯云代金券