Heim > Artikel > Backend-Entwicklung > 关于腾讯的那道题截取字符串的题

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

WBOYOriginal: 2016-06-23 14:03:392144Durchsuche

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

题目是:
假设有"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 '<hr size=1>最后结果为:'; //栈是空的直接返回 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 = "a1<body>b2c3d4e5f6</body>g7h8";echo '处理结果为: <hr size=1>',htmlspecialchars( mySubstr( $str, 18 ) ),' ';echo "内存使用情况:",(memory_get_usage()-$stmem),' ';echo "算法运行时间(microtime):",(microtime(true)-$sttime),' ';

回复讨论(解决方案)

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

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

、自封闭标记
等等出现的。而

标记无论嵌套多少层，是否匹配，在浏览器中的表现都是一样的

呵呵，这题有印象

来添砖加瓦

$str = "a1<body>b2<p>c3<em>d4</em>e5</p>f6</body>g7h8";$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] => <body>         ) ……*/

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

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

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

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

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

这个题我上次测过
不好做

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

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

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

这个题：

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

这就是只考一下你的算法

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

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

呵呵，这题有印象

来添砖加瓦

PHP code

$str = "a1

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 = "a1

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 = "a1

c3d4e5

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

这样不是更直观些？

$str = "a1<body>b2<p>c<!--</em>123<em>-->3<em>d4</em>e5</p>f6</body>g7h8<br />";$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 = "a1

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('<', '</', $v);      for($i=$k+1; $i<$len && $ar[$i]!=$ch; $i++);      if($i == $len)        if($mode)          $ar[$len] = $ch . $ar[$len];        else          $ar[$k] = '';    }  }  return join('', $ar);}$str = "123<em>abc</em>456<em>def</em>789";echo '<xmp>';echo html_substr($str, 5) . PHP_EOL;echo html_substr($str, 5, 1);

123ab
123ab

学习了，高手都在啊。

唠叨老大写的这个很简洁，满足题意是绝对没问题了。但是如果再多考虑一些。假如这个字符串很长，1000个字节。而我只截取10个字符。

用preg_split将整个字符串按标签分组的话，正则解析器会搜索整个字符串。做了很多多余的搜索。

$str = "a1<body>b2c3<p><em>d4</em>e</p>5f6</body>g7h8";$gn  = 7;$i   = $j = $k = 0;while( ($c = $str[$i++]) && $j < $gn ) {	if( $c == '<')	{		$tag = 1;	}	elseif($c == '>')	{		if(trim($tg,'/') == 'em')		{			$tgs[$j-1] = '<'.$tg.'>';		}		else 		{			if($tgs[$j-1]) $ogs[$j-1] = '1|'.'<'.$tg.'>';			else $ogs[$j-1] 		  = '0|'.'<'.$tg.'>';		}		$tag = 0;		$tg  = '';	}	elseif($tag == 1)	{		$tg .= $c;	}	else	{		$tmp[] = $c;		$j++;	}}$ts = count($tgs);if($ts % 2) array_pop($tgs);foreach($tmp as $k=>$v){   $ba = explode('|',$ogs[$k],2);   if( $tgs[$k] && $ogs[$k])   {		if($ba[0])		{			$s .= $v.$tgs[$k].$ba[1];		}			else $s .= $v.$ba[1].$tgs[$k];   }   else $s .= $v.$tgs[$k].$ba[1];}echo htmlspecialchars($s);

不会做了。123abc456def789
一定要做的话，只会：
对标签作为分割符，对其视而不见，将第一段字符存贮为$a1;即$a1=123;第二断为$a2,$a2=abc;一直到$a.$i;
总之就是一段一段的
$a1.$2.$a3.$a4.……
然后算字符，当第一段字符不够，接着取下一段。一直到够为止。

最后写条件加标签。
123奇abc偶456奇def偶789,$a1奇$a2偶$a3奇$a4偶$a5
奇偶条件。截取的如果奇偶对满，加标签，如果不满，就不加。

我做题的思路和楼主不太一样。
首先楼主直接把这个问题中的标签由 em 升级到通用性的 html 标签了，我觉得这种抽象的思维是一种好习惯，但针对如题的面试，我会就按如题所说，只对em 进行解析，完成第一版的原型，复杂的事情，以后时间多了慢慢的思考。

也写点代码，
我的思路是希望通过数据结构来处理这个问题，少依赖正则表达式。
例如
123abc456def789
的数据结构为
tagInfo =>array(
1 start 3, end 6
2 start 9, end 12
) 用于记录标签的位置
和stripStr = "123abc456def789"; 用来存取相应的去掉标签的字符串
这样一来，得到目标字符串，就成了在这个数据结构上去merge 最终字符串的一种算法了。
代码可以使用，在此我更多的是想表达一种思路，代码中有很多需要完善的地方，感谢大家指正，

$str = "123<em>abc</em>456<em>def</em>789";$str1 = mysub($str,5);/************************the result is 123bc************************/$str2 = mysub($str,10);/************************the result is 123<em>abc</em>456d************************//** * * * * @param string $str * @param int $len * @return str 目标字符串 */function mysub($str,$len = 8){	$str = "123<em>abc</em>456<em>def</em>789";	$parseStr = getTag($str,"em");  //将字符串中的em 进行解析，得到所在的开始位置和结束位置.		//得到当前指定位置所在的游标.	$cur = -1;	foreach($parseStr as $key=>$val)	{		if($len >= $val["end"])		{			$cur = $key;		}	}	$dest_str = substr(strip_tags($str),0,$len);	    $dest_str = merge_str($dest_str,$cur,$parseStr);  //得到拼接出来的目标字符串        return $dest_str; }//生成最终数据function merge_str($dest_str,$cur,$parseStr){  for($i=0;$i<strlen($dest_str);$i++)  {  	$str_arr[$i] =substr($dest_str,$i,1);  }  foreach($parseStr as $key=>$val)  {  	if($cur >= $key)  	{  		echo $val["start"];  		$str_arr[ $val["start"] ] = "<em>".$str_arr[ $val["start"] ];  		$str_arr[ $val["end"]-1 ] .= "</em>";  		  	}  }     $str_out= implode("",$str_arr);   echo $str_out;  	}/** * 解析字符串中em 的 start end 位置. * */function getTag($str,$tagName = "em"){	preg_match_all("/<$tagName>(.*)<\/$tagName>/iU",$str,$matches);	$tagArr = $matches[1];  //将em 标签的内容放入tagArr数组。		//获取相应的起始位置.	foreach ($tagArr as $key=>$val)	{		$resultArr[$key]["val"] = $val;		$resultArr[$key]["start"] = handel_getstart($str,$val,$key);		$resultArr[$key]["end"] = handel_getend($str,$val,$key);	}	return $resultArr;	}//获取开始位置function handel_getstart($str,$val,$key){	return strripos($str,$val)- $key*9-4;    //这里写得比较随意,可能问题很多，todo : 要防止重复字符串时取位错误.}//获取结束位置function handel_getend($str,$val,$key){	return handel_getstart($str,$val,$key)+strlen($val);}

唠叨老大写的这个很简洁，满足题意是绝对没问题了。但是如果再多考虑一些。假如这个字符串很长，1000个字节。而我只截取10个字符。

用preg_split将整个字符串按标签分组的话，正则解析器会搜索整个字符串。做了很多多余的搜索。
的确如此！
不过可以考虑只取一部分（比如待截取的长度*5）来做分析

是否使用正则表达式去分割字符串，是可商榷的。这取决于 memory_limit 的值
早期的php默认 memory_limit = 8M
这样的话，用正则表达式切割字符串远没有自己写一个函数来的快
现在的php默认 memory_limit = 128M
我测试了一下，还是正则来的快，所以就用了正则。毕竟看起来简洁多了

唠叨老大写的这个很简洁，满足题意是绝对没问题了。但是如果再多考虑一些。假如这个字符串很长，1000个字节。而我只截取10个字符。

用preg_split将整个字符串按标签分组的话，正则解析器会搜索整个字符串。做了很多多余的搜索。

我觉得在不考虑递归的情况下。
取字符串时可以预处理一下。
例如取前10 个，
最极端的情况下，字符串长度为
1234567890
那么先把字段直接取前100个，使用唠叨老大的代码处理。。。

有点错，更正一下

为了便于测试，我仿你的思路写了个测试函数

/** * 函数名 check_speed * 功能 统计运行时间和内存使用情况 * 参数 $num 大于0 开始计时，等于0或缺省 停止计时并输出结果 * 说明 本函数可以以 check_speed(运行次数, 函数名, 参数列表); *      方式调用。输出的结果是平均每次的耗时 **/function check_speed($num=0) {  static $time;  static $memo;  $argc = func_num_args();  $param = func_get_args();  switch($argc) {    case 1:      $time = microtime(true);      $memo = memory_get_usage();      break;    default:      $time = microtime(true);      $memo = memory_get_usage();      $len = array_shift($param);      $func = array_shift($param);      for($i = 0; $i<$len; $i++)        call_user_func_array($func, $param);      echo '<br />' . PHP_EOL . $func;    case 0:      $len or $len = 1;      echo '<br />' . PHP_EOL;      printf("时间: %s 微秒<br />%s", number_format((microtime(true) - $time)*1000000/$len), PHP_EOL);      printf("内存: %d<br />%s", memory_get_usage()-$memo, PHP_EOL);  }}

对你我的代码做了一下测试
check_speed(100, 'html_substr', $str, 5);
check_speed(100, 'mySubstr', $str, 5); //注：已注释掉影响速度的 echo 语句

结果如下：

html_substr
时间: 42 微秒
内存: 3416

mySubstr
时间: 85 微秒
内存: 3864

学习了！

我这里有啊....

http://hi.baidu.com/lael80/blog/item/669ebe1e50f635134134172c.html

//tags : 字符串可能包含的HTML标签//zhfw : 用来修正中英字宽参数function wsubstr($str, $length = 0, $suffixStr = "...", $start = 0, $tags = "div|span|p", $zhfw = 0.9, $charset = "utf-8"){//author: lael//blog: http://hi.baidu.com/lael80$re['utf-8']   = "/[\x01-\x7f]|[\xc2-\xdf][\x80-\xbf]|[\xe0-\xef][\x80-\xbf]{2}|[\xf0-\xff][\x80-\xbf]{3}/";$re['gb2312'] = "/[\x01-\x7f]|[\xb0-\xf7][\xa0-\xfe]/";$re['gbk']    = "/[\x01-\x7f]|[\x81-\xfe][\x40-\xfe]/";$re['big5']   = "/[\x01-\x7f]|[\x81-\xfe]([\x40-\x7e]|\xa1-\xfe])/";$zhre['utf-8']   = "/[\xc2-\xdf][\x80-\xbf]|[\xe0-\xef][\x80-\xbf]{2}|[\xf0-\xff][\x80-\xbf]{3}/";$zhre['gb2312'] = "/[\xb0-\xf7][\xa0-\xfe]/";$zhre['gbk']    = "/[\x81-\xfe][\x40-\xfe]/";$zhre['big5']   = "/[\x81-\xfe]([\x40-\x7e]|\xa1-\xfe])/";//下面代码还可以应用到关键字加亮、加链接等，可以避免截断HTML标签发生//得到标签位置$tpos = array();preg_match_all("/<(".$tags.")([\s\S]*?)>|<\/(".$tags.")>/ism", $str, $match);$mpos = 0;for($j = 0; $j < count($match[0]); $j ++){$mpos = strpos($str, $match[0][$j], $mpos);$tpos[$mpos] = $match[0][$j];$mpos += strlen($match[0][$j]);}ksort($tpos);//根据标签位置解析整个字符$sarr = array();$bpos = 0;$epos = 0;foreach($tpos as $k => $v){$temp = substr($str, $bpos, $k - $epos);if(!empty($temp))array_push($sarr, $temp);array_push($sarr, $v);$bpos = ($k + strlen($v));$epos = $k + strlen($v);}$temp = substr($str, $bpos);if(!empty($temp))array_push($sarr, $temp);//忽略标签截取字符串$bpos = $start;$epos = $length;for($i = 0; $i < count($sarr); $i ++){if(preg_match("/^<([\s\S]*?)>$/i", $sarr[$i]))continue;//忽略标签preg_match_all($re[$charset], $sarr[$i], $match);for($j = $bpos; $j < min($epos, count($match[0])); $j ++){if(preg_match($zhre[$charset], $match[0][$j]))$epos -= $zhfw;//计算中文字符}$sarr[$i] = "";for($j = $bpos; $j < min($epos, count($match[0])); $j ++){//截取字符$sarr[$i] .= $match[0][$j];}$bpos -= count($match[0]);$bpos = max(0, $bpos);$epos -= count($match[0]);$epos = round($epos);}//返回结果$slice = join("", $sarr);//自己可以加个清除空html标签的东东if($slice != $str)return $slice.$suffixStr;return $slice;}

preg_split 原来有这函数...

腾讯居然这么干啊，真是服了

看看！

路过,路过,学习

#25 代码有误，已更正

good thing

全是高手啊、

用数据结构来考虑这道题
struct Node_t
{
    char *pdata;//动态申请内存保存字符串，也可以直接指向源字符串地址,不包含
    int nLen;//字符串长度，不包含
}

struct Node
{
    int flag;//统计不匹配情况，为0时表示完全匹配，开始下一个layer
    Node_t *p_next;//下一个嵌套节点
    Node *p_next_layer;//下一个完整节点开始
}

如上结构，如果遇到不匹配的情况，flag＋＋，同时开始新的嵌套节点，当flag为0时，开始新的node。到达指定长度后，根据节点重构字符串，如果该node的flag为0，每个node_t的字符串都要加上,如果不为0，则都不加上。

重构步骤，根据实际需求确定。

要把各种情况都考虑到就比较困难。

每天回帖即可获得10分可用分！

如果原串符合xml标准，根本不用考虑标签里的内容是什么，只要用栈进去就可以了，2n的时间复杂度

我只会用c c++做这个

世界性难题啊

如果原串符合xml标准，根本不用考虑标签里的内容是什么，只要用栈进去就可以了，2n的时间复杂度
如果原串标签不规范，主要的开销在于标签字符串匹配上面，那么时间复杂度最坏可到 2n+2*标签长度L*标签数量C。这样程序比较复杂，不是一下能搞定的，我写过HTML解析的初期版，花了一天时间，后来零碎的调试也差不多有天把时间修正BUG，因为总是有一些意外没有考虑到。

学习。。。

看看！

学习。。。

Stellungnahme：

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Vorheriger Artikel：求个对数据库增删改查的类Nächster Artikel：php 简单的cookie问题～～

In Verbindung stehende Artikel

Mehr sehen