<?php

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

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
echo "<pre>";
class Solution {
    
    /**
     * 344. 反转字符串
     * 
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * 
     * @param String[] $s
     * @return NULL
     */
    function reverseString(&$s) {
        $left = 0;
        $right = count($s) - 1;
        while ($left < $right) {
            $tmp = $s[$left];
            $s[$left] = $s[$right];
            $s[$right] = $tmp;
            $left++;
            $right--;
        } 

        return $s;
    }

    /**
     * 541. 反转字符串 II
     * 
     * 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
     *   如果剩余字符少于 k 个，则将剩余字符全部反转。
     *   如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
     * 
     * @param String $s
     * @param Integer $k
     * @return String
     */
    function reverseStr($s, $k) {        
        for ($i=0; $i < strlen($s); $i+=2*$k) { 
            $left = $i;
            $right = min(strlen($s) - 1, $left + $k - 1);
            while ($left < $right) {
                $tmp = $s[$left];
                $s[$left] = $s[$right];
                $s[$right] = $tmp;
                $left++;
                $right--;
            }
        }

        return $s;
    }

    /**
     * 剑指 Offer 05. 替换空格
     * 
     * 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
     * 示例 1： 输入：s = "We are happy."
     * 输出："We%20are%20happy."
     * 
     * @param String $s
     * @return String
     */
    function replaceSpace($s) {
        $oldLen = strlen($s);
        $newLen = $oldLen;
        for ($i=0; $i < $oldLen; $i++) { 
            if ($s[$i] === ' ') {
                $newLen += 2;
            }
        }

        $i = $oldLen - 1;
        $j = $newLen - 1;
        for (; $i >= 0; $i--) {
            // 没找到正常替换并移动
            if ($s[$i] !== ' ') {
                $s[$j--] = $s[$i];
            }
            // 找到之后j直接移动三格
            else {
                $s[$j--] = "0";
                $s[$j--] = "2";
                $s[$j--] = "%";
            }
        }

        return $s;
    }

}

$solution = new Solution;

// 输入：s = ["h","e","l","l","o"]
// 输出：["o","l","l","e","h"]

// $s = ["h","e","l","l","o"];
// var_dump($solution->reverseString($s));

// 输入：s = "abcdefg", k = 2
// 输出："bacdfeg"

// $s = "abcdefg"; $k = 2;
// var_dump($solution->reverseStr($s, $k));

$s = "We are happy.";
var_dump($solution->replaceSpace($s));