master

分支 (1)

管理

管理

master

keep-learning
/
slideWindow.php

<?php

function getMsectime() {
    list($msec, $sec) = explode(' ', microtime());
    return (float)sprintf('%.0f', (floatval($msec) + floatval($sec)) * 1000);
}

class Solution {

    public $nums;

    /**
     * 长度最小的子数组
     *
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
     * 如果不存在符合条件的子数组，返回 0 。
     *
     * 分析：把遍历过的值累加，如果超过了就减去
     *
     * @param Integer[] $nums
     * @return Integer
     */
    function minSubArrayLen($target, $nums) {
        if (count($nums) < 1) {
            return 0;
        }
        $left = $num = 0;
        $res = PHP_INT_MAX;
        for ($right = 0; $right < count($nums); $right++) {
            $num += $nums[$right];
            while ($num >= $target) {
                $num -= $nums[$left++];
                $res = min($res, $right - $left + 1);
            }
        }

        return $res == PHP_INT_MAX ? 0 : $res;
    }

    /**
     *
     * 77.最小覆盖子串
     *
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
     * 注意：
     *     对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     *     如果 s 中存在这样的子串，我们保证它是唯一的答案。
     *  s = "ADOBECODEBANC", t = "ABC" => "BANC"
     * @param String $s
     * @param String $t
     * @return String
     */
    function minWindow($s, $t) {
        $left = 0;
        $tArr = $sArr = [];
        $retStr = '';
        for ($i=0; $i < strlen($t); $i++) {
            $tArr[$t[$i]]++;
        }
        for ($right = 0; $right < strlen($s); $right++) {
            if (isset($tArr[$s[$right]])) {
                $sArr[$s[$right]]++;
            }
            while ($this->check($tArr, $sArr)) {
                if ($retStr == '' || strlen($retStr) >= ($right - $left + 1)) {
                    $retStr = substr($s, $left, ($right - $left + 1));
                }
                if (isset($sArr[$s[$left]])) {
                    $sArr[$s[$left]]--;
                }
                $left++;
            }
        }

        return $retStr;
    }

    // 判断数组arr2的各项值是否大于arr1
    function check($arr1, $arr2) {
        if (count($arr1) != count($arr2)) {
            return false;
        }
        foreach ($arr1 as $key => $value) {
            if ($value > $arr2[$key]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 904. 水果成篮
     *
     * 在一排树中，第 i 棵树产生tree[i] 型的水果。
     * 你可以从你选择的任何树开始，然后重复执行以下步骤：
     *  1. 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
     *  2. 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
     *
     * 请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
     * 你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
     * 用这个程序你能收集的水果树的最大总量是多少?
     *
     * @param Integer[] $fruits
     * @return Integer
     */
    function totalFruit($fruits) {
        $left = $retLen = 0;
        $totalArr = [$fruits[0] => 1];
        for ($right = 1; $right < count($fruits); $right++) {
            $totalArr[$fruits[$right]]++;
            while (count($totalArr) > 2) {
                if (!$retLen || $retLen < ($right - $left)) {
                    $retLen = $right - $left;
                }
                // 滑动左边
                $totalArr[$fruits[$left]]--;
                if ($totalArr[$fruits[$left]] <= 0) {
                    unset($totalArr[$fruits[$left]]);
                }
                $left++;
            }
            if (count($totalArr) == 2) {
                if (!$retLen || $retLen < ($right - $left + 1)) {
                    $retLen = $right - $left + 1;
                }
            }
        }

        return $retLen ? $retLen : count($fruits);
    }
}

echo "<!DOCTYPE html>
<html>
<head>
    <meta charset=\"utf-8\">
    <title>算法测试</title>
</head>
<body>
    <div style='margin:0 auto; width:50%;'>";

$a = $_GET['a'] ?? '';
$b = $_GET['b'] ?? '';
$c = $_GET['c'] ?? '';
$d = $_GET['d'] ?? '';
$x = $_GET['x'] ?? '';
$y = $_GET['y'] ?? '';

echo "<form>
参数a：<input type='text' name='a' value='{$a}'><br><br>
参数b：<input type='text' name='b' value='{$b}'><br><br>
参数c：<input type='text' name='c' value='{$c}'><br><br>
参数d：<input type='text' name='d' value='{$d}'><br><br>
参数x：<input type='text' name='x' value='{$x}'><br><br>
参数y：<input type='text' name='y' value='{$y}'><br><br>
<input type='submit' value='提交'>
</form>";

$time1 = getMsectime();
$solution = new Solution;

// $target = 7;
// $nums = [2,3,1,2,4,3];
// $result = $solution->minSubArrayLen($target, $nums);

// $s = "ADOBECODEBANC";
// $t = "ABC";
// $s = "a";
// $t = "aa";

// $s = "a";
// $t = "b";

// $s = "ab";
// $t = "a";

// $s = "aa";
// $t = "aa";

// $s = "cabwefgewcwaefgcf";
// $t = "cae";

// $result = $solution->minWindow($s, $t);

// $fruits = [1,2,1];
// $fruits = [0,1,2,2];
// $fruits = [1,2,3,2,2];
// $fruits = [3,3,3,1,2,1,1,2,3,3,4];
$result = $solution->totalFruit($fruits);

$time2 = getMsectime();

$result = (is_object($result) || is_array($result)) ? json_encode($result) : $result;
// echo $solution->nums."次<br>";
// echo '<br>结果：'.implode(',', $result1)."<br>", '执行耗时：'.($time2 - $time1)."ms";
echo '<br>结果：'.$result."<br>", '执行耗时：'.($time2 - $time1)."ms";


echo "
    </div>
</body>
</html>";