<?php

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

class Solution {

    public $nums;

    /**
     * 删除有序数组中的指定重复项
     * 
     * 给你一个有序数组nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
     * 不要使用额外的数组空间，你必须在原地修改输入数组,并在使用O(1)额外空间的条件下完成。
     * 
     * 分析：删除数组的元素不能简单的直接删除，实质上是对指针空间的值进行覆盖
     * 思路： [1,3,5,5,7,9] -> 5 => [1,3,7,9]
     * 1. 用2层循环，第一层循环遍历所有元素搜索到目标元素，第二层循环将目标元素往后移动
     * 2. 用2根指针，2根指针同时往后移动，快指针直接完整遍历，慢指针在找到目标元素后直接移动元素
     * 
     * @param Integer[] $nums
     * @return Integer
     */
    function removeElement(&$nums, $val) {
        $slowIndex = 0;
        for ($fastIndex = 0; $fastIndex < count($nums); $fastIndex++) {
            // 如果找到目标元素，慢指针会等快指针往前移动一下，然后交换数据
            if ($val != $nums[$fastIndex]) {
                $nums[$slowIndex++] = $nums[$fastIndex];
            }
        }

        return $slowIndex;
    }

    /**
     * 删除有序数组中的重复项
     * 
     * 给你一个有序数组nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
     * 不要使用额外的数组空间，你必须在原地修改输入数组,并在使用O(1)额外空间的条件下完成。
     * 
     * 分析：删除数组的元素不能简单的直接删除，实质上是对指针空间的值进行覆盖
     * 思路： [1,3,5,5,7,9] -> 5 => [1,3,7,9]
     * 1. 用2层循环，第一层循环遍历所有元素搜索到目标元素，第二层循环将目标元素往后移动
     * 2. 用2根指针，2根指针同时往后移动，快指针直接完整遍历，慢指针在找到目标元素后直接移动元素
     * 
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {        
        $size = count($nums);
        if ($size == 1) {
            return 1;
        }

        $slowIndex = 0;
        for ($fastIndex = 1; $fastIndex < $size; ++$fastIndex) {
            if ($nums[$slowIndex] !== $nums[$fastIndex]) {
                $nums[++$slowIndex] = $nums[$fastIndex];                
            }
        }

        echo "快={$fastIndex},慢={$slowIndex},[".implode(',', $nums)."]";
        return $slowIndex;
    }

    /**
     * 移动零
     * 
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 输入: [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     * 
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums) {
        if (count($nums) <= 1) {
            return $nums;
        }
        $slowIndex = 0;
        for ($fastIndex = 0; $fastIndex < count($nums); $fastIndex++) { 
            if (0 !== $nums[$fastIndex]) {
                $nums[$slowIndex] = $nums[$fastIndex];
                if ($slowIndex !== $fastIndex) {
                    $nums[$fastIndex] = 0;
                }
                $slowIndex++;
            }
        }

        return $nums;
    }

    /**
     * 844. 比较含退格的字符串
     * 
     * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
     * 如果相等，返回 true ；否则，返回 false 。
     * 
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function backspaceCompare($s, $t) {
        return $this->backspaceStr($s) == $this->backspaceStr($t);
    }

    function backspaceStr($s) {
        $slowIndex = 0;
        for ($fastIndex = 0; $fastIndex < strlen($s); $fastIndex++) { 
            if ($s[$fastIndex] != '#') {
                $s[$slowIndex++] = $s[$fastIndex];
            } elseif ($slowIndex > 0) {
                $slowIndex--;
            }
        }
        return substr($s, 0, $slowIndex);
    }

    /**
     * 有序数组的平方
     * 
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     * 
     * @param Integer[] $nums
     * @return Integer[]
     */
    function sortedSquares($nums) {
        $size = count($nums);
        $arr = [];
        for ($i = 0; $i < $size; $i++) { 
            $arr[$i] = 0;
        }
        $left = 0;
        $right = $index = $size - 1;
        while ($left <= $right) {
            if ($nums[$left]*$nums[$left] < $nums[$right]*$nums[$right]) {
                $arr[$index--] = $nums[$right]*$nums[$right];
                $right--;
            } else {
                $arr[$index--] = $nums[$left]*$nums[$left];
                $left++;
            }
        }
        return $arr;
    }

    /**
     * 15. 三数之和
     * 
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
     * 注意： 答案中不可以包含重复的三元组。
     * 
     * 示例：
     *   给定数组 nums = [-1, -1, -1, 0, 1, 2, 2, -1, -4]，
     *   满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
     * 
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        $res = [];
        // 先对数组排序
        sort($nums);
        $count = count($nums);
        for ($i=0; $i < $count; $i++) { 
            // 去除重复的
            if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
                continue;
            }
            $left = $i + 1;
            $right = $count - 1;
            while ($left < $right) {
                $sum = $nums[$i] + $nums[$left] + $nums[$right];
                // 累加小于0，需要更大的数，左指针移动
                if ($sum < 0) {
                    $left++;
                } 
                // 累加大于0，需要更小的数，右指针移动
                elseif($sum > 0) {
                    $right--;
                } 
                // 找到一个，继续移动
                else {
                    $res[] = [$nums[$i], $nums[$left], $nums[$right]];
                    while ($left < $right && $nums[$left] == $nums[$left + 1]) $left++;     // 如果前后相等继续移动
                    while ($left < $right && $nums[$right] == $nums[$right - 1]) $right--;  // 如果前后相等继续移动
                    // 常规的收缩头尾
                    $left++;
                    $right--;
                }
            }
        }

        return $res;
    }

    
    /**
     * 18. 四数之和
     * 
     * 给你一个由 n 个整数组成的数组nums ，和一个目标值 target 。
     * 请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
     *    0 <= a, b, c, d< n
     *    a、b、c 和 d 互不相同
     *    nums[a] + nums[b] + nums[c] + nums[d] == target
     *    你可以按 任意顺序 返回答案 。
     * 
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[][]
     */
    function fourSum($nums, $target) {
        $res = [];
        sort($nums);
        $count = count($nums);
        if ($count < 4) {
            return $res;
        }
        for ($i=0; $i < $count; $i++) {
            // 去重
            if ($i > 0 && $nums[$i] == $nums[$i - 1 ]) {
                continue;
            }
            for ($j=$i+1; $j < $count; $j++) { 
                // 去重
                if ($j > $i+1 && $nums[$j] == $nums[$j - 1]) {
                    continue;
                }
                $left = $j + 1;
                $right = $count - 1;
                while ($left < $right) {
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
                    // 小了，左边收
                    if ($sum < $target) {
                        $left++;
                    }
                    // 大了，右边收
                    elseif($sum > $target) {
                        $right--;
                    }
                    // 找到了
                    else {
                        $res[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];
                        while ($left < $right && $nums[$left] == $nums[$left + 1]) $left++;     // 如果前后相等额外的收缩
                        while ($left < $right && $nums[$right] == $nums[$right - 1]) $right--;  // 如果前后相等额外的收缩
                        // 常规的收缩头尾
                        $left++;
                        $right--;
                    }
                }
            }
        }

        return $res;
    } 

    /**
     * 151. 翻转字符串里的单词
     * 
     * 给你一个字符串s，逐个翻转字符串中的所有单词 。
     * 单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。
     * 请你返回一个翻转s中单词顺序并用单个空格相连的字符串。
     * 说明：
     *     输入字符串s可以在前面、后面或者单词间包含多余的空格。
     *     翻转后单词间应当仅用一个空格分隔。
     *     翻转后的字符串中不应包含额外的空格。
     * 
     * 输入：s = "the sky is blue"
     * 输出："blue is sky the"
     * 
     * @param String $s
     * @return String
     */
    function reverseWords($s) {
        $s = $this->rmExtraSpace($s);
        $len = strlen($s);
        $s = $this->reverseStr($s, 0, $len - 1);
        $start = 0;
        for ($i=0; $i < $len; $i++) { 
            if ($s[$i] == ' ') {
                $s = $this->reverseStr($s, $start, $i - 1);
                $start = $i + 1;
            }
            if ($i == ($len - 1)) {
                $s = $this->reverseStr($s, $start, $i);
                $start = $i;
            }
        }
        return $s;
    }

    function rmExtraSpace($s) {
        $slow = 0;
        for ($fast=0; $fast < strlen($s); $fast++) {
            if ($s[$fast] == ' ' && $s[$slow] == ' ' && $slow == 0) {
                continue;
            }
            if ($s[$fast] != ' ' || ($s[$fast] == ' ' && $s[$fast - 1] != ' ')) {
                
                $s[$slow++] = $s[$fast];
            }
            if ($fast == (strlen($s) - 1) && $s[$fast] == ' ') {
                $slow--;
            }
        }
        return substr($s, 0, $slow);
    }

    function reverseStr($s, $left, $right) {
        while ($left < $right) {
            $tmp = $s[$left];
            $s[$left] = $s[$right];
            $s[$right] = $tmp;
            $left++;
            $right--;
        }
        return $s;
    }
}

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;

// $a = [1,2,2,3,4,5,6,6,7];
// $a = [0,0,1,1,1,2,2,3,3,4];
// $a = [1,1,2];
// 123345667
// 123445667
// 123455667
// 123456667
// 123456777
// $a = [1,1,2];
// $result = $solution->removeDuplicates($a);

// $a = [0,1,0,3,12];
// $a = [1,0,1];
// $result = $solution->moveZeroes($a);

// $result = $solution->backspaceCompare($a, $b);

// $a = [-4,-1,0,3,10];
// $result = $solution->sortedSquares($a);

// $nums = [-1,0,1,2,-1,-4];
// $nums = [-2,0,0,2,2];
// $nums = [-1,0,1,2,-1,-4];
// $nums = [0,0,0,0];
// $nums = [-1,0,1,0];
// $result = $solution->threeSum($nums);

// $nums = [1,0,-1,0,-2,2];$target = 0;
// $nums = [2,2,2,2,2]; $target = 8;
// $result = $solution->fourSum($nums, $target);

// $a = "  hello world  ";
$a = "the sky is blue";
// $a = "the  sky ";
$result = $solution->reverseWords($a);

$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>";