题1:对一个有序数组去除重复元素,返回无重复的数组的长度
解决思路:
有序数组,不是递增就是递减。有序的,有利于使用双指针去重。
用双指针算法,一个指针pre指向第一个元素,另一个指针i遍历第二个元素到最后一个元素。如果pre指向的元素不等于i指向的元素,用pre+1的位置保存i指向的元素;
如果pre指向的元素等于i指向的元素,pre还在原位置。
当数组遍历完成的时候,[0,pre]这区间存的就是这个有序数组去重之后的结果。
class Solution {
/**
* @param Integer[] $nums
* @return integer
*/
function remDupli($nums) {
//pre指向有序数组的索引0的位置
$pre = 0;
$len = count($nums);
if($len == 0){
return 0;
}
for($i=1;$i
if($nums[$pre] != $nums[$i]){
$pre ++;
$nums[$pre] = $nums[$i];
}
}
//去重的区间段[0,$pre],所以长度是pre+1
return $pre+1;
}
}
$nums = [0,1,2,3,4,5,5,6];
$nums =[2,2,2,3,4,4,5,5];
$obj = new Solution();
$res = $obj->remDupli($nums);
var_dump($res);
//4
题2:一个字符串有小写字母和数字组成,对这个字符串进行重新格式化,使得字符串相邻的类型不同。如果不能格式化相邻不同的字符串,返回空字符串。
解决思路:
根据题意,计算字符串中数字的个数,看数字和字母是否相等。可以知道是否能格式化。数字和字母的个数差不能大于1。
然后把数字和字母,一个个的连起来。对撞指针的方式把字母和数字分布到字符串的两端。对撞指针的好处是不需要额外的空间。
class Solution {
/**
* @param string $str
* @return string
*/
function format($str) {
$len = strlen($str);
$l = 0;
$r = $len -1;
$res_str = '';
//第一步:左边放字母,右边放数字
while($l
//使用双指针,遇到需要交换的,进行交换。
//var_dump($l-$r,$l,$r,$str);
//左边是字母,继续。遇到不是字母就停下,准备交换
if($this->is_alpha($str{$l})){
$l++;
}
//左边是数字,继续。遇到不是数字就停下,准备交换
if($this->is_int($str{$r})){
$r--;
}
//当左边是数字,右边是字母时,下面进行交换。
if($this->is_int($str{$l}) && $this->is_alpha($str{$r})){
//var_dump('--',$str);
$tmp = $str{$l};
$str{$l} = $str{$r};
$str{$r} = $tmp;
$l++;
$r--;
}
}
//var_dump('----',$l,$r,$str);
//第二步:找到字母和数字的分界点
$l = 0;
$r = 0;
for($i=0;$i
if($this->is_int($str{$i})){
$l = $i-1;
$r = $i;
break;
}
}
//[0,$l]是字母,[$r,$len-1]是数字。
//字母和数字的个数差不能大于1,根据题意返回空字符串。
if(abs(($len - ($l+1))-($l+1)) > 1){
return '';
}
//第三步:组成格式化的字符串
//$len - ($l+1) 是右边,即数字的个数 , $l+1 是字母的个数
if($len - ($l+1) > $l+1){
//数字多的情况,先取数字。数字取完循环结束。
for($i=0,$j=$len-1;$j>=$r;$i++,$j--){
$res_str .= $str{$j};
//在字母范围内,取出字母,超出范围,就不取字母了。
if($i <= $l){
$res_str .= $str{$i};
}
}
}else{
//字母多的情况,先取字母。字母取完循环结束。
for($i=0,$j=$len-1;$i<=$l;$i++,$j--){
$res_str .= $str{$i};
//在数字范围内,取出数字,超出范围,就不取数字了。
if($j >= $r){
$res_str .= $str{$j};
}
}
}
return $res_str;
}
function is_alpha($a){
if($a >= 'a' && $a <= 'z'){
return 1;
}else{
return 0;
}
}
function is_int($a){
if($a >= '0' && $a <= '9'){
return 1;
}else{
return 0;
}
}
}
$str = '9o5ck83';
$obj = new Solution();
$res = $obj->format($str);
var_dump($res);
//3k8o9c5
双指针用法和优势
对于有序的,相邻的数字一样的留下一个就在全局去重了,使用双指针,可以提高效率;还有就是双指针可以快速的交换元素,整理数据,进行快速分类。
优势:不需要额外的空间,执行效率高。
如果觉得《字节跳动面试经验 php 双指针算法:字节跳动初级面试题 PHP》对你有帮助,请点赞、收藏,并留下你的观点哦!