关于腾讯的那道题截取字符串的题,该怎么解决-PHP教程-爱易网页

关于腾讯的那道题截取字符串的题,该怎么解决

日期：2014-05-17　浏览次数：20551 次

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

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

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

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

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

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

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

原题其实是没有考虑标签嵌套的情况的，我尽量的让程序可以处理嵌套标签，使其更健壮。并且尽量少的去用php的内置函数，因为那样可能会掩盖算法本身。如可以处理a1b2c3d4e5
这种形式的嵌套标签。但我发现如果标签是这种不规则形式a1b2c3d4e5的话，程序就会出问题了。因为我只将取到的结束标记与栈顶的元素相比较，而没有去循环搜索整个栈。这里要改一下其实也可以。

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

PHP code


<?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/>';

------解决方案--------------------
呵呵，这题有印象

来添砖加瓦

PHP code


$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

免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。

关于腾讯的那道题截取字符串的题,该怎么解决

相关资料更多>

推荐阅读更多>