wordpress升级5.1后的一系列坑

wordpress自动更新至5.1版本后,提示升级PHP可提高性能。于是我开始对服务器进行了PHP升级···这里我升级至php7.2.16版本,升级历程如下:

检查wordpress上已安装插件是否支持PHP7.2

  • 在wordpress后台安装该插件:PHP Compatibility Checker,启用后对已安装插件进行扫描,可选择待检查支持的PHP版本,使用较为简单,此处不赘述。

安装PHP7.2版本

cd /usr/local/
#解压安装包
tar -xzvf php-7.2.16.tar.gz
cd php-7.2.16
#查看下帮助
./configure   --help
#执行编译
./configure --prefix=/usr/local/php \
 --with-curl \
 --with-freetype-dir \
 --with-gd \
 --with-gettext \
 --with-iconv-dir \
 --with-kerberos \
 --with-libdir=lib64 \
 --with-libxml-dir \
 --with-mysqli \
 --with-openssl \
 --with-pcre-regex \
 --with-pdo-mysql \
 --with-pdo-sqlite \
 --with-pear \
 --with-png-dir \
 --with-xmlrpc \
 --with-xsl \
 --with-zlib \
 --enable-fpm \
 --enable-bcmath \
 --enable-libxml \
 --enable-inline-optimization \
 --enable-gd-native-ttf \
 --enable-mbregex \
 --enable-mbstring \
 --enable-opcache \
 --enable-pcntl \
 --enable-shmop \
 --enable-soap \
 --enable-sockets \
 --enable-sysvsem \
 --enable-xml \
 --enable-zip
 #执行过程中可能会提示缺少依赖库,使用yum安装依赖库,基本包含如下:
 yum -y install libjpeg libjpeg-devel libpng libpng-devel freetype freetype-devel libxml2 libxml2-devel pcre-devel curl-devel libxslt-devel
 #上述操作无误后,编译安装:
 make &&  make install
 #配置文件
cp php.ini-development /usr/local/php-7.2.16/lib/php.ini
cp /usr/local/php-7.2.16/etc/php-fpm.conf.default /usr/local/php-7.2.16/etc/php-fpm.conf
cp /usr/local/php-7.2.16/etc/php-fpm.d/www.conf.default /usr/local/php-7.2.16/etc/php-fpm.d/www.conf
cp -R ./sapi/fpm/php-fpm /etc/init.d/php-fpm
#若已有旧版本运行,先杀掉旧的php进程
ps -ef | grep "php-fpm"
#找到对应pid后,执行
kill 'pid'
#启动
/etc/init.d/php-fpm
  • 此时服务器已完成php升级,但是竟然发现升级后博客无法访问,页面提示数据库无法连接的错误。检查下数据库配置没错,看了下wordpress5.1的wp-db.php页面,发现更新后的wordpress对mysql和mysqli扩展都支持,也就是说问题不在wordpress上,那看来就是php7对旧版本的mysql扩展不支持了。原来php7采用了mysqli和mysqlnd扩展,默认已不再支持mysql扩展···然鹅我的服务器mysql还是5.0.1版本···于是我尝试了还原mysql扩展,操作如下:

找回mysql扩展

#编写一个php页面检查phpinfo及能否连接mysql
<?php
echo phpinfo();
$link=MySQLi_connect('localhost','J3gm2lWz','uDwSOHvv11M7','J3gm2lWz');
if(!$link) echo "Error !";
else echo "Ok!";
MySQLi_close();
?>
#将此页面放在/yjdata/www/www/下,即项目根目录下,在浏览器上访问即可验证是否实现对mysql的连接~

访问网站是否完成升级

  • 正常的话升级就结束了,而且我发现性能的确有了很大提升,之前整个网站访问延时都是秒级,现在似乎大部分都在1秒内即可加载完成了。而且对接wordpress的微信小程序,之前经常性的刷不出页面,无法访问,现在基本不再遇到了。丝滑到底~哈哈~
  • 我这里使用了wp-photo-album插件, 升级后还遇到了一个错误:网站首页最上栏出现错误信息Warning: fopen(/yjdata/www/www/wp-content/plugins/wp-photo-album-plus/dynamic/wppa-init.zh.js): failed to open stream: Permission denied in /yjdata/www/www/wp-content/plugins/wp-photo-album-plus/wppa-wrappers.php on line 233,看起来是文件/文件夹权限问题,我这里暴力对整个文件夹采用了chmod +777 /yjdata/www/www/wp-content/plugins/wp-photo-album-plus/*操作,立马解决了,但我的wordpress其实还有一个遗留问题就是下载更新插件,上传多媒体文件都需要输入FTP账户密码,显然是隶属于的用户和组有问题,没有写权限,不过一直还没仔细排查处理。感觉这个wp-photo-album插件问题也和遗留问题类似,尚待解决啊!

docker镜像操作相关shell脚本

deleteRegistryImages.sh

传参说明

  • num:仓库中各项目保留镜像数
  • oneProject:可选参数,表示只删除仓库中当前项目的历史镜像

功能说明

  • 遍历仓库中各项目或指定项目,保留num个镜像,其余各镜像均删除,每次删除镜像后,执行垃圾收集。执行日志将写入/.deleteRegistryImage.log文件中
#! /bin/bash

num=$1
oneProject=$2
registryUrl="127.0.0.1:5000"

get_image_digest(){
   sed -n '/Docker-Content-Digest/{s/\S*Docker-Content-Digest: //; s/\r//; p;}' /.image.txt
}

startTime=`date +'%Y-%m-%d %H:%M:%S'`
echo "************************************************" | tee -a /.deleteRegistryImage.log
echo "$startTime使用$(pwd)/下的脚本执行了删除仓库镜像操作:" | tee -a /.deleteRegistryImage.log

if [ -z "$num" ]; then
        num=2;
fi
echo "传入参数:num=$num(若未传入,默认为2),oneProject=$oneProject 并开始执行:" | tee -a /.deleteRegistryImage.log

curl -k https://$registryUrl/v2/_catalog 2>/dev/null >>/.repositories.txt
sed  -i "s/\"//g" /.repositories.txt
cat /.repositories.txt | while IFS= read -r line; do
        temp=$(echo $line | cut -d'[' -f2)
        repositories=$(echo $temp | cut -d ']' -f1)
        echo "仓库中包含以下项目:$repositories" | tee -a /.deleteRegistryImage.log
        str=${repositories//,/ }
        arr=($str)
        if [ -n "$oneProject" ]; then
                curl -k https://$registryUrl/v2/$oneProject/tags/list 2>/dev/null >>/.$oneProject.txt
                sed  -i "s/\"//g" /.$oneProject.txt
                cat /.$oneProject.txt | while IFS= read -r line1; do
                        temp1=$(echo $line1 | cut -d'[' -f2)
                        tags=$(echo $temp1 | cut -d ']' -f1)
                        echo "删除前仓库中$oneProject项目包含的镜像如下:$tags" | tee -a /.deleteRegistryImage.log
                        str1=${tags//,/ }
                        tagArr=($str1)
                        tagArrLength=${#tagArr[*]}
                        echo "仓库中$project项目包含$tagArrLength个镜像。" | tee -a /.deleteRegistryImage.log
                        if [ $tagArrLength -gt $num ]; then 
                                for((i=0; i<${#tagArr[*]}-$num; i++));do 
                                        #根据digest删除仓库里的镜像操作在这里
                                        imageTag=${tagArr[$i]}
                                        echo "根据名字和镜像tag获取digest" | tee -a /.deleteRegistryImage.log
                                        curl --header "Accept:application/vnd.docker.distribution.manifest.v2+json" -I -XGET -k https://$registryUrl/v2/$oneProject/manifests/$imageTag  2>/dev/null >>/.image.txt
                                        cat /.image.txt | grep Docker-Content-Digest | while IFS= read -r line2; do
                                                lineName=$(echo $line2 | cut -d':' -f1)
                                                if [ $lineName == "Docker-Content-Digest"  ];then
                                                   imageDigest=$(get_image_digest)
                                                   echo "删除镜像:$imageTag $imageDigest" | tee -a /.deleteRegistryImage.log
                                                   curl -XDELETE -k https://$registryUrl/v2/$oneProject/manifests/$imageDigest
                                                fi
                                        done
                                        rm -f /.image.txt
                                done
                                echo "$oneProject项目已删除完毕,仓库中保留最近上传的的$num个镜像。" | tee -a /.deleteRegistryImage.log
                        else
                                echo "仓库中$oneProject项目的镜像数为$tagArrLength,不大于$num,不执行删除操作!" | tee -a /.deleteRegistryImage.log
                        fi
                        rm -f /.$oneProject.txt
                done
        else
                for project in ${arr[*]}do
                        echo "删除仓库中的$project项目镜像:" | tee -a /.deleteRegistryImage.log
                        curl -k https://$registryUrl/v2/$project/tags/list 2>/dev/null >>/.$project.txt
                        sed  -i "s/\"//g" /.$project.txt
                        cat /.$project.txt | while IFS= read -r line1; do
                                temp1=$(echo $line1 | cut -d'[' -f2)
                                tags=$(echo $temp1 | cut -d ']' -f1)
                                echo "删除前仓库中$project项目包含的镜像如下:$tags" | tee -a /.deleteRegistryImage.log
                                str1=${tags//,/ }
                                tagArr=($str1)
                                tagArrLength=${#tagArr[*]}
                                echo "仓库中$project项目包含$tagArrLength个镜像。" | tee -a /.deleteRegistryImage.log
                                if [ $tagArrLength -gt $num ]; then
                                        echo "根据名字和镜像tag获取digest" | tee -a /.deleteRegistryImage.log
                                        for((i=0; i<${#tagArr[*]}-$num; i++));do 
                                                #根据digest删除仓库里的镜像操作在这里
                                                imageTag=${tagArr[$i]}
                                                curl --header "Accept:application/vnd.docker.distribution.manifest.v2+json" -I -XGET -k https://$registryUrl/v2/$project/manifests/$imageTag  2>/dev/null >>/.image.txt
                                                cat /.image.txt | grep Docker-Content-Digest | while IFS= read -r line2; do
                                                        lineName=$(echo $line2 | cut -d':' -f1)
                                                        if [ $lineName == "Docker-Content-Digest"  ];then
                                                           imageDigest=$(get_image_digest)
                                                           echo "删除镜像:$imageTag $imageDigest" | tee -a /.deleteRegistryImage.log
                                                           curl -XDELETE -k https://$registryUrl/v2/$project/manifests/$imageDigest
                                                        fi
                                                done
                                                rm -f /.image.txt
                                        done
                                        echo "$project项目已删除完毕,仓库中保留最近上传的的$num个镜像。" | tee -a /.deleteRegistryImage.log
                                else
                                        echo "仓库中$project项目的镜像数为$tagArrLength,不大于$num,不执行删除操作!" | tee -a /.deleteRegistryImage.log
                                fi
                                rm -f /.$project.txt
                        done
                done
        fi
done
rm -f /.repositories.txt

echo "删除镜像操作结束!开始执行垃圾清理操作···" | tee -a /.deleteRegistryImage.log

docker exec -i itacRegistry /bin/sh -c "cd /var/lib/registry && registry garbage-collect /etc/docker/registry/config.yml"

echo "垃圾清理操作结束!脚本执行结束!" | tee -a /.deleteRegistryImage.log
echo -e "\n\n\n\n" | tee -a /.deleteRegistryImage.log

produceCloud.sh

传参说明

  • date:待保存镜像日期
  • oneItem:待保存镜像项目名称

功能说明

  • 根据参数制作云端完整安装包,或保存单个项目镜像
#!/bin/bash

date=$1
oneItem=$2
registry="127.0.0.1:5000"
arr=(apiserv itac itactask portal-demo portal-largescreen portal-promotion vpn)

if [ -z "$oneItem" ]; then 
        rm -rf cloud
        mkdir cloud
        cd cloud
        mkdir adesk-images
        for item in ${arr[@]}do
                echo $item
                docker pull $registry/$item:$item-release-$date
                docker tag $registry/$item:$item-release-$date $item:$item-release-$date
                docker save $item:$item-release-$date > adesk-images/$item-release-$date.tar
                docker rmi $registry/$item:$item-release-$date 
                docker rmi $item:$item-release-$date
        done
        cp -r /var/adesk-scripts .
        cp -r /var/adesk-ymls .
        tar -czvf cloud.tar.gz adesk-images/ adesk-scripts/ adesk-ymls/
else
        docker pull $registry/$oneItem:$oneItem-release-$date
        docker tag $registry/$oneItem:$oneItem-release-$date $oneItem:$oneItem-release-$date
        docker save $oneItem:$oneItem-release-$date > $oneItem-release-$date.tar
        docker rmi $registry/$oneItem:$oneItem-release-$date
        docker rmi $oneItem:$oneItem-release-$date

fi

produceAdesk.sh

功能说明

  • 制作探针完整安装包
#!/bin/bash

time=$(date +%Y%m%d)
docker ps | while IFS= read -r line ; do
        image=$(echo $line | cut -d ' ' -f2)
        if [ $image != "ID" ]; then
                tag=$(echo $image | cut -d '/' -f2)
                name=$(echo $tag | cut -d ':' -f1)
                tarName=$(echo $image | cut -d ':' -f3)
                docker tag  $image $tag
                mkdir $name
                docker save $tag > ./$name/$tarName.tar
                docker rmi $tag
        fi
done
cp -r /var/tmp/deploy .
tar -czvf Adesk-R2.0.0-$time.tar.gz deploy/ splus/ probe/ zabbix/ agent/

ntp.sh

功能说明

  • 安装NTP服务后,配置服务器与ntpServer时钟源同步
#!/bin/bash

yum localinstall -y *.rpm
# 设置本地时区
timedatectl set-timezone "Asia/Shanghai"
# 设置硬件时钟以协调世界时(UTC)
timedatectl set-local-rtc 0
# 设置硬件时间,使得硬件时钟变为跟系统时间同步
hwclock --systohc

ntpServer=*.*.*.*

# 修改ntp配置
sed -i '/server 3/a\restrict '$ntpServer' nomodify notrap noquery'  /etc/ntp.conf
sed -i '/server 3/a\server '$ntpServer''  /etc/ntp.conf
sed -i '/centos.pool.ntp.org/d'  /etc/ntp.conf
# 开启NTP服务
systemctl start ntpd
systemctl enable ntpd

# 关闭chrony服务,避免系统重启后NTP服务无法启动
systemctl stop chronyd
systemctl disable chronyd

pushAgentImage.sh

参数说明:

  • edition:镜像制作版本

– registryIp:镜像推送至的仓库

功能说明:

  • 在服务器上制作探针镜像,制作前清除本地镜像,清除仓库中同标签镜像,制作后再次清除本地镜像。以/.temp.ini作为“锁”,保证该脚本被多人使用时不冲突。
#!/bin/bash

set +e

edition=$1
registryIp=$2

while [ -f "/.temp.ini" ];do
        sleep 5
                echo "someone is running script to build and push docker image, so waiting for the finish..."
done

touch /.temp.ini

getVersion(){
    cat version.txt | grep agent_"$edition" | while IFS= read -r line; do
       version=$(echo $line | cut -d'=' -f2)
       echo $version
    done
}

version=$(getVersion)

get_image_version() {
    unzip -q Adesk.war WEB-INF/conf/productConf/Adesk/product.xml
    sed -n '/productVersion/{s/\S*<productVersion value="//; s/"\/>\r//; s/\t//; p;}' WEB-INF/conf/productConf/Adesk/product.xml
    rm -rf WEB-INF
}

get_image_digest(){
   sed -n '/Docker-Content-Digest/{s/\S*Docker-Content-Digest: //; s/\r//; p;}' /.image.txt
}


imageName="*.*.*.*:5000/agent"
imageVer=$(get_image_version)
imageTag="agent-$imageVer-$(date +%Y%m%d)"
imageNameTag="$imageName:$imageTag"

echo "delete the last image of today"
docker rmi "$imageNameTag"

echo "Building docker image \"$imageNameTag\"."
docker build -t "$imageNameTag" .

if [ -n "$registryIp" ]; then
        echo "add $registryIp *.*.*.* into /etc/hosts"
        sed -i "/^::1/a $registryIp *.*.*.*" /etc/hosts

        curl --header "Accept:application/vnd.docker.distribution.manifest.v2+json" -I -XGET -k https://*.*.*.*:5000/v2/agent/manifests/$imageTag 2>/dev/null >>/.image.txt
        cat /.image.txt | grep Docker-Content-Digest | while IFS= read -r line; do
                lineName=$(echo $line | cut -d':' -f1)
                if [ $lineName == "Docker-Content-Digest"  ];then
                   imageDigest=$(get_image_digest)
                   echo $imageDigest
                   echo "delete the last image in registry of today"
                   curl -XDELETE -k https://*.*.*.*:5000/v2/agent/manifests/$imageDigest
                fi
        done
        rm -f /.image.txt

        sleep 20
        echo "pushing docker image \"$imageNameTag\"."
        docker push "$imageNameTag"

        echo "remove $registryIp *.*.*.* in /etc/hosts"
        sed -i "/rois/d" /etc/hosts 
else
        SELFDIR=$(dirname "$(realpath -s "$0")")
        source $SELFDIR/data/read_ini.sh
        # parameter processing
        TEST_ENV_NAME=""
        while (( "$#" )); do
                if [ "$1" == "--test-env" ]; then
                        shift
                        TEST_ENV_NAME=$1
                        shift
                        continue
                fi
                shift
        done

        # do work
        for fullfn in `ls /etc/h3c/$edition/*.test-env`; do
                fn=$(basename $fullfn)
                name=${fn%%.*}
                if [ ! -z $TEST_ENV_NAME ] && [ "$TEST_ENV_NAME" != "$name" ]; then
                        continue
                fi
                read_ini $fullfn
                cloudIp=${INI__cloud__ip}
                cloudUser=${INI__cloud__user}
                cloudPwd=${INI__cloud__passwd}

                echo "add $cloudIp *.*.*.* into /etc/hosts"
                sed -i "/^::1/a $cloudIp *.*.*.*" /etc/hosts

                curl --header "Accept:application/vnd.docker.distribution.manifest.v2+json" -I -XGET -k https://*.*.*.*:5000/v2/agent/manifests/$imageTag 2>/dev/null >>/.image.txt
                cat /.image.txt | grep Docker-Content-Digest | while IFS= read -r line; do
                        lineName=$(echo $line | cut -d':' -f1)
                        if [ $lineName == "Docker-Content-Digest"  ];then
                           imageDigest=$(get_image_digest)
                           echo $imageDigest
                           echo "delete the last image in registry of today"
                           curl -XDELETE -k https://*.*.*.*:5000/v2/agent/manifests/$imageDigest
                        fi
                done
                rm -f /.image.txt

                echo "pushing docker image \"$imageNameTag\"."
                docker push "$imageNameTag"

                sleep 20
                echo "remove $cloudIp *.*.*.* in /etc/hosts"
                sed -i "/rois/d" /etc/hosts 
        done
fi

echo "delete this image in local docker"
docker rmi "$imageNameTag"
rm -f /.temp.ini
echo "Complete."

二叉树的遍历、查找、插入、删除等

/********************************************
 * All Rights Reserved By www.laughing.ren
 * @author:Laughing_Lz
 * @version:2018年11月29日 下午11:33:24
 * ******************************************/
package ren.laughing.code.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树
 * 
 * @author Laughing_Lz
 *
 */
public class Tree {

    /**
     * 前序遍历二叉树
     * 
     * @param root
     */
    public static void preOrder(Node root{
        if (root == null) {
            return;
        }
        System.out.print(root.getValue() + " ");
        if (root.getLeft() != null) {
            preOrder(root.getLeft());
        }
        if (root.getRight() != null) {
            preOrder(root.getRight());
        }
    }

    /**
     * 中序遍历二叉树
     * 
     * @param root
     */
    public static void inOrder(Node root{
        if (root == null) {
            return;
        }
        if (root.getLeft() != null) {
            inOrder(root.getLeft());
        }
        System.out.print(root.getValue() + " ");
        if (root.getRight() != null) {
            inOrder(root.getRight());
        }
    }

    /**
     * 后序遍历二叉树
     * 
     * @param root
     */
    public static void postOrder(Node root{
        if (root == null) {
            return;
        }
        if (root.getLeft() != null) {
            postOrder(root.getLeft());
        }
        if (root.getRight() != null) {
            postOrder(root.getRight());
        }
        System.out.print(root.getValue() + " ");
    }

    /**
     * 层次遍历二叉树
     * 
     * @param root
     */
    public static void levelOrder(Node root{
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            System.out.print(currentNode.getValue() + " ");
            if (currentNode.getLeft() != null) {
                queue.add(currentNode.getLeft());
            }
            if (currentNode.getRight() != null) {
                queue.add(currentNode.getRight());
            }
        }
    }

    /**
     * 卡特兰数: 给定一组数据,比如 1,3,5,6,9,10。你来算算,可以构建出多少种不同的二叉树?
     * https://en.wikipedia.org/wiki/Catalan_number
     * 
     * @param numKeys
     * @return
     */
    public static int countTrees(int numKeys{
        if (numKeys <= 1) {
            return (1);
        } else {
            int sum = 0;
            int left, right, root;
            // 每次迭代,root节点的左右两颗子树的节点数不同--左子树的节点数从0到numKeys-1,右子树相反
            // 这样迭代结束后,各种情况便都覆盖全了;
            for (root = 1; root <= numKeys; root++) {
                left = countTrees(root - 1);
                right = countTrees(numKeys - root);

                // number of possible trees with this root == left*right
                sum += left * right;
            }
            return (sum);
        }
    }

    static class Node {
        private int value;
        private Node left;
        private Node right;

        public Node(int value{
            super();
            this.value = value;
        }

        public Node() {
            super();
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left{
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right{
            this.right = right;
        }

        public void setValue(int value{
            this.value = value;
        }

        public int getValue() {
            return this.value;
        }
    }

    /**
     * 二叉查找树的查找操作 二叉查找树:每个节点的左节点都比当前节点值小,右节点都比当前节点大值。
     * 
     * @param root
     * @param value
     * @return
     */
    public static Node find(Node root, int value{
        if (root == null) {
            return null;
        }
        while (root != null) {
            if (root.getValue() == value) {
                return root;
            } else if (root.getValue() > value) {
                root = root.getLeft();
            } else if (root.getValue() < value) {
                root = root.getRight();
            }
        }
        return null;
    }

    /**
     * 二叉查找树的插入操作
     * 
     * @param root
     * @param value
     */
    public static void insert(Node root, int value{
        if (root == null) {
            root = new Node(value);
        }
        while (root != null) {
            if (root.getValue() < value) {
                if (root.getRight() == null) {
                    root.setRight(new Node(value));
                    return;
                }
                root = root.getRight();
            } else if (root.getValue() > value) {
                if (root.getLeft() == null) {
                    root.setLeft(new Node(value));
                    return;
                }
                root = root.getLeft();
            }
        }
    }

    /**
     * 二叉查找树的删除操作,要注意有三种情况:1、待删除节点没有子节点2、待删除节点只有一个子节点(只需更新父节点)
     * 3、待删除节点有两个子节点(从待删除节点的左子节点中找出最大的节点替换,或从右子节点中找出最小的节点替换)
     * 
     * @param tree
     * @param data
     */
    public static void delete(Node tree, int data{
        Node p = tree; // p 指向要删除的节点,初始化指向根节点
        Node pp = null// pp 记录的是 p 的父节点
        while (p != null && p.getValue() != data) {
            pp = p;
            if (data > p.getValue())
                p = p.right;
            else
                p = p.left;
        }
        if (p == null)
            return// 没有找到

        // 要删除的节点有两个子节点
        if (p.left != null && p.right != null) { // 查找右子树中最小节点
            Node minP = p.right;
            Node minPP = p; // minPP 表示 minP 的父节点
            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            p.setValue(minP.getValue()); // 将 minP 的数据替换到 p 中
            p = minP; // 下面就变成了删除 minP 了
            pp = minPP;
        }

        // 删除节点是叶子节点或者仅有一个子节点
        Node child; // p 的子节点
        if (p.left != null)
            child = p.left;
        else if (p.right != null)
            child = p.right;
        else
            child = null;

        if (pp == null)
            tree = child; // 删除的是根节点
        else if (pp.left == p)
            pp.left = child;
        else
            pp.right = child;

        System.out.println("\n删除节点" + data + "后:");
        inOrder(tree);
    }

    /**
     * 计算二叉树的高度
     *
     * @param root
     * @param index
     * @return
     */
    public static int getBinaryLevel(Node root, int index{
        if (null == root) {
            return index;
        }

        int maxleftLevel = 0;
        if (root.left != null) {
            maxleftLevel = getBinaryLevel(root.left, index + 1);
        }

        int maxRightLevel = 0;

        if (root.right != null) {
            maxRightLevel = getBinaryLevel(root.right, index + 1);
        }

        return Math.max(maxleftLevel, maxRightLevel) + 1;
    }

    public static void main(String[] args{
        // 构建二叉树
        Node leaf1 = new Node(6);
        Node leaf2 = new Node(9);
        Node leaf3 = new Node(10);
        Node node1 = new Node(3);
        node1.setLeft(leaf1);
        node1.setRight(leaf2);
        Node node2 = new Node(5);
        node2.setLeft(leaf3);
        Node root = new Node(1);
        root.setLeft(node1);
        root.setRight(node2);
        // 构建中序遍历有序的二叉查找树
        Node leaf11 = new Node(1);
        Node leaf22 = new Node(5);
        Node leaf33 = new Node(9);
        Node node11 = new Node(3);
        node11.setLeft(leaf11);
        node11.setRight(leaf22);
        Node node22 = new Node(10);
        node22.setLeft(leaf33);
        Node root1 = new Node(6);
        root1.setLeft(node11);
        root1.setRight(node22);

        System.out.println("前序遍历:");
        preOrder(root);
        System.out.println("\n中序遍历:");
        inOrder(root);
        System.out.println("\n后序遍历:");
        postOrder(root);
        System.out.println("\n层次遍历:");
        levelOrder(root);
        System.out.print("\n计算卡特兰数:\n" + countTrees(3));
        System.out.print("\n二叉查找树的查找操作:\n" + find(root1, 6).value);
        System.out.print("\n计算二叉树高度:\n" + getBinaryLevel(root, 0));
        System.out.println("\n二叉查找树的插入操作:");
        insert(root1, 11);
        System.out.println("\n二叉查找树插入节点11后:");
        inOrder(root1);
        System.out.println("\n二叉查找树的删除操作:");
        delete(root1, 6);
    }
}

哈希冲突、散列表学习记录

 1/********************************************
 2 * All Rights Reserved By www.laughing.ren
 3 * @author:Laughing_Lz
 4 * @version:2018年11月27日 上午1:07:01
 5 * ******************************************/
 6package ren.laughing.code.Test;
 7
 8import java.util.HashMap;
 9import java.util.LinkedHashMap;
10import java.util.Map;
11import java.util.TreeMap;
12
13public class Hash {
14    class Son {
15        private int age;
16        private String name;
17    }
18
19    /*
20     * ThreadLocalMap 使用了开放寻址法处理hash冲突 数据量小,装载因子小(较于链表更浪费内存空间)
21     * 开放寻址法的数据都存储在数组中,可以有效利用CPU缓存加快查询,而且序列化较为简单。
22     * 删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据。而且,在开放寻址法中,所有的数据都存储在一个数组中,比起链表法来说,冲突的代价更高。所以,
23     * 使用开放寻址法解决冲突的散列表,装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
24     */
25    public static void hash() {
26        // ThreadLocalMap是ThreadLocal的内部类,它是一个Map,key是ThreadLocal的实例变量
27        ThreadLocal<Son> threadLocal = new ThreadLocal<Son>();
28        // 使用链表法解决hash冲突,适用于大对象,大数据量,装载因子可以大于1,使用灵活,可将链表转换为红黑树、跳表等结构。
29        LinkedHashMap<String, Son> linkedHashMap = new LinkedHashMap<>();
30        HashMap<String, Son> map = new HashMap<String, Son>();
31        // hashmap 可修改初始大小,默认为16,装载因子默认0.75
32        HashMap<ObjectObject> hashMap = new HashMap<ObjectObject>(110);
33    }
34    /*
35     * 设计工业级的散列表,应具有哪些属性? 1.支持快速查询、插入、删除 2.内存占用合理,不能浪费过多的内存空间
36     * 3.性能稳定,极端情况下,散列表的性能也不会退化到无法接受的情况
37     */
38
39    /*
40     * 如何设计工业级的散列表? 1.设计一个合理的散列函数 2.定义装载因子阈值,并且设计动态扩容策略 3.选择合适的散列冲突解决方法
41     */
42
43    /*
44     * 集合类的带hash的,例如hashmap、hashset、hashtable等。
45     * hashmap中散列函数是key的hashcode与key的hashcode右移16位异或,这是为了把key的高位考虑进去,如果key是0,hash值为0
46     * 。在put的时候,如果表没有初始化,需要初始化下,在计算key的位置的时候很巧妙,使用表的length-1和key的hash值与计算的,
47     * 实际上就是对key的hash值对表长取模,基于hashmap是2的幂次方特性,这种位运算速度更快。如果put后hashmap的数据容量超过了表的容量*
48     * 负载因子,就会自动扩容,默认是两倍,自动扩容方法是将key的hash与表长直接与判断是否有高位,有高位就把这个node放到新表里旧表对应位置加旧表长的地方
49     * 。没有高位就直接是新表旧位置。这是hashmap1.8的处理方法。hashmap1.7还是对key的hash取模。如果是个非常大的数,赋值为integer
50     * .max。hashmap采用的是链地址法结合红黑树解决hash冲突,当桶中链表长度大于8就会将桶中数据结构转化为红黑树。
51     * hashtable默认的初使容量11,负载因子也是0.75,如果要指定初始化hashtable容量最好是给一个素数。
52     * 这是因为放入table的时候需要对表长取模,尽量分散地映射。hashtable通过链地址法解决hash冲突,当数据容量大于数据容量*负载因子自动扩容,
53     * 扩容原表长两倍+1。
54     */
55    /*
56     * TreeMap 使用红黑树的数据结构,好好研究源码
57     */
58    Map<StringString> map = new TreeMap<>();
59}

关于二分查找及变体

关于二分查找及变体

/********************************************
 * All Rights Reserved By www.laughing.ren
 * @author:Laughing_Lz
 * @version:2018年11月22日 下午11:28:28
 * ******************************************/
package ren.laughing.code.Test;

import java.util.Arrays;

public class Search {

    /**
     * 简单的二分查找,前提是数组是有序,且无重复值
     * 
     * @param arr arr
     */
    public static int binarySearch(int valueint[] arr{
        int low = 0, high = arr.length - 1, middle;
        // 为什么要是<=呢?
        while (low <= high) {
            middle = low + ((high - low) >> 1);
            if (arr[middle] < value) {
                low = middle + 1;
            } else if (arr[middle] > value) {
                high = middle - 1;
            } else {
                return middle;
            }
        }
        return -1;

    }

    /**
     * 递归方法实现简单二分查找,前提同上:数组有序,且无重复值
     * 
     * @param value value
     * @param arr   arr
     * @param low   low
     * @param high  high
     * @return
     */
    public static int recursionBinarySearch(int valueint[] arr, int low, int high{
        if (low > high) {
            return -1;
        }
        int middle = low + ((high - low) >> 1);
        if (arr[middle] == value) {
            return middle;
        } else if (arr[middle] > value) {
            return recursionBinarySearch(value, arr, low, middle - 1);
        } else {
            return recursionBinarySearch(value, arr, middle + 1, high);
        }

    }

    /**
     * 求解一个数的平方根,精确到小数六位
     * 
     * @param n n
     * @return
     */
    public static float square(float n{
        if (n == 0 || n == 1) {
            return 1;
        }
        float low = 0, high = n;
        float middle = low + (high - low) / 2;
        while (Math.abs(middle * middle - n) > 0.000001) {
            if (middle * middle > n) {
                high = middle;
            } else if (middle * middle < n) {
                low = middle;
            } else {
                return middle;
            }
            middle = low + (high - low) / 2;
        }
        return middle;
    }

    /**
     * 利用二分查找返回数组中第一个出现value的位置,注意边界条件middle==0
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int firstEqual(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                if ((middle == 0) || (arr[middle - 1] < value)) {
                    return middle;
                } else {
                    high = middle - 1;
                }
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 利用二分查找返回数组中最后一个出现value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int lastEqual(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low < high) {
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                if ((middle == arr.length - 1) || (arr[middle + 1] > value)) {
                    return middle;
                } else {
                    low = middle + 1;
                }
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;

    }

    /**
     * 利用二分查找返回数组中第一个大于value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int firstGreat(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] > value && arr[middle - 1] <= value) {
                return middle;
            } else if (arr[middle] <= value) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 利用二分查找返回数组中最后一个小于value的位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int lastLess(int[] arr, int value{
        int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);
        while (low <= high) {
            if (arr[middle] < value && arr[middle + 1] >= value) {
                return middle;
            } else if (arr[middle] >= value) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
            middle = low + ((high - low) >> 1);
        }
        return -1;
    }

    /**
     * 循环数组中使用二分查找获取value所在位置
     * 
     * @param arr   arr
     * @param value value
     * @return
     */
    public static int loopBinarySearch(int[] arr, int value{
        if(arr.length < 1) {
            return -1;
        }
        if (arr.length == 1) {
            if (arr[0] == value) {
                return 0;
            } else {
                return -1;
            }
        }
        int low = 0, high = arr.length, middle = 0;
        // 首先获取首末位置
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                high = i;
                low = i + 1;
            }
        }
        if (arr[arr.length - 1] > arr[0]) {
            low = 0;
            high = arr.length - 1;
        }
        // 经过和arr[0]判断后筛选出可能包含value的子数组
        if (arr[0] == value) {
            return 0;
        } else if (arr[0] < value) {
            low = 1;
        } else if (arr[0] > value) {
            high = arr.length - 1;
        }
        // 使用简单二分查找获取value位置
        while (low <= high) {
            middle = low + ((high - low) >> 1);
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    public static void main(String[] args{
        int[] arr = { 2146730985 };
        Arrays.sort(arr);
//        System.out.println(binarySearch(5, arr));
//        System.out.println(recursionBinarySearch(5, arr, 0, arr.length - 1));
        System.out.println(square(5f));
        int[] arr1 = { 01234455589 };
        System.out.println(firstEqual(arr1, 5));
        System.out.println(lastEqual(arr1, 5));
        System.out.println(firstGreat(arr1, 5));
        System.out.println(lastLess(arr1, 5));
        int[] arr2 = { 7890123456 };
        System.out.println(loopBinarySearch(arr2, 8));

    }
}