PHP之-高频基础算法

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

示例说明：

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；
另：
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

function stockProfit()
{
    $prices = [9,2,7,4,3,1,8,4];
    $c = count($prices);
    $maxProfit = 0;
    $minPrice = $prices[0];
    $ret=[];//最佳买入卖出时间
    $buyDay = 1;
    for ($i=1; $i < $c; $i++) {
        if ($prices[$i] < $minPrice) {
            $minPrice = $prices[$i];
            $buyDay = $i+1;
        } else {
            $tmpProfit = $prices[$i]- $minPrice;
            if ($tmpProfit > $maxProfit) {
                $maxProfit = $tmpProfit;
                $ret[0] = $buyDay; //最佳买入时间
                $ret[1] = $i+1; //最佳卖出时间
            }
        }
    }
    print_r($ret);
    return $maxProfit;
}

买卖股票的最佳时机变体之：不限次数

但强制要求每次买入前，必须卖出持有的股票。其实这道题反而更简单，为什么呢？
因为既然买卖次数不限，那我们完全可以在每一次低点都进行买入，在每一次高点都进行卖出。
这样，连上题中的 最小价格 的条件因素都不用考虑了，代码如下：

function stockProfit()
{
    $prices = '51638247';
    $prices = str_split($prices);
    $c = count($prices);
    $maxProfit = 0;
    for ($i=1; $i < $c; $i++) {
        if ($prices[$i] > $prices[$i-1]) {
            $maxProfit += $prices[$i]-$prices[$i-1];
        }
    }
    return $maxProfit;
}

力扣之求数组中第三大的数

原题有个要求：

1 <= nums.length <= 104
-2^31 <= nums[i] <= 2^31 - 1
如果有这个要求，需要使用内置变量 PHP_INT_MIN，获取一个小于条件中的负数值作为初始值。

//方法1
function thirdMax ($a) {
    $c = count($a);
    if ($c <= 2) {
        return max($a);
    }
    $fMax = $sMax = $tMax = PHP_INT_MIN;
    for ($i=0; $i < $c; $i++) {
        if ($a[$i] === $fMax || $a[$i] === $sMax) {
            continue;
        }
        if ($a[$i] > $fMax) {
            list($tMax, $sMax, $fMax) = [$sMax, $fMax, $a[$i]];
        } else if ($a[$i] > $sMax) {
            list($tMax, $sMax) = [$sMax, $a[$i]];
        } else if ($a[$i] > $tMax) {
            $tMax = $a[$i];
        }
    }
    if ($tMax === PHP_INT_MIN) {
        $tMax = $fMax;
    }
    return $tMax;
}
//方法2，不借助中间变量，时间复杂度较高
function thirdMax ($a) {
    $a = array_unique($a);
    sort($a);
    $c = count($a);
    return $c<3 ? max($a) : $a[$c-3];
}

力扣 134 题之「加油站」问题

加油站题型说明

这是个典型的贪心算法问题，题解如下：

function tanxin($gas, $cost) {
    $c = count($gas);
    $sum=0;
    for ($i=0; $i < $c; $i++) {
        // 判断是否最后 总获得油量 小于 总油耗量，如果小于则不能完成循环
        $sum+=$gas[$i]-$cost[$i];
    }
    if ($sum<0) {
        return -1;
    }
    $tank = 0;
    $start = 0;
    for ($i=0; $i < $c; $i++) { 
        $tank+=$gas[$i]-$cost[$i];
        if ($tank<0) {
            // 如果走到 i 时剩余总油量正好小于 0，则 i 点必然是cost远大于gas；
            // 即便用 i 作为起点也是如此，cost大于gas 无法启动汽车；
            $start=$i+1;
            $tank=0;
        }
    }
    $start = ($start==$c)?0:$start;
    return $start;
}

814之二叉树剪枝

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。
返回移除了所有不包含 1 的子树的原二叉树。
节点 node 的子树为 node 本身加上所有 node 的后代。

//给定如下treenode类
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}
class Solution {  
  /**
     * @param TreeNode $root
     * @return TreeNode
     */
    function pruneTree($root) {
        return $this->dfs($root) ? $root : null;
    }
    // 总觉得此处的subNode应该传递引用才对，因为遍历方法并没有返回tree
    function dfs(&$subNode) {
        if ($subNode === null) {
            return false;
        }
        $lNode = $this->dfs($subNode->left);
        $rNode = $this->dfs($subNode->right);
        if (!$lNode) {
            $subNode->left = null;
        }
        if (!$rNode) {
            $subNode->right = null;
        }
        return $subNode->val === 1 || $lNode || $rNode;
    }
}

70、爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

典型的动态规划算法题，F(3)=F(2)+F(1)，以此类推……F(n)=F(n-2)+F(n-1)，题解如下，复杂度O(N)：

function dpStair($n) {
    if ($n<3) {
        return $n;
    }
    $f1=1;
    $f2=2;
    $fi = 0;
    for ($i=3; $i <= $n; $i++) { 
        $fi=$f1+$f2;
        list($f2,$f1)=[$fi, $f2];
    }
    return $fi;
}
print_r([
    dpStair(10),
]);