有关数组题

2.1.6 Longest Consecutive Sequence
描述
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1,2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

function f9($arr)
{if(false&＃61;&＃61;&＃61;is_array($arr)) return false;if(($n&＃61;count($arr))<&＃61;1) return $n;$hs&＃61;array_flip($arr);//将数组的key与value翻转$maxlog&＃61;0;foreach($hs as $key&＃61;>$value){$nkey&＃61;$key&＃43;1;$longe&＃61;1;while(array_key_exists($nkey,$hs)){//判断数组中是否存在key&＃xff0c;bool$longe&＃43;&＃43;;$nkey&＃43;&＃43;;}$nkey&＃61;$key-1;while(array_key_exists($nkey,$hs)){$longe&＃43;&＃43;;$nkey--;}if($maxlog<$longe) $maxlon&＃61;$longe;}return $maxlon;
}
利用php自带的函数array_search 不用上面那么麻烦
function f9($arr)
{if(false&＃61;&＃61;&＃61;is_array($arr)) return false;if(($n&＃61;count($arr))<&＃61;1) return $n;$maxlog&＃61;0;foreach($arr as $key&＃61;>$value){$lvalue&＃61;$value&＃43;1;$longe&＃61;1;while(false!&＃61;&＃61;array_search($lvalue,$arr)){$longe&＃43;&＃43;;$lvalue&＃43;&＃43;;}$lvalue&＃61;$value-1;while(false!&＃61;&＃61;array_search($lvalue,$arr)){$longe&＃43;&＃43;;$lvalue--;}if($maxlog<$longe) $maxlon&＃61;$longe;}return $maxlon;
}
c&＃43;&＃43;中可以使用vector<> find函数


2.1.10 Remove Element
描述
Given an array and a value, remove all instances of that value in place and return the new length.The order of elements can be changed. It doesn’t maer what you leave beyond the new length.

//时间复杂度&＃xff1a;o(n)使用php自带的函数 array array_keys($arr,$value)找到数组中值为$value对应的键值&＃xff0c;存在多个返回数组&＃xff0c;不存在则true
function removeV($arr,$value)
{if(false&＃61;&＃61;&＃61;is_array($arr)) return false;$brr&＃61;array_keys($arr,$value);if(false&＃61;&＃61;&＃61;$brr) return count($arr); foreach($brr as $key&＃61;>$val){unset($arr[$val]);}return count($arr);
}
//时间复杂度&＃xff1a;o(n),
function removeV($arr,$value)
{if(false&＃61;&＃61;&＃61;is_array($arr)) return false;$n&＃61;count($arr);$index&＃61;0;for($i&＃61;0;$i<$n;&＃43;&＃43;$i){if($arr[$i]!&＃61;$value)$arr[$index&＃43;&＃43;]&＃61;$arr[$i];}return $index;
}


2.1.16 Plus One
描述
Given a number represented as an array of digits, plus one to the number.

function plusOne(&$arr)
{if(false&＃61;&＃61;&＃61;is_array($arr)) return false;$addNum&＃61;0;$yu&＃61;1;foreach( $arr as $key&＃61;>$value ){$value&＃43;&＃61;$addNum&＃43;$yu; $yu&＃61;$value/10;$value&＃61;$value%10;$arr[$key]&＃61;$value;//注意改变$value 不会影响数组的$arr大小。}
}

3.4 Add Binary
描述
Given two binary strings, return their sum (also a binary string).
For example,
a &＃61; “11”
b &＃61; “1”
Return ”100.

function addBin($a,$b)
{if(empty($a)&&empty($b)) return NULL;if(empty($a)) return $b;if(empty($b)) return $a;$arr&＃61;str_split(strrev($a));/*注意将字符串直接强制赋给数组$str&＃61;111&＃61;>array(0&＃61;>&＃39;111&＃39;);得使用str_split转为array(0&＃61;>&＃39;1&＃39;;1&＃61;>&＃39;1&＃39;;2&＃61;>&＃39;1&＃39;); */$brr&＃61;str_split(strrev($b));$n&＃61;count($arr); $m&＃61;count($brr);$yu&＃61;0;$newstr&＃61;null;//为空$maxn&＃61;$n<$m?$m:$n;for($i&＃61;0;$i<$maxn;&＃43;&＃43;$i){$ar&＃61;$i<$n?$arr[$i]:0;$br&＃61;$i<$m?$brr[$i]:0;$value&＃61;$ar&＃43;$br&＃43;$yu;$yu&＃61;$value/2;$newstr.&＃61;$value%2;}var_dump($newstr);return strrev($newstr);
}


2.1.17 Climbing Stairs
描述
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
分析
设f(n) 表示爬n 阶楼梯的不同方法数&＃xff0c;为了爬到第n 阶楼梯&＃xff0c;有两个选择&＃xff1a;
. 从第n … 1 阶前进1 步&＃xff1b;
. 从第n … 1 阶前进2 步&＃xff1b;
因此&＃xff0c;有f(n) &＃61; f(n -1) &＃43; f(n-2)。
这是一个斐波那契数列。也是动态规划中的一种

常见的写法&＃xff1a;是从上往下
function calWays($n)
{if($n&＃61;&＃61;0) return 0;if($n&＃61;&＃61;1) return 1;if($n&＃61;&＃61;2) return 2; return calWay($n-1)&＃43;calWay($n-2);
}
但是这种方法会出现重复计算的情况&＃xff0c;如下图


浪费时间&＃xff0c;采用从下往上的计算方法

function calWays($n)
{if($n&＃61;&＃61;0) return 0;if($n&＃61;&＃61;1) return 1;if($n&＃61;&＃61;2) return 2; $m&＃61;3;$f&＃61;array(0,1,2); while($m<&＃61;$n){$f[$m]&＃61;$f[$m-1]&＃43;$f[$m-2];$m&＃43;&＃43;;}return $f[$n];
}
这样减少了重复计算的次数&＃xff0c;但是增加了空间复杂度&＃xff0c;可以进行简化
function calWays($n)
{if($n&＃61;&＃61;0) return 0;if($n&＃61;&＃61;1) return 1;if($n&＃61;&＃61;2) return 2; $m&＃61;1;$prev&＃61;0;$curr&＃61;1;while($m<&＃61;$n){$temp&＃61;$curr;$curr&＃43;&＃61;$prev;$prev&＃61;$temp;$m&＃43;&＃43;;}return $curr;
}


递归和循环(取自剑指offer)