<?php

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

class Solution {

    public $nums;

    /**
     * @param Integer $a
     * @param Integer $b
     * @return Integer
     */
    function divide($a, $b) {
        if ($a == -pow(2, 31) && $b == -1) return pow(2, 31) -1;
        $num = 0;
        $fu = ($a>0) ^ ($b>0) ? 1 : -1;
        $a = abs($a);
        $b = abs($b);
        while($a >= $b) {
            $a -= $b;
            $num++;
        }

        return $num*$fu;
    }

    /**
     * @param Integer $a
     * @param Integer $b
     * @return Integer
     */
    function divide1($a, $b) {
        if ($a == -pow(2, 31) && $b == -1) return pow(2, 31) -1;
        $num = 0;
        $fu = $a*$b > 0 ? 1 : -1;
        $a = abs($a);
        $b = abs($b);
        while(($a - $b) >= pow(2, $num)) {
            $num++;
        }

        return $num*$fu;
    }

    /**
     * 求a的b次方
     * @param Integer $a
     * @param Integer $b
     * @return Integer
     */
    function myfunc1($a, $b) {
        $this->nums++;
        // echo $b,"<br>";
        if ($b == 0) return 1;
        $t = $this->myfunc1($a, $b / 2);
        if ($b % 2 == 1) {
            return $t * $t * $a;
        }
        return $t * $t;
    }

    /**
     * 最长回文子串
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        $len = strlen($s);
        $ret = "";

        for ($i=0; $i < $len; $i++) {
            $tmp = $s[$i];
            $j = 1;
            while (($i + $j) < $len && $i >= $j) {
                if ($s[$i+$j] == $s[$i-$j]) {
                    $tmp = $s[$i-$j] . $tmp . $s[$i+$j];
                } else {
                    break;
                }
                $j++;
            }
            $ret = strlen($ret) > strlen($tmp) ? $ret : $tmp;
        }

        for ($i=0; $i < $len; $i++) {
            if ($i+1 < $len && $s[$i] == $s[$i+1]) {
                $tmp = $s[$i] . $s[$i+1];
            } else {
                $tmp = "";
                continue;
            }
            
            $j = 1;
            while (($i + $j + 1) < $len && $i >= $j) {
                if ($s[$i+$j+1] == $s[$i-$j]) {
                    $tmp = $s[$i-$j] . $tmp . $s[$i+$j+1];
                } else {
                    break;
                }
                $j++;
            }
            $ret = strlen($ret) > strlen($tmp) ? $ret : $tmp;
        }

        return $ret;
    }

    // 2abcdefedcxy
    // aacabdkacaa
    // abcdbbfcba
    function longestPalindrome1($str) {
        $len = strlen($str);
        for ($i = $len; $i > 0; $i--) {
            for ($j=0; $j < $len; $j++) {
                $tmp = substr($str, $j, $i);
                if (strlen($tmp) < $i) {
                    break;
                }
                for ($k = 0; $k < ceil($i/2)+1; $k++) { 
                    if ($tmp[$k] !== $tmp[$i-$k-1]) {
                        break;
                    }

                    if ($k >= $i-$k-1) {
                        return $tmp;
                    }
                }
            }
        }
    }

    /**
     * 分割回文串
     * @param String $s
     * @return String[][]
     */
    function partition($str) {
        $len = strlen($str);
        $ret = [];
        for ($i = $len; $i > 0; $i--) {
            for ($j=0; $j < $len; $j++) {
                $tmp = substr($str, $j, $i);
                if (strlen($tmp) < $i) {
                    break;
                }
                for ($k = 0; $k < ceil($i/2)+1; $k++) { 
                    if ($tmp[$k] !== $tmp[$i-$k-1]) {
                        break;
                    }

                    if ($k >= $i-$k-1) {
                        $ret[] = $tmp;
                    }
                }
            }
        }

        return $ret;
    }

    function partition1($str, $index = 0) {
        $result = "";
        $path = "";

        // 回溯终止
        if ($index >= strlen($str)) {
            return;
        }

        for ($i = $index; $i < strlen($str); $i++) { 
            if ($this->isPalindrome($str, $index, $i)) {
                $tmp = substr($str, $index, $i - $index + 1);
            }
        }
    }

    // 判断是否回文子串
    function isPalindrome($str, $start, $end) {
        for ($i=$start, $j=$end; $i < $j; $i++, $j--) { 
            if ($str[$j] != $str[$j]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，
     * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     * 
     * 二分法的条件
     * 1. 有序
     * 2. 元素不重复
     * 
     * 二分法的要点就是对区间的定义
     * 
     * 区间的定义就是不变量。
     * 要在二分查找的过程中，保持不变量。
     * 就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
     * 
     * 写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)
     * 
     * 写法1：[left, right]
     * 要点：
     * 1. while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
     * 2. if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，
     *    那么接下来要查找的左区间结束下标位置就是 middle - 1
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search1(array $nums, $target) {
        $left = 0;
        $right = count($nums) - 1; // 定义target在左闭右闭的区间里，即：[left, right]，右边界存在
        while ($left <= $right) {
            $middle = $left + (($right - $left) >> 1); // 防止溢出 等同于(left + right)/2
            if ($nums[$middle] > $target) {
                $right = $middle - 1;
            } elseif ($nums[$middle] < $target) {
                $left = $middle + 1;
            } else {
                return $middle;
            }
        }

        return -1;
    }

    /*
     * 写法2：[left, right)
     * 要点：
     * 1. while (left < right) 要使用 < ，因为left == right是无意义的，所以使用 <
     * 2. if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，
     *    那么接下来要查找的左区间结束下标位置就是 middle - 1
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search2(array $nums, $target) {
        $left = 0;
        $right = count($nums); // 定义target在左闭右开的区间里，即：[left, right)，右边界不存在
        while ($left < $right) {
            // 位运算 a << b a左移b次，相当于除以2^b
            // 位运算 a >> b a右移b次，相当于除以2^b
            $middle = $left + (($right - $left) >> 1);
            if ($nums[$middle] > $target) {
                $right = $middle;
            } elseif ($nums[$middle] < $target) {
                $left = $middle + 1;
            } else {
                return $middle;
            }
        }

        return -1;
    }

    /**
     * 题目：在排序数组中查找元素的第一个和最后一个位置
     * 
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回[-1, -1]。
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function searchRange(array $nums, $target) {
        $left = 0;
        $right = count($nums) - 1;
        $start = -1;
        $end = -1;        
        while ($left <= $right) {
            $middle = $left + (($right - $left) >> 1);            
            if ($nums[$middle] > $target) {
                $right = $middle - 1;
            } elseif ($nums[$middle] < $target) {
                $left = $middle + 1;
            } else {                
                break;
            }
        }

        $start = $end = $middle;
        $i = 0;
        while ($nums[$middle - $i] == $nums[$middle] && ($middle - $i) >= $left) {
            $start = $middle - $i;
            $i++;
        }
        $i = 0;
        while ($nums[$middle + $i] == $nums[$middle] && ($middle + $i) <= $right) {
            $end = $middle + $i;
            $i++;
        }

        return [$start, $end];
    }

    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
     * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 
     * 分析： 有序且不重复, 考虑二分查找
     * 1. 目标值在所有元素前面
     * 2. 目标值在所有元素后面
     * 3. 目标值等于某元素
     * 4. 目标值在已知元素之间
     * 
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function searchInsert($nums, $target) {
        $n = count($nums);
        $left = 0;
        $right = $n - 1;
        while ($left <= $right) {
            $middle = $left + (($right - $left) >> 1);
            if ($nums[$middle] > $target) {
                $right = $middle - 1;
            } elseif ($nums[$middle] < $target) {
                $left = $middle + 1;
            } else {
                return $middle;
            }
        }

        // 目标值在所有元素前面　return $right + 1(循环终止时$right = -1)
        // 目标值在所有元素后面　return $right + 1
        // 目标值等于某元素　　　return $middle
        // 目标值在已知元素之间　return $right + 1
        return $right + 1;
    }

    /**
     * 
     * 给你一个非负整数x ，计算并返回 x 的算术平方根 。
     * 由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
     * 分析：结果一定是0-x之间的值，可以用二分逼近法
     * 
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x) {
        $left = 1;
        $right = $x;
        while ($left <= $right) {
            $middle = $left + (($right - $left) >> 1);
            if ($middle * $middle > $x) {
                $right = $middle - 1;
            } elseif ($middle * $middle < $x) {
                $left = $middle + 1;
            } else {
                return $middle;
            }
        }

        return $right;
    }

    /**
     * 有效的完全平方数
     * 
     * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
     * 分析：上题的反例
     * 
     * @param Integer $num
     * @return Boolean
     */
    function isPerfectSquare($num) {
        $left = 1;
        $right = $num;
        while ($left <= $right) {
            $middle = $left + (($right - $left) >> 1);
            if ($middle * $middle > $num) {
                $right = $middle - 1;
            } elseif ($middle * $middle < $num) {
                $left = $middle + 1;
            } else {
                return true;
            }
        }

        return false;
    }

    /**
     * 375. 猜数字大小 II
     * 
     * 我们正在玩一个猜数游戏，游戏规则如下：
     * 我从1到 n 之间选择一个数字。
     * 你来猜我选了哪个数字。
     * 如果你猜到正确的数字，就会 赢得游戏 。
     * 如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
     * 每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会 输掉游戏 。
     * 给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。
     * 
     * @param Integer $n
     * @return Integer
     */
    function getMoneyAmount($n) {
        $left = 1;
        $res = 0;
        while ($n >= $left) {
            $left = floor(($left + $n)/2);
            $res += $left;
        }
        return $res;
    }
}
// 0123
// 3 => [0, 3) => 1
// 4 => [0, 4) => 1

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;

// $result1 = $solution->divide(-pow(2, 31), -1);
// $result1 = $solution->divide(-pow(2, 31), -1);
// $result1 = $solution->divide(-2147483647, -1);
// $result1 = $solution->divide(483222647, 2);
// $result1 = $solution->myfunc1((int)$a, (int)$b);

// $result1 = $solution->longestPalindrome1($a);
$nums = [-1,0,3,5,9,12,14,17,22,25,66,88,123,157,189,231,251,267,299,999];
$target = 189;
// $result = $solution->search1($nums, $target);
// $result = $solution->search2($nums, $target);

// $nums = [-1,0,3,5,9,12,14,17,22,25,66,88,88,123,157,189,231,231,251,267,299,999];
// $target = 88;
// $nums = [0,0,0,1,2,3];
// $target = 0;
// $result = $solution->searchRange($nums, $target);

// $result = $solution->mySqrt($a);
// $result = $solution->mySqrt(100);
$result = $solution->isPerfectSquare($a) ? "{$a}是完全平方数" : "{$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>";