1.給定一個排序數(shù)組毅该，你需要在 原地 刪除重復(fù)出現(xiàn)的元素咨堤，使得每個元素只出現(xiàn)一次仔蝌，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間思恐，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成沾谜。
/**
* 去除數(shù)組重復(fù)元素
* https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
* @param $arr
* @return int
*/
function removeDuplicates(&$arr) {
$index = 1;
for ($i = 1; $i < count($arr); $i++) {
$v1 = $arr[$i]; //快指針
$v2 = $arr[$index - 1]; //慢指針
//不相等的時候替換當(dāng)前慢指針位置的值
if ($v1 != $v2) {
$arr[$index] = $arr[$i];
$index++;
}
}
return $index;
}
$arr = [0,0,1,1,1,2,2,3,3,4];
removeDuplicates($arr);
2.給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格胀莹。
設(shè)計一個算法來計算你所能獲取的最大利潤基跑。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）描焰。
/**
* @param $price
* @return int|mixed
*/
function maxProfit($price) {
$length = count($price);
if ($length <= 1) {
return 0;
}
$profit = 0;
for ($i = 0; $i < $length - 1; $i++) {
$profit += max($price[$i + 1] - $price[$i],0);
}
return $profit;
}
3.假設(shè)你正在爬樓梯媳否。需要 n 階你才能到達(dá)樓頂栅螟。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢篱竭？
/**
* 爬樓梯
* @param $n
* @return mixed
*/
function climbStairs($n) {
$arrStep = [
2 => 2,
1 => 1,
0 => 0,
];
for ($i = 3; $i <= $n; $i ++) {
$arrStep[$i] = $arrStep[$i - 1] + $arrStep[$i - 2];
}
return $arrStep[$n];
}
4.給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target力图，請你在該數(shù)組中找出 和為目標(biāo)值 的那 兩個 整數(shù)，并返回它們的數(shù)組下標(biāo)掺逼。
/**
* hash法返回兩數(shù)之和的位置
* @param $nums
* @param $target
* @return array
*/
function twoSum($nums, $target) {
$map = [];
foreach ($nums as $k => $v) {
$num = $target - $v;
if (isset($map[$num])) {
return [$k, $map[$num]];
}
$map[$v] = $k;
}
return [];
}
$res = twoSum([2,4,5], 9);
5.數(shù)組連續(xù)和最大
/**
* 連續(xù)數(shù)之和最大
* @param $arr
* @return mixed
*/
function getMaxSubSum($arr) {
$curSum = $arr[0];
$maxSum = $arr[0];
for ($i = 1; $i < count($arr); $i++) {
if ($curSum > 0) {
$curSum += $arr[$i];
} else {
$curSum = $arr[$i];
}
if ($curSum > $maxSum) {
$maxSum = $curSum;
}
}
return $maxSum;
}
$arr = [1,2,3,-3];
$res = maxProfit($arr);
