1.给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
/**
* 去除数组重复元素
* 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]; //慢指针
//不相等的时候替换当前慢指针位置的值
if ($v1 != $v2) {
$arr[$index] = $arr[$i];
$index++;
}
}
return $index;
}
$arr = [0,0,1,1,1,2,2,3,3,4];
removeDuplicates($arr);
2.给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
/**
* @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.假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 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.给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
/**
* hash法返回两数之和的位置
* @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.数组连续和最大
/**
* 连续数之和最大
* @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);
