关于腾讯的那道题截取字符串的题

2024-09-06 15:55:01

开发者中心
> 正文

记得是前阵子去腾讯面试时的那道题，当时用笔我没写出来，就大概说了下思路，今天有空，就写了一下，发现要做到完美还是很麻烦的。

题目是:
假设有"123abc456def789"这么一个字符串,写一个函数，可以传入一个字符串，和一个要截取的长度。返回截取后的结果。

要求:
1 和标记不得计算在长度之内。
2 截取后的字符串，要保留原有标签，不过如果最后有一个标签没有闭合，则去掉其开始标签。

示例:
题中的字符串，要截取长度5，则返回的字符串应该为:123ab,要截取长度8，应返回123abc45。

我的做法大概思路是:
1 首先顺序读取字符串，并用一个resultstr变量来记录所有字符，当发现 2 如果发现tag变量形式为也就是html标签的开始标记)，就将其入栈。用栈结构来存储这个标记。若遇到(html标签的结束标记)，就出栈。

3 否则如果是常规字符的话，长度计数器++。直到与传入的要截取长度相等。

4 最后判断栈是否为空，如果为空，直接返回截取后的字符串，否则，将栈中剩余元素一个个出栈，循环从截取后的字符串中查找栈顶标签元素最后一次出现的位置，返回索引，将这个标签替换为空。直到整个栈为空为止。最后返回处理后的字符串。

原题其实是没有考虑标签嵌套的情况的，我尽量的让程序可以处理嵌套标签，使其更健壮。并且尽量少的去用php的内置函数，因为那样可能会掩盖算法本身。如可以处理a1

b2c3d4

e5
这种形式的嵌套标签。但我发现如果标签是这种不规则形式a1
b2c3d4
e5的话，程序就会出问题了。因为我只将取到的结束标记与栈顶的元素相比较，而没有去循环搜索整个栈。这里要改一下其实也可以。

不知大家还有没有其他思路，我感觉我这么做实在是太麻烦了，罗罗嗦嗦一大堆。这么多代码面试时拿笔写非得疯了不可。而且这个时间复杂度不理想，大概为O(n*(n2))。空间方面也占了很多多余的空间。我相信一定有很简单的办法。希望大家一起想想有什么更简单的方法没？

<?phpfunction mySubstr( $str, $length ){ $tagcnt = 0; $charcnt = 0; $tag = ''; $maxlen = strlen( $str ); $resultstr = ''; $tagstack = array(); for( $i = 0; $i < $length; $i++ ){ if( $str[$i] == '<' ){ $resultstr .= $str[$i]; for( $j=$i; $str[$j]!='>'; $j++,$length++ ){ $tag .= $str[$j]; } $tagcnt++; $length++; $tag .= '>'; //如果是开始标记，则入栈，如果是与之相对应的结束标记则出栈 if( preg_match('/<([^\/]+)?>/i', $tag, $r) ){ echo '入栈:',htmlspecialchars($r[1]),'
'; array_push($tagstack, $r[1]); } elseif( preg_match( '/'.$tagstack[count($tagstack)-1].'/', $tag ) ){ echo '出栈:',htmlspecialchars($tagstack[count($tagstack)-1]),'
'; array_pop( $tagstack ); } $tag = ''; continue; } $charcnt++; $resultstr .= $str[$i]; } echo '
最后结果为:'; //栈是空的直接返回 if(empty($tagstack)){ return $resultstr; } //否则去掉没有结束标记的开始标记 else{ while(!empty($tagstack)){ $tag = array_pop($tagstack); $index = strrpos($resultstr, $tag); for($i = $index-1; $resultstr[$i] != '>'; $i++ ){ $resultstr[$i] = ''; } $resultstr[$i++] = ''; } return $resultstr; } }$sttime = microtime(true);$stmem = memory_get_usage();$str = "a1b2
c3d4e5
f6g7h8";echo '处理结果为:
',htmlspecialchars( mySubstr( $str, 18 ) ),'
';echo "内存使用情况:",(memory_get_usage()-$stmem),'
';echo "算法运行时间(microtime):",(microtime(true)-$sttime),'
';

回复讨论(解决方案)

应该说楼主的代码已经相当不错了

先提几点自己的看法
1、作为试题，考官已有先入为主的答案，任何对题面的深入剖析都可能被认为是画蛇添足。论坛首页上就有这样的报屈帖子
2、从题面入手就是边找html标记边计数（楼主也是这么做的）在到达退出条件时，检查缓存的html标记，因为不考虑嵌套所以处理成偶数个数即可，最后生成返回串。这样的代码量较少，即使不能上机调试，出错的概率也较小
3、作为实用函数，自然要考虑多些了。楼主的代码只考虑了一般性的标记配对，而忽略了html中是允许独立标记

、自封闭标记
等等出现的。而
标记无论嵌套多少层，是否匹配，在浏览器中的表现都是一样的

呵呵，这题有印象

来添砖加瓦

$str = "a1b2
c3d4e5
f6g7h8";$arr = preg_split('/(<[^>]*>)/', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);foreach($arr AS $k => $v){ if(isset($arr[$k+1])) { $temp = $arr[$k][1] + strlen($arr[$k][0]); $arr[$k][2] = substr($str, $temp, $arr[$k+1][1] - $temp); }}print_r($arr);/*经过这么处理后，字符串变成了由html标签 + 这个标签之前的字符组成的元素组成的数组。。如下Array( [0] => Array ( [0] => a1 [1] => 0 [2] => ) ……*/

接下来，遍历，将元素组成一个想要的字符串即可

同时稍加处理，记录，用+1， -1。。。如果<0的，不加入字符串。。如果最终结果>0，则由后往前，替换几次

但是，还有一个问题。。。。。。。没有考虑这种情况

其实这样的话，注释也能考虑进来了

$arr = preg_split('/(<\!--.*-->|<[^>]*>)/s', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);

这个题我上次测过
不好做

ＰＨＰ手上有标签不配对时，自动补全的代码
估计腾讯的人如果没有答案，也够它搞几天的

实际应用中，一些程序有这功能，如网博士的网页选取保存

标签的混合嵌套是不符合xhtml标准的，但单标签闭合是允许的

这个题：

如果只考虑"123abc456def789"这个字符串
问题可以简单很多。

这就是只考一下你的算法

但不具实际应用意义，具有实际应用意的话就是标签不限，不是一下两个能解决的

对于
这种单标签是不受影响的，因为其第一次匹配到时在栈里找不到与之对应的开始标签是不会入栈的。不过对于
这种单标签确实是会出现问题。

呵呵，这题有印象

来添砖加瓦

PHP code

$str = "a1b2
c3d4e5
f6g7h8";
$arr = preg_split('/(<[^>]*>)/', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);
foreach($arr AS $k => $v)
{
i……

哥们你的代码我没看太懂，最后出来的那个数组，字符并不是单独存在于数组每个元素的，如果按照长度来计算出我想要截取到的长度？

我理解为你希望看到的结果是
array
0 => string 'a',
1 => string '1',
2 => string ''
3 => string 'b',
4 => string '2',
...

这样的形式，可以将每一个元素连接起来，取得截取后的字符串

呵呵，打印一下数组结构
比如
$str = "a1b2
c3d4e5
f6g7h8
";
…………

结果如下，，遍历下数组，拼接字符串，应该就可以了。$arr[$i][1]是字符串开始位置，到这一步可以不用理会了
Array
(
[0] => Array
(
[0] => a1
[1] => 0
[2] =>
)

[1] => Array
(
[0] => b2
[1] => 8
[2] =>

)

[2] => Array
(
[0] => c
[1] => 13
[2] =>
)

[3] => Array
(
[0] => 3
[1] => 33
[2] =>
)
……
……

引用 2 楼 amani11 的回复:
呵呵，这题有印象

来添砖加瓦

PHP code

$str = "a1b2
c3d4e5
f6g7h8";
$arr = preg_split('/(<[^>]*>)/', $str, -1, PREG_SPLIT_OFFSET_CAPTURE);
foreach($arr ……
那你理解错了，你最好先看看preg_split
结果是个二维的数组

这样不是更直观些？
$str = "a1b2
c3d4e5
f6g7h8
";$arr = preg_split("/(<\!--.*-->|<[^>]*>)/s", $str, -1, PREG_SPLIT_DELIM_CAPTURE);print_r($arr);

Array
(
[0] => a1
[1] =>
[2] => b2
[3] =>

[4] => c
[5] =>
[6] => 3
[7] =>
[8] => d4
[9] =>
[10] => e5
[11] =>

[12] => f6
[13] =>
[14] => g7h8
[15] =>

[16] =>
)

引用 9 楼 shadowsniper 的回复:

引用 2 楼 amani11 的回复:
呵呵，这题有印象

来添砖加瓦

PHP code

$str = "a1b2
c3d4e5
f6g7h8";
$arr = preg_split('/(<[^>]*>)/', $str, -1, PREG_SPLIT_OFFSET_……

明白了，如果是这样就可以将二维数组的元素连接起来了。不过最后还是要处理掉不匹配的标签。

写了个简单的，欢迎拍砖
/** * 函数名 html_substr * 功能从html串中截取指定长度的字串，html标记不计算在内 * 参数 * $str 要截取的串 * $len 要截取的长度 * $mode 不匹配的标记的处理方式 0 删去(默认)，1 补齐 * 返回截取到的串 * 说明 * 未考虑多字节字符，仅已字节做计数单位 * 未考虑可单独存在的标记 **/function html_substr($str, $len, $mode=0) { $ar= preg_split('/(<\!--.*-->|<[^>]*>)/s', $str, -1, PREG_SPLIT_DELIM_CAPTURE); foreach($ar AS $k => $v) { if($v{0} != '<') { $len = $len - strlen($v); if($len < 0) $ar[$k] = substr($v, 0, $len); }else $ar[$k] = strtolower($v); if($len <= 0) break; } $ar = array_slice($ar, 0, $k+1); $len = count($ar); foreach($ar as $k=>$v) { if($v{0} == '<' && $v[1] != '/') { $ch = str_replace('<', 'abc456def789";echo '