(答案来了)两道腾讯面试题目

前天推送的文章《两道腾讯技术面试题(二面经历)》,收到了不少留言,感兴趣的可以去哪篇文章下查看精选留言,有一多半同学没有正确理解题目,可分享的留言寥寥无几,根据留言我实现了一套方案。

第一题

  • 题目要求: 假设给定一个由字母和小数点组成的字符串,把字符串按块翻转,其中连续的小数点为一块,连续的字母为一块。例如 'ab..bc...cd.' 翻转后为 '.cd...bc..ab'。
  • 思路: 分为两步,先分块,后翻转
  • 代码实现: <?php // 把此字符串分块后倒序输出, 连续'点'为一块,连续'非点'为一块 function change($a) { // 分块后存入数组 $b = []; $j = 0; $b[$j] = $a[0]; $i = 1; while ($a[$i]){ $is_dot_i_1 = $a[$i-1] <> '.'; $is_dot_i = $a[$i] <> '.'; // 和前一个元素对比是否同一块 if ($is_dot_i_1 <> $is_dot_i) { $j ++; $b[$j] = $a[$i]; } else { $b[$j] .= $a[$i]; } $i ++; } $r = ''; // 倒序遍历分库数组 for($k=count($b)-1;$k>=0;$k--) { $r .= $b[$k]; } return $r; }?>
  • 测试结果 <?php $a = 'aa.b...c..d..abd...'; $r = change($a);echo $r,"\n"; // 输出 ...abd..d..c...b.aa ?>

第二题

  • 题目要求: 对于一个只有0和1的二维矩阵,上下或者左右相邻元素都为1则为一块,求一共有多少取值为1的连续块。 例如下图所示矩阵一共有4个取值为1的连续块(虚线框)。
  • 思路:
    1. 以php二维数组方式来标示矩阵,遍历每个元素
    2. 对取值为1的元素以及其所有取值为1的相邻元素的值设置为0
    3. 对每个相邻元素都递归执行第2步
  • 代码实现: <?php // 设置相邻等于1元素为0,并递归调用自身 function reset_1_to_0(&$a, $k1, $k2, $first = true) { if ($k1==count($a) && $k2 == count($a[0])) return; if (!$first && $k1-1 >= 0 && $a[$k1-1][$k2]==1) { $a[$k1-1][$k2] = 0; reset_1_to_0($a, $k1-1, $k2, false); } if (!$first && ($k2-1 >= 0) && $a[$k1][$k2-1]==1) { $a[$k1][$k2-1] = 0; reset_1_to_0($a, $k1, $k2-1, false); } if ($k1+1 < count($a) && $a[$k1+1][$k2]==1) { $a[$k1+1][$k2] = 0; reset_1_to_0($a, $k1+1, $k2, false); } if ($k2+1 < count($a[$k1]) && $a[$k1][$k2+1]==1) { $a[$k1][$k2+1] = 0; reset_1_to_0($a, $k1, $k2+1, false); } } function count_block($a) { $c = 0; for($k1=0;$k1<count($a);$k1++) { for($k2=0;$k2<count($a[$k1]);$k2++) { if ($a[$k1][$k2] == 1) { reset_1_to_0($a, $k1, $k2); $c ++; } } } return $c; }?>
  • 测试结果 <?php $a = [ [0,1,1,0,0,1], [1,0,1,0,0,1], [0,0,1,0,1,1], ]; $c = count_block($a); echo $c,"\n"; // 输出3 ?>

原文发布于微信公众号 - nginx(nginx-study)

原文发表时间:2018-04-26

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

字符串提取函数

今天要跟大家分享三个excel中使用频率最高的字符串提取函数——left/right/mid函数。 ▽▼▽ 这三个函数分别对用截取某一单元格文本的左、右、中间某...

3595
来自专栏数据结构与算法

洛谷P1730 最小密度路径(floyd)

很显然的一个dp方程\(f[i][j][k][l]\)表示从\(i\)到\(j\)经过了\(k\)条边的最小权值

973
来自专栏小红豆的数据分析

小蛇学python(18)pandas的数据聚合与分组计算

对数据集进行分组并对各组应用一个函数,这是数据分析工作的重要环节。在将数据集准备好之后,通常的任务就是计算分组统计或生成透视表。pandas提供了一个高效的gr...

2752
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

43710
来自专栏nummy

Uninformed search Python实现【译】

图的搜索可以分为uninformed搜索和informed搜索,两者的区别是前者是的搜索是盲目的,它不知道目标节点在哪,而后者是启发式的搜索。

1122
来自专栏数据结构与算法

1265. [NOIP2012] 同余方程

1265. [NOIP2012] 同余方程 ★☆   输入文件:mod.in   输出文件:mod.out 简单对比 时间限制:1 s   内存限制:128 M...

3436
来自专栏机器学习算法与Python学习

Numpy

Numpy Numpy是Python中用于科学计算的核心库。它提供了高性能的多维数组对象,以及相关工具。(本文文末的原文链接为numpy的官方文档) NumPy...

3497
来自专栏C/C++基础

迷宫问题(maze problem)——深度优先(DFS)与广度优先搜索(BFS)求解

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

1.6K1
来自专栏C/C++基础

认识UML类关系——依赖、关联、聚合、组合、泛化

在学习面向对象设计时,类关系涉及依赖、关联、聚合、组合和泛化这五种关系,耦合度依次递增。关于耦合度,可以简单地理解为当一个类发生变更时,对其他类造成的影响程度,...

1392
来自专栏逆向技术

逆向课程第五讲逆向中的优化方式,除法原理,以及除法优化下

        逆向课程第五讲逆向中的优化方式,除法原理,以及除法优化下 一丶除法的优化 1.有符号被除数 / 无符号除数的情况下 高级代码为: ? 汇编中优化...

2205

扫码关注云+社区

领取腾讯云代金券