腾讯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的必胜策略下第一步应该取?

目录
相关文章
|
4月前
|
存储 算法 安全
如何控制上网行为——基于 C# 实现布隆过滤器算法的上网行为管控策略研究与实践解析
在数字化办公生态系统中,企业对员工网络行为的精细化管理已成为保障网络安全、提升组织效能的核心命题。如何在有效防范恶意网站访问、数据泄露风险的同时,避免过度管控对正常业务运作的负面影响,构成了企业网络安全领域的重要研究方向。在此背景下,数据结构与算法作为底层技术支撑,其重要性愈发凸显。本文将以布隆过滤器算法为研究对象,基于 C# 编程语言开展理论分析与工程实践,系统探讨该算法在企业上网行为管理中的应用范式。
122 8
|
4月前
|
存储 监控 算法
解析公司屏幕监控软件中 C# 字典算法的数据管理效能与优化策略
数字化办公的时代背景下,企业为维护信息安全并提升管理效能,公司屏幕监控软件的应用日益普及。此软件犹如企业网络的 “数字卫士”,持续记录员工电脑屏幕的操作动态。然而,伴随数据量的持续增长,如何高效管理这些监控数据成为关键议题。C# 中的字典(Dictionary)数据结构,以其独特的键值对存储模式和高效的操作性能,为公司屏幕监控软件的数据管理提供了有力支持。下文将深入探究其原理与应用。
83 4
|
5月前
|
机器学习/深度学习 监控 算法
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
108 2
|
7月前
|
存储 算法 安全
.NET 平台 SM2 国密算法 License 证书生成深度解析
授权证书文件的后缀通常取决于其编码格式和具体用途。本文档通过一个示例程序展示了如何在 .NET 平台上使用国密 SM2 算法生成和验证许可证(License)文件。该示例不仅详细演示了 SM2 国密算法的实际应用场景,还提供了关于如何高效处理大规模许可证文件生成任务的技术参考。通过对不同并发策略的性能测试,开发者可以更好地理解如何优化许可证生成流程,以满足高并发和大数据量的需求。 希望这段描述更清晰地传达了程序的功能和技术亮点。
643 14
.NET 平台 SM2 国密算法 License 证书生成深度解析
|
4月前
|
存储 监控 算法
内网监控桌面与 PHP 哈希算法:从数据追踪到行为审计的技术解析
本文探讨了内网监控桌面系统的技术需求与数据结构选型,重点分析了哈希算法在企业内网安全管理中的应用。通过PHP语言实现的SHA-256算法,可有效支持软件准入控制、数据传输审计及操作日志存证等功能。文章还介绍了性能优化策略(如分块哈希计算和并行处理)与安全增强措施(如盐值强化和动态更新),并展望了哈希算法在图像处理、网络流量分析等领域的扩展应用。最终强调了构建完整内网安全闭环的重要性,为企业数字资产保护提供技术支撑。
118 2
|
6月前
|
人工智能 算法 语音技术
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
清华大学与腾讯联合推出的Video-T1技术,通过测试时扩展(TTS)和Tree-of-Frames方法,显著提升视频生成的连贯性与文本匹配度,为影视制作、游戏开发等领域带来突破性解决方案。
175 4
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
|
5月前
|
存储 监控 算法
员工电脑监控场景下 Python 红黑树算法的深度解析
在当代企业管理范式中,员工电脑监控业已成为一种广泛采用的策略性手段,其核心目标在于维护企业信息安全、提升工作效能并确保合规性。借助对员工电脑操作的实时监测机制,企业能够敏锐洞察潜在风险,诸如数据泄露、恶意软件侵袭等威胁。而员工电脑监控系统的高效运作,高度依赖于底层的数据结构与算法架构。本文旨在深入探究红黑树(Red - Black Tree)这一数据结构在员工电脑监控领域的应用,并通过 Python 代码实例详尽阐释其实现机制。
100 7
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
99 4
|
5月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
91 0
|
6月前
|
监控 算法 安全
基于 C# 的内网行为管理软件入侵检测算法解析
当下数字化办公环境中,内网行为管理软件已成为企业维护网络安全、提高办公效率的关键工具。它宛如一位恪尽职守的网络守护者,持续监控内网中的各类活动,以确保数据安全及网络稳定。在其诸多功能实现的背后,先进的数据结构与算法发挥着至关重要的作用。本文将深入探究一种应用于内网行为管理软件的 C# 算法 —— 基于二叉搜索树的入侵检测算法,并借助具体代码例程予以解析。
95 4

热门文章

最新文章

推荐镜像

更多
  • DNS