LEETCODE – FreeLoop

leetcode-棒球比赛

说明：

你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。

“+”（一轮的得分）：表示本轮获得的得分是前两轮有效回合得分的总和。
“D”（一轮的得分）：表示本轮获得的得分是前一轮有效回合得分的两倍。
“C”（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效回合的分数是无效的，应该被移除。

每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/baseball-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路：模拟栈

public function solution($ops)
    {
        $stack = [];
        $res = 0;
        foreach ($ops as $k=>$op) {
            switch ($op) {
                case "+":
                    count($stack) > 1 ? $end = end($stack) + $stack[count($stack)-2] : $end = end($stack);
                    array_push($stack, (int)$end);
                    $res += end($stack);
                    break;
                case "D":
                    array_push($stack, (int)(end($stack)*2));
                    $res += end($stack);
                    break;
                case "C":
                    $res -= array_pop($stack);
                    break;
                default:
                    array_push($stack, (int)$op);
                    $res += end($stack);
                    break;
            }
        }
        return $res;
    }

Visits: 1548

leetcode-一周中的第几天

如何不使用自带的公式自己造轮子获取一周的星期几呢，可以使用吉姆拉森日期计算公式。

详细介绍：https://baike.baidu.com/item/%E5%9F%BA%E5%A7%86%E6%8B%89%E5%B0%94%E6%A3%AE%E8%AE%A1%E7%AE%97%E5%85%AC%E5%BC%8F

public function __construct()
    {
        $this->weeks = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"];
    }

    /**
     * 基姆拉尔森日期公式
     * @param int $day
     * @param int $month
     * @param int $year
     * @return mixed
     */
    public function solution(int $day, int $month, int $year)
    {
        return $this->weeks[($day + 2*$month + 3*($month+1)/5 + $year + $year/4 - $year/100 + $year/400) % 7];
    }

Visits: 411

leetcode-最大子序和

题目：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray

动态规划解法的思路：

假定第一个元素为最终返回的子序和，设为result
设定数组元素相加和为 sum
遍历数组，将元素相加获得的sum与result对比，取最大
时间复杂度 O(n)

代码：

class MaxSubArray
{
    function solution($nums)
    {
        $result = $nums[0];
        $sum = 0;

        for ($i=1; $i < count($nums); $i++) {
            if ($sum > 0) {
                $sum += $nums[$i];
            } else {
                $sum = $nums[$i];
            }

            $result = max($result, $sum);
        }

        return $result;
    }
}

Visits: 708

leetcode-斐波那契数

class Fib
{
    //自底向上计算结果
    public function solution($N)
    {
        $current = 0;
        $next = 1;
        while ($N-- > 0) {
            $next = $next + $current;
            $current = $next - $current;
        }
        return (int)$current;
    }
}

$fib = new Fib();
$res = $fib->solution(10);

算法使用了自底向上的方法，通过迭代计算斐波那契数子问题的结果，最后获得最终结果。

复杂度分析：

时间复杂度：O(N)O(N)。
空间复杂度：O(N)O(N)，使用了空间大小为N 的数组。

github练习仓库

题目来源：力扣中国-斐波那契数

Visits: 549