0

0

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

php中文网

php中文网

发布时间:2016-06-13 10:06:00

|

1002人浏览过

|

来源于php中文网

原创

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


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



PHP code
'; $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

SekoTalk
SekoTalk

商汤科技推出的AI对口型视频创作工具

下载
f6g7h8";echo '处理结果为:

',htmlspecialchars( mySubstr( $str, 18 ) ),'
';echo "内存使用情况:",(memory_get_usage()-$stmem),'
';echo "算法运行时间(microtime):",(microtime(true)-$sttime),'
';


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

来添砖加瓦
PHP code
$str = "a1b2

c3d4e5

f6g7h8";$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] => ) ……*/

相关专题

更多
c++主流开发框架汇总
c++主流开发框架汇总

本专题整合了c++开发框架推荐,阅读专题下面的文章了解更多详细内容。

79

2026.01.09

c++框架学习教程汇总
c++框架学习教程汇总

本专题整合了c++框架学习教程汇总,阅读专题下面的文章了解更多详细内容。

46

2026.01.09

学python好用的网站推荐
学python好用的网站推荐

本专题整合了python学习教程汇总,阅读专题下面的文章了解更多详细内容。

121

2026.01.09

学python网站汇总
学python网站汇总

本专题整合了学python网站汇总,阅读专题下面的文章了解更多详细内容。

12

2026.01.09

python学习网站
python学习网站

本专题整合了python学习相关推荐汇总,阅读专题下面的文章了解更多详细内容。

15

2026.01.09

俄罗斯手机浏览器地址汇总
俄罗斯手机浏览器地址汇总

汇总俄罗斯Yandex手机浏览器官方网址入口,涵盖国际版与俄语版,适配移动端访问,一键直达搜索、地图、新闻等核心服务。

71

2026.01.09

漫蛙稳定版地址大全
漫蛙稳定版地址大全

漫蛙稳定版地址大全汇总最新可用入口,包含漫蛙manwa漫画防走失官网链接,确保用户随时畅读海量正版漫画资源,建议收藏备用,避免因域名变动无法访问。

370

2026.01.09

php学习网站大全
php学习网站大全

精选多个优质PHP入门学习网站,涵盖教程、实战与文档,适合零基础到进阶开发者,助你高效掌握PHP编程。

45

2026.01.09

php网站搭建教程大全
php网站搭建教程大全

本合集专为零基础用户打造,涵盖PHP网站搭建全流程,从环境配置到实战开发,免费、易懂、系统化,助你快速入门建站!

12

2026.01.09

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
AngularJS教程
AngularJS教程

共24课时 | 2.5万人学习

CSS3实现按钮特效视频教程
CSS3实现按钮特效视频教程

共15课时 | 3.2万人学习

细说PHP第三季
细说PHP第三季

共58课时 | 11.2万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号