（答案来了）两道腾讯面试题目

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

第一题

• 题目要求： 假设给定一个由字母和小数点组成的字符串，把字符串按块翻转，其中连续的小数点为一块，连续的字母为一块。例如 '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 ?>