内容简介:2019-6-23 星期天 开始吧
2019-6-23 星期天 开始吧
上 一 题 链 接 Leetcode基础刷题之 PHP 解析(7. Reverse Integer)
题 目 描 述
这是一道字符串匹配的题,让我们求公共字符串前缀。
题 目 分 析
对于这一类题目,肯定都需要遍历对比一下,先来一种常规的思路,因为只要给定数组中元素当前位置有一个不同,那么公共字符串前缀就是从0截取到当前位置的上一个位置。所以我先随便拿出一个参照点(数组第一个元素),第一层遍历元素中的值,嵌套循环中遍历数组之后的元素,然后进行对比判断。最后得出结果。
/** * @param String[] $strs * @return String */ function longestCommonPrefix($strs) { if(empty($strs)) return ""; for($i=0;$i<strlen($strs[0]);$i++){ $temp=$strs[0][$i]; for($j=1;$j<count($strs);$j++){ if($i==strlen($strs[$j]) || $strs[$j][$i] != $temp){ $strs[0]=substr($strs[0],0,$i); } } } return $strs[0]; }
换一种思路
我们可以使用分而治之的思想啊。每次把数组中的元素分为两个部分,前(左)半部分和后(右)半部分,每次求出半个部分的字符串公共前缀,然后比较两个部分的公共前缀,最后得出整体的公共字符串前缀。这里求数组的中位数可以有三个方法,第一种并不推荐,因为当数值过大时可能会爆表。
/** * @param String[] $strs * @return String */ function longestCommonPrefix($strs) { if(empty($strs)) return ""; return $this->longCommon($strs,0,count($strs)-1); } function longCommon($strs,$l,$r) { if($l==$r) return $strs[$l]; else{ $mid = $l+(($r-$l)>>1) ; $left=$this->longCommon($strs,$l,$mid); $right=$this->longCommon($strs,$mid+1,$r); return $this->commonPrefix($left,$right); } } function commonPrefix($left,$right) { $min=min(strlen($left),strlen($right)); for($i=0;$i<$min;$i++){ if($left[$i] != $right[$i]){ return substr($left,0,$i); } } return substr($left,0,$min); }
Github整理地址 : https://github.com/wuqinqiang/leetcode-php
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Apache Flink 零基础入门(一):基础概念解析
- Apache Flink 零基础入门(一):基础概念解析
- JStorm 源码解析:基础线程模型
- React Hooks 解析(上):基础
- TypeScript基础入门之模块解析(一)
- TypeScript基础入门之模块解析(二)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
系统分析与设计方法
惠滕 / 孙慧、肖刚 / 机械工业出版社 / 2004-9 / 69.00元
本书是介绍信息系统分析和设计原理、方法、技术、工具和应用的力作,自问世以来,广受欢迎,以至于一版再版,延续至今。 本书采用一个完整的案例研究,以整个信息系统构件(基于Zachman框架)和信息系统开发生命周期(FAST方法学)为主线,详细探讨了系统开发生命周期的前期、中期和后期以及跨生命周期的活动。另外,书中第一章都提供了大量的练习题、讨论题、研究题和小型案例,以加深读者对书中所述理论的实际应用和......一起来看看 《系统分析与设计方法》 这本书的介绍吧!