eleven26
0%

Posted on Edited on

bash 脚本：

script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/bin/sh
OSX_VERS=$(sw_vers -productVersion | awk -F "." '{print $2}')

# Get Xcode CLI tools
# https://devimages.apple.com.edgekey.net/downloads/xcode/simulators/index-3905972D-B609-49CE-8D06-51ADC78E07BC.dvtdownloadableindex
# https://developer.apple.com/downloads/index.action
TOOLS=clitools.dmg
if [ ! -f "$TOOLS" ]; then
  if [ "$OSX_VERS" -eq 7 ]; then
	  DMGURL=http://devimages.apple.com/downloads/xcode/command_line_tools_for_xcode_os_x_lion_april_2013.dmg
  elif [ "$OSX_VERS" -eq 8 ]; then
  	  DMGURL=http://devimages.apple.com/downloads/xcode/command_line_tools_for_xcode_os_x_mountain_lion_april_2013.dmg
  elif [ "$OSX_VERS" -eq 9 ]; then
	  DMGURL=http://adcdownload.apple.com/Developer_Tools/command_line_tools_os_x_mavericks_for_xcode__late_october_2013/command_line_tools_os_x_mavericks_for_xcode__late_october_2013.dmg
  elif [ "$OSX_VERS" -eq 10 ]; then
	  DMGURL=http://adcdownload.apple.com/Developer_Tools/Command_Line_Tools_OS_X_10.10_for_Xcode_6.3.2/commandlinetoolsosx10.10forxcode6.3.2.dmg
  elif [ "$OSX_VERS" -eq 11 ]; then
	  DMGURL=http://adcdownload.apple.com/Developer_Tools/Command_Line_Tools_OS_X_10.11_for_Xcode_7.3.1/Command_Line_Tools_OS_X_10.11_for_Xcode_7.3.1.dmg
  elif [ "$OSX_VERS" -eq 12 ]; then
	  DMGURL=http://adcdownload.apple.com/Developer_Tools/Command_Line_Tools_macOS_10.12_for_Xcode_8.1/Command_Line_Tools_macOS_10.12_for_Xcode_8.1.dmg
  elif [ "$OSX_VERS" -eq 14 ]; then
	  DMGURL=https://download.developer.apple.com/Developer_Tools/Command_Line_Tools_for_Xcode_11_GM_Seed/Command_Line_Tools_for_Xcode_11_GM_Seed.dmg
  elif [ "$OSX_VERS" -eq 15 ]; then
	  DMGURL=https://download.developer.apple.com/Developer_Tools/Command_Line_Tools_for_Xcode_12.2/Command_Line_Tools_for_Xcode_12.2.dmg
  fi
  curl "$DMGURL" -o "$TOOLS"
fi
TMPMOUNT=`/usr/bin/mktemp -d /tmp/clitools.XXXX`
hdiutil attach "$TOOLS" -mountpoint "$TMPMOUNT"
installer -pkg "$(find $TMPMOUNT -name '*.mpkg' -o -name '*.pkg')" -target /
hdiutil detach "$TMPMOUNT"
rm -rf "$TMPMOUNT"
rm "$TOOLS"
exit
  1. 把上面脚本保存为 install.sh
  2. 执行 sudo sh install.sh

Posted on Edited on

实现思路

我们按照普通二分查找的方式获取中点，这个时候和普通有序数组有一个不一样的地方，有可能这个数组不是单调递增的。 1. 如果是单调递增的，按照普通二分查找的方式查找即可 2. 如果不是单调递增的，判断 value 是否在这个区间内，如果不在，返回 -1 即可。判断方法比较简单，如果 $value < $array[$low] 并且 $value > $array[$high] 那就说明不在该区间内（因为是循环有序，比如[5,6,1]里面查找2）。 3. 如果在这个区间内，还需要判断是否等于临界点，因为 $array[$low] 或者 $array[$high] 有可能等于 value，比如 [5, 6, 1] 里面查找 1

PHP 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
$arr1 = [4, 5, 6, 1, 2, 3];

function bsearch($array, $value)
{
    $low = 0;
    $high = count($array) - 1;

    while ($low <= $high) {
        $mid = intval(($low + $high) / 2);

        if ($array[$low] <= $array[$high]) {
            if ($value > $array[$mid]) {
                $low = $mid + 1;
            } else if ($value < $array[$mid]) {
                $high = $mid - 1;
            } else {
                return $mid;
            }
        } else {
            // 不是递增区间
            if ($value == $array[$high]) return $high;
            if ($value == $array[$low]) return $low;

            if ($value > $array[$high] && $value < $array[$low]) {
                return -1;
            } else if ($value < $array[$high]) {
                $high--;
            } else {
                $low++;
            }
        }
    }

    return -1;
}

var_dump(bsearch($arr1, 2));

Posted on Edited on

问题

  1. 在有序数组中查找第一个值等于 $value 的元素
  2. 在有序数组中查找最后一个值等于 $value 的元素
  3. 在有序数组中查找第一个值大于等于 $value 的元素
  4. 在有序数组中查找最后一个值小于等于 $value 的元素

在有序数组中查找第一个值等于 $value 的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
$array = [1, 2, 3, 4, 5, 5, 5, 5, 7];

// 1. 在有序数组中查找第一个值等于 $value 的元素
function bsearch1($arr, $value)
{
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        // 最终只剩两个元素的时候，$mid 指向小的元素
        $mid = intval(($low + $high) / 2);

        if ($arr[$mid] < $value) {
            $low = $mid + 1;
        } else if ($arr[$mid] > $value) {
            $high = $mid - 1;
        } else {
            // 如果 mid == 0，则说明只有一个元素，则直接返回 0。
            // 判断 mid 的前一个元素是否不等于 value，如果是，则说明 mid 就是第一个等于 value 的元素
            if ($mid == 0 || $arr[$mid - 1] != $value) {
                return $mid;
            }
            $high = $mid - 1;
        }
    }

    return -1;
}

var_dump(bsearch1($array, 5));

在有序数组中查找最后一个值等于 $value 的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
$array = [1, 2, 3, 4, 5, 5, 5, 5, 7];

// 2. 在有序数组中查找最后一个值等于 $value 的元素
function bsearch2($arr, $value)
{
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        // 最终只剩两个元素的时候，$mid 指向小的元素
        $mid = intval(($low + $high) / 2);

        if ($arr[$mid] < $value) {
            $low = $mid + 1;
        } else if ($arr[$mid] > $value) {
            $high = $mid - 1;
        } else {
            // 如果 mid 是最后一个元素，则直接返回 count($arr) - 1。
            // 如果不是，判断 $arr[mid + 1] 的值是否不等于 value，如果不等于 value，则说明 $arr[$mid] 就是最后一个等于 value 的元素了
            if ($mid == count($arr) - 1 || $arr[$mid + 1] != $value) {
                return $mid;
            }

            $low = $mid + 1;
        }
    }

    return -1;
}

var_dump(bsearch2($array, 5));

在有序数组中查找第一个值大于等于 $value 的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
$array = [1, 2, 3, 3, 5, 5, 5, 5, 7];

// 3. 在有序数组中查找第一个值大于等于 $value 的元素
function bsearch3($arr, $value)
{
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        // 最终只剩两个元素的时候，$mid 指向小的元素
        $mid = intval(($low + $high) / 2);

        if ($arr[$mid] < $value) {
            $low = $mid + 1;
        } else {
            // 如果 mid == 0，说明只有一个元素，直接返回 0；
            // 否则，判断 mid 的前一个元素是否小于 value，如果是，则返回 mid。
            if ($mid == 0 || $arr[$mid - 1] < $value) {
                return $mid;
            }

            $high = $mid - 1;
        }
    }

    return -1;
}

var_dump(bsearch3($array, 3));

在有序数组中查找最后一个值小于等于 $value 的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
$array = [1, 2, 3, 3, 5, 5, 5, 5, 7];

// 4. 在有序数组中查找最后一个值小于等于 $value 的元素
function bsearch4($arr, $value)
{
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        // 最终只剩两个元素的时候，$mid 指向小的元素
        $mid = intval(($low + $high) / 2);

        if ($arr[$mid] > $value) {
            $high = $mid - 1;
        } else {
            // 如果是最后一个元素，则直接返回 count($arr) - 1；
            // 否则，判断下一个元素是否大于 value，如果是，则返回 mid。
            if ($mid == count($arr) - 1 || $arr[$mid + 1] > $value) {
                return $mid;
            }

            $low = $mid + 1;
        }
    }

    return -1;
}

var_dump(bsearch4($array, 3));

Posted on Edited on

如何使用二分查找法求 8 的平方根？保留 6 位小数。

假设只精确到整数部分

如果我们只需要计算整数部分的话，那很好实现，假设要开平方的数为 value，依次二分，直到找到某一个整数的平方小于等于 value，然后这个整数加1的平方大于 value，那这个数就是开平方结果的整数部分了。

下面为 PHP 实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function calcInteger($value, $low, $high)
{
    $mid = round(($low + $high) / 2);
    $mid2 = $mid * $mid;

    if ($mid2 > $value) {
        if (($mid - 1) * ($mid - 1) <= $value) return $mid - 1;
        return calcInteger($value, 0, $mid);
    } else if ($mid2 < $value) {
        if (($mid + 1) * ($mid + 1) >= $value) return $mid;
        return calcInteger($value, $mid, $high);
    } else {
        return $mid;
    }
}

var_dump(calcInteger(8, 0, 8)); // 2

实现思路：

  1. 如果二分的中点的平方大于 value，说明整数部分肯定位于中点之前。这个时候需要特别注意的是，不能直接 calcInteger($value, 0, $mid - 1) 这样使用 $mid - 1 作为下一次二分查找区间的上限，因为如果开平方结果带有小数的情况下，最终会陷入死循环（具体表现为，不断地在两个区间之间循环，比如 [0, 3], [2, 3]）。
  2. 如果位于中点之前，那么先判断 中点-1 的平方是否不大于 value，那说明这个 中点-1 就是开平方结果的整数部分了
  3. 中点的平方小于 value 的情况也类似
  4. 如果中点的平方恰好等于 value，那这个中点就是整数部分了。

再假设一下，精确到 1 位小数

这也好办，只要我们做平方操作的时候精确到 1 位小数就行了。如果中位数的平方大于 value，这个时候就计算一下 $mid - 0.1 的平方，跟 value 做比较。我们在这种情况下，假设下一个比 $mid 小的数字为 $mid - 0.1。

将一个整数之间的区间再细分成十份就很好理解了。

下面为 PHP 实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function calcInteger($value, $low, $high)
{
    $mid = round(($low + $high) / 2, 1);
    $mid2 = $mid * $mid;

    if ($mid2 > $value) {
        if (($mid - 0.1) * ($mid - 0.1) <= $value) return $mid - 0.1;
        return calcInteger($value, 0, $mid);
    } else if ($mid2 < $value) {
        if (($mid + 0.1) * ($mid + 0.1) >= $value) return $mid;
        return calcInteger($value, $mid, $high);
    } else {
        return $mid;
    }
}

var_dump(calcInteger(8, 0, 8)); // 2.8

回到正题

按上一小节说的，我们如果要保留 6 位小数，则可以将原来一个整数的区间想象成有 1000000（10的6次方） 个小区间，比较的过程加减的粒度就是 10^-6 了。

下面为 PHP 实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 求 3 的平方根，保留 6 位小数
$value = 8;
// 2.8284271247462

function calc($value, $low, $high, $float)
{
    $mid = round(($low + $high) / 2, $float);
    $mid2 = $mid * $mid;

    // 依次确定每一位小数
    $v = 1 / pow(10, $float);

    if ($mid2 > $value) {
        if (($mid - $v) * ($mid - $v) <= $value) return $mid - $v;
        return calc($value, 0, $mid, $float);
    } else if ($mid2 < $value) {
        if (($mid + $v) * ($mid + $v) >= $value) return $mid;
        return calc($value, $mid, $high, $float);
    } else {
        return $mid;
    }
}

var_dump(calc($value, 0, $value, 6)); // 2.828427

非递归实现

非递归实现的方式也挺简单的，只要在 $mid * $mid > $value 和 $mid * $mid < $value 两种情况下，分别修改一下区间的上限、下限即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 求 8 的平方根，保留 6 位小数
$value = 8;
// 2.8284271247462

function calc($value, $low, $high, $float)
{
    // 依次确定每一位小数
    $v = 1 / pow(10, $float);

    while (true) {
        $mid = round(($low + $high) / 2, $float);
        $mid2 = $mid * $mid;

        if ($mid2 > $value) {
            if (($mid - $v) * ($mid - $v) <= $value) return $mid - $v;
            $high = $mid;
        } else if ($mid2 < $value) {
            if (($mid + $v) * ($mid + $v) >= $value) return $mid;
            $low = $mid;
        } else {
            return $mid;
        }
    }
}

var_dump(calc($value, 0, $value, 6)); // 2.828427

总结

本文求平方根的思想在于，将原来一个整数的区间拆分成多个小的区间，然后在所有的这些小区间里面依次二分找到最终合适的那个数。

Posted on Edited on

  1. 打开 PHPStorm 的默认安装目录 C:\Program Files\JetBrains\PhpStorm 2021.1.2\jbr\lib。

  2. 将里面的 fontconfig.properties.src 复制一份，命名为 fontconfig.properties

  3. 打开 fontconfig.properties，将下面两个键对应的值修改为 Microsoft YaHei

1
2
allfonts.chinese-ms936=Microsoft YaHei
allfonts.chinese-gb18030=Microsoft YaHei
  1. 最后，重启 PHPStorm 即可