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

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


题目是:
假设有"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))。空间方面也占了很多多余的空间。我相信一定有很简单的办法。希望大家一起想想有什么更简单的方法没？

function mySubstr( $str, $length ){

	$tagcnt = 0;
	$charcnt = 0;
	$tag = '';
	$maxlen = strlen( $str );
	$resultstr = '';
	$tagstack = array();

	for( $i = 0; $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),'
';

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

来添砖加瓦

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系[e-mail]核实处理。
相关文章
相关视频

• 详解win10下PHP的安装配置（以php5.6为...
• php Swoole实现毫秒定时计划任务（详解）
• 一文详解Windows和Linux环境下怎么安装配...
• 【DTM】PHP协程客户端v0.1 beta版本发...
• 关于腾讯的那谈题截取字符串的题

• HTML基础教程之<strong>和<em>
• HTML基础教程之<span>标签
• HTML基础教程之<meta>标签
• HTML <div> 和<span>
• multiple backgrounds多背景

网友评论

文明上网理性发言，请遵守 新闻评论服务协议

我要评论

立即提交

专题推荐

• 独孤九贱-php全栈开发教程

  全栈 170W+

  主讲：Peter-Zhu 轻松幽默、简短易学，非常适合PHP学习入门

• 玉女心经-web前端开发教程

  入门 80W+

  主讲：灭绝师太 由浅入深、明快简洁，非常适合前端学习入门

• 天龙八部-实战开发教程

  实战 120W+

  主讲：西门大官人 思路清晰、严谨规范，适合有一定web编程基础学习