记得是前阵子去腾讯面试时的那道题,当时用笔我没写出来,就大概说了下思路,今天有空,就写了一下,发现要做到完美还是很麻烦的。
题目是:
假设有"123<em>abc</em>456<em>def</em>789"这么一个字符串,写一个函数,可以传入一个字符串,和一个要截取的长度。返回截取后的结果。要求:
1 <em>和</em>标记不得计算在长度之内。
2 截取后的字符串,要保留原有<em>标签,不过如果最后有一个标签没有闭合,则去掉其开始标签。示例:
题中的字符串,要截取长度5,则返回的字符串应该为:123ab,要截取长度8,应返回123<em>abc</em>45。我的做法大概思路是:
1 首先顺序读取字符串,并用一个resultstr变量来记录所有字符,当发现<标记时,开始将这个子字符串用tag变量记录下来。
2 如果发现tag变量形式为<\w+>也就是html标签的开始标记),就将其入栈。用栈结构来存储这个标记。若遇到<\/\w+>(html标签的结束标记),就出栈。3 否则如果是常规字符的话,长度计数器++。直到与传入的要截取长度相等。4 最后判断栈是否为空,如果为空,直接返回截取后的字符串,否则,将栈中剩余元素一个个出栈,循环从截取后的字符串中查找栈顶标签元素最后一次出现的位置,返回索引,将这个标签替换为空。直到整个栈为空为止。最后返回处理后的字符串。原题其实是没有考虑标签嵌套的情况的,我尽量的让程序可以处理嵌套标签,使其更健壮。并且尽量少的去用php的内置函数,因为那样可能会掩盖算法本身。如可以处理a1<p>b2<em>c3</em>d4</p>e5
这种形式的嵌套标签。但我发现如果标签是这种不规则形式a1<p>b2<em>c3d4</p>e5的话,程序就会出问题了。因为我只将取到的结束标记与栈顶的元素相比较,而没有去循环搜索整个栈。这里要改一下其实也可以。
不知大家还有没有其他思路,我感觉我这么做实在是太麻烦了,罗罗嗦嗦一大堆。这么多代码面试时拿笔写非得疯了不可。而且这个时间复杂度不理想,大概为O(n*(n2))。空间方面也占了很多多余的空间。我相信一定有很简单的办法。希望大家一起想想有什么更简单的方法没?
<?php
function 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]),'<br />';
array_push($tagstack, $r[1]);
}
elseif( preg_match( '/'.$tagstack[count($tagstack)-1].'/', $tag ) ){
echo '出栈:',htmlspecialchars($tagstack[count($tagstack)-1]),'<br />';
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>b2<p>c3<em>d4</em>e5</p>f6</body>g7h8";echo '处理结果为:<br/><hr size=1>',htmlspecialchars( mySubstr( $str, 18 ) ),'<br />';echo "内存使用情况:",(memory_get_usage()-$stmem),'<br />';echo "算法运行时间(microtime):",(microtime(true)-$sttime),'<br/>';
题目是:
假设有"123<em>abc</em>456<em>def</em>789"这么一个字符串,写一个函数,可以传入一个字符串,和一个要截取的长度。返回截取后的结果。要求:
1 <em>和</em>标记不得计算在长度之内。
2 截取后的字符串,要保留原有<em>标签,不过如果最后有一个标签没有闭合,则去掉其开始标签。示例:
题中的字符串,要截取长度5,则返回的字符串应该为:123ab,要截取长度8,应返回123<em>abc</em>45。我的做法大概思路是:
1 首先顺序读取字符串,并用一个resultstr变量来记录所有字符,当发现<标记时,开始将这个子字符串用tag变量记录下来。
2 如果发现tag变量形式为<\w+>也就是html标签的开始标记),就将其入栈。用栈结构来存储这个标记。若遇到<\/\w+>(html标签的结束标记),就出栈。3 否则如果是常规字符的话,长度计数器++。直到与传入的要截取长度相等。4 最后判断栈是否为空,如果为空,直接返回截取后的字符串,否则,将栈中剩余元素一个个出栈,循环从截取后的字符串中查找栈顶标签元素最后一次出现的位置,返回索引,将这个标签替换为空。直到整个栈为空为止。最后返回处理后的字符串。原题其实是没有考虑标签嵌套的情况的,我尽量的让程序可以处理嵌套标签,使其更健壮。并且尽量少的去用php的内置函数,因为那样可能会掩盖算法本身。如可以处理a1<p>b2<em>c3</em>d4</p>e5
这种形式的嵌套标签。但我发现如果标签是这种不规则形式a1<p>b2<em>c3d4</p>e5的话,程序就会出问题了。因为我只将取到的结束标记与栈顶的元素相比较,而没有去循环搜索整个栈。这里要改一下其实也可以。
不知大家还有没有其他思路,我感觉我这么做实在是太麻烦了,罗罗嗦嗦一大堆。这么多代码面试时拿笔写非得疯了不可。而且这个时间复杂度不理想,大概为O(n*(n2))。空间方面也占了很多多余的空间。我相信一定有很简单的办法。希望大家一起想想有什么更简单的方法没?
<?php
function 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]),'<br />';
array_push($tagstack, $r[1]);
}
elseif( preg_match( '/'.$tagstack[count($tagstack)-1].'/', $tag ) ){
echo '出栈:',htmlspecialchars($tagstack[count($tagstack)-1]),'<br />';
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>b2<p>c3<em>d4</em>e5</p>f6</body>g7h8";echo '处理结果为:<br/><hr size=1>',htmlspecialchars( mySubstr( $str, 18 ) ),'<br />';echo "内存使用情况:",(memory_get_usage()-$stmem),'<br />';echo "算法运行时间(microtime):",(microtime(true)-$sttime),'<br/>';
$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>
)
……
*/
接下来,遍历,将元素组成一个想要的字符串即可同时稍加处理,记录<em></em>,用+1, -1如果<0的</em>,不加入字符串。。如果最终结果>0,则由后往前,替换几次<em>
但是,还有一个问题。没有考虑<!----</em><em>---->这种情况
不好做PHP手上有标签不配对时,自动补全的代码
估计腾讯的人如果没有答案,也够它搞几天的实际应用中,一些程序有这功能,如网博士的网页选取保存标签的混合嵌套是不符合xhtml标准的,但单标签闭合是允许的
问题可以简单很多。
这就是只考一下你的算法但不具实际应用意义,具有实际应用意的话就是标签不限,不是一下两个能解决的
哥们你的代码我没看太懂,最后出来的那个数组,字符并不是单独存在于数组每个元素的,如果按照长度来计算出我想要截取到的长度?我理解为你希望看到的结果是
array
0 => string 'a',
1 => string '1',
2 => string '<body>'
3 => string 'b',
4 => string '2',
...
这样的形式,可以将每一个元素连接起来,取得截取后的字符串
比如
$str = "a1<body>b2<p>c<!--</em>123<em>-->3<em>d4</em>e5</p>f6</body>g7h8<br />";
…………结果如下,,遍历下数组,拼接字符串,应该就可以了。$arr[$i][1]是字符串开始位置,到这一步可以不用理会了
Array
(
[0] => Array
(
[0] => a1
[1] => 0
[2] => <body>
)
[1] => Array
(
[0] => b2
[1] => 8
[2] => <p>
)
[2] => Array
(
[0] => c
[1] => 13
[2] => <!--</em>123<em>-->
)
[3] => Array
(
[0] => 3
[1] => 33
[2] => <em>
)
……
……
结果是个二维的数组
$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] => <body>
[2] => b2
[3] => <p>
[4] => c
[5] => <!--</em>123<em>-->
[6] => 3
[7] => <em>
[8] => d4
[9] => </em>
[10] => e5
[11] => </p>
[12] => f6
[13] => </body>
[14] => g7h8
[15] => <br />
[16] =>
)
* 函数名 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
123<em>ab</em>
$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);
一定要做的话,只会:
对标签作为分割符,对其视而不见,将第一段字符存贮为$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 进行解析,完成第一版的原型,复杂的事情,以后时间多了慢慢的思考。
我的思路是希望通过数据结构来处理这个问题,少依赖正则表达式。
例如
123<em>abc</em>456<em>def</em>789
的数据结构为
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);
}
不过可以考虑只取一部分(比如待截取的长度*5)来做分析是否使用正则表达式去分割字符串,是可商榷的。这取决于 memory_limit 的值
早期的php默认 memory_limit = 8M
这样的话,用正则表达式切割字符串远没有自己写一个函数来的快
现在的php默认 memory_limit = 128M
我测试了一下,还是正则来的快,所以就用了正则。毕竟看起来简洁多了
我觉得在不考虑递归的情况下。
取字符串时可以预处理一下。
例如取前10 个,
最极端的情况下,字符串长度为
<em>1</em><em>2</em><em>3</em><em>4</em><em>5</em><em>6</em><em>7</em><em>8</em><em>9</em><em>0</em>
那么先把字段直接取前100个,使用唠叨老大的代码处理
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;
}
题目是:
假设有"123<em>abc</em>456<em>def</em>789"这么一个字符串,写一个函数,可以传入一个字符串,和一个要截取的长度。返回截取后的结果。要求:
1 <em>和</em>标记不得计算在长度之内。
2 截取后的字符串,要保留原有<em>标签,不过如果最后有一个标签没有闭合,则去掉其开始标签。示例:
题中的字符串,要截取长度5,则返回的字符串应该为:123ab,要截取长度8,应返回123<em>abc</em>45。我的做法大概思路是:
1 首先顺序读取字符串,并用一个resultstr变量来记录所有字符,当发现<标记时,开始将这个子字符串用tag变量记录下来。
2 如果发现tag变量形式为<\w+>也就是html标签的开始标记),就将其入栈。用栈结构来存储这个标记。若遇到<\/\w+>(html标签的结束标记),就出栈。3 否则如果是常规字符的话,长度计数器++。直到与传入的要截取长度相等。4 最后判断栈是否为空,如果为空,直接返回截取后的字符串,否则,将栈中剩余元素一个个出栈,循环从截取后的字符串中查找栈顶标签元素最后一次出现的位置,返回索引,将这个标签替换为空。直到整个栈为空为止。最后返回处理后的字符串。原题其实是没有考虑标签嵌套的情况的,我尽量的让程序可以处理嵌套标签,使其更健壮。并且尽量少的去用php的内置函数,因为那样可能会掩盖算法本身。如可以处理a1<p>b2<em>c3</em>d4</p>e5
这种形式的嵌套标签。但我发现如果标签是这种不规则形式a1<p>b2<em>c3d4</p>e5的话,程序就会出问题了。因为我只将取到的结束标记与栈顶的元素相比较,而没有去循环搜索整个栈。这里要改一下其实也可以。
不知大家还有没有其他思路,我感觉我这么做实在是太麻烦了,罗罗嗦嗦一大堆。这么多代码面试时拿笔写非得疯了不可。而且这个时间复杂度不理想,大概为O(n*(n2))。空间方面也占了很多多余的空间。我相信一定有很简单的办法。希望大家一起想想有什么更简单的方法没?
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,则都不加上。重构步骤,根据实际需求确定。
$num = 0;
$i = 0;
$k = 0;
$t = '';
while($num < $len) {
$ch = $str{$i++};
if($ch == '<' && ++$k == 1) {
$ar[] = $t;
$t = '';
}
$t .= $ch;
if(! $k) $num++;
if($ch == '>' && --$k == 0) {
$ar[] = strtolower($t);
$t = '';
}
}
$ar[] = $t; $t = $ret = '';
$len = count($ar);
foreach($ar as $k=>$v) {
if($k%2 && $v[1] != '/') {
$ch = '</'.substr($v, 1);
for($i=$k+2; $i<$len && $ar[$i]!=$ch; $i+=2);
if($i == $len) {
if($mode) {
$t = $ch . $t;
}else
$v = '';
}
}
$ret .= $v;
}
return $ret . $t;
}
$str = "123<em>abc</em>456<em>def</em>789";
$n = 10;
check_speed(200, 'html_substr', $str, $n);
check_speed(200, 'mySubstr', $str, $n);
check_speed(200, 'html_substr_1', $str, $n);html_substr
时间: 41 微秒
内存: 2824mySubstr
时间: 60 微秒
内存: 448html_substr_1
时间: 44 微秒
内存: 0
时间: 41 微秒
内存: 2824mySubstr
时间: 60 微秒
内存: 448html_substr_1
时间: 44 微秒
内存: 0==================================
也测试了,将$str 长度增加到13200字节正则使用内存比后面多差不多70倍,但依然能保持速度优势
如果内容是
123<em>abc<test</em>456><em>de><f<\em>789
判断的依据是否就又要重写一下呢?
如果递归了怎么办。
如写能在单位时间内写到通过条件覆盖。 各种特殊值的方式。这里我表达一下我自己的观点,
题目给的是关于<em> 标签的,我会考虑我做题的时间以及我自己的能力,不会一开始直接就把这个问题给抽象到各种标签解析的情况。事后有兴趣,那是以后的事。面试时,先出自己能保证的结果。在保证了结果的前提下,有能力,我想谁都会考虑进一步处理一下。
按理说函数中的变量会自动释放,调用函数前后的 memory_get_usage 之差应为 0 才对
老大贴出来那几份代码,可能需要再稍微改改
以适应
a1<body id='abc'>b2c3<p><em>d4</em>e</p>5f6</body>g7h8
这种标签带属性的情况,这样就更实用一点。
等晚上有时间,再改成真正的substr..有起始位置,截取长度。function DOHtml_substr($str,$num)
{
$i = $j = $tag = 0;
while( ($c = $str[$i++]) && $j < $num )
{
if( $c == '<') $tag = 1;
elseif($c == '>')
{
$tagname = explode(' ',trim($tg,'/'),2);
$tagname = $tagname[0];
$is_end_hasopen = strpos($tg,'/') === 0;
$is_end_noopen = $str[$i-2] == '/';
if($is_end_hasopen)
{
if($temArr['<'.$tagname.'>'][1])
{
$tgsk = $temArr['<'.$tagname.'>'][0];
$tgs[$tgsk] = array_merge(array($temArr['<'.$tagname.'>'][1]),$tgs[$tgsk] ? $tgs[$tgsk] : array());
$tgs[$j-1][] = '<'.$tg.'>';
}
unset($temArr['<'.$tagname.'>']);
}
elseif($is_end_noopen)
{
$tgs[$j-1][] = '<'.$tg.'>';
unset($temArr['<'.$tagname.'>']);
}
else
{
$temArr['<'.$tagname.'>'][] = $j-1;
$temArr['<'.$tagname.'>'][] = '<'.$tg.'>';
}
$tag = 0;
$tg = '';
}
elseif($tag == 1) $tg .= $c;
else $tmp[$j++] = $c;
}
foreach($tmp as $k=>$v)
{
$bh = '';
foreach((array)$tgs[$k] as $k2=>$v2)
$bh .= $v2;
$s .= $v.$bh;
}
return $s;
}echo htmlspecialchars(DOHtml_substr($str,13));
a1<body id='1'>b2<p>c3<em>d4</em>e5</p>f6</body><hr/>g7h
str;
echo htmlspecialchars(DOHtml_substr($str,13));
建立一个结构体
node {
string key; //关键字:em,html,and so on;
int start; //start of the key;
int end; //end of the key;
int length; //the total length of the string:
//node[i+1].length = node[i].length+length;
}node[MAX];1.首先对各个关键字进行匹配,其实就相当于括号匹配问题:遍历字符串,遇到"<"入栈,此时记录该关键字,以及起始位置:node[i].key、node[i].start;遇到"</"出栈,记录关键字的结束位置:node[i].end; 时间效率:O(N)
2.根据要输出的字符串长度nlength,遍历node.length(2分搜也可以,初始化是就是从小到大的顺序,关键是看关键字数量),可以大概判断出输出字符串到何处结束,如果该节点的node.length > nlength,则该节点的关键字就不输出(因为无法满足关键字的匹配); 时间效率:O(nlgn)(n为关键字数量 << N)思路大概就是这样,具体细节就看个人了;
该方法可以实现嵌套的输出;
而在C语言中,要自己用struct来做一个stack结构,其实说php简单,就简单在这些基本数据结构不用自己去模拟,不用自己去抽象其基本操作方法了。
不一定要用php,但凡做web的,html解析是基本功