首頁 > 後端開發 > php教程 > 关于腾讯的那谈题截取字符串的题

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

WBOY
發布: 2016-06-13 12:51:54
原創
940 人瀏覽過

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


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

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

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



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

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

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



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

b2c3d4

e5
这种形式的嵌套标签。但我发现如果标签是这种不规则形式a1

b2c3d4

e5的话,程序就会出问题了。因为我只将取到的结束标记与栈顶的元素相比较,而没有去循环搜索整个栈。这里要改一下其实也可以。


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



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

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

来添砖加瓦
 <div class="clear">
                 
              
              
        
            </div>
登入後複製

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板