不知名程序员韭菜个人博客

线段树

发表于 2022-07-19 更新于 2023-04-26 分类于技术 Valine：

本文转自线段树可以解决什么问题

线段树概述

线段树是什么？

线段树是一种高级数据结构，也是一种树结构，准确的说是二叉树。它能够高效的处理区间修改查询等问题。因此学习线段树，我们就是在学习一种全新的高级数据结构，学习它如何组织数据，然后高效的进行数据查询，修改等操作。

线段树树的基本操作有哪些？

线段树的构建
线段树的修改
线段树的查询
这些基本操作都会在后面部分讲到。

线段树的使用场景？

用于维护区间信息（要求满足结合律）
实现 [公式] 的区间修改
持多种操作（加、乘），更具通用性

线段树问题举例

我们有时会遇到这样的问题: 给你一些数，组成一个序列，如[1 4 2 3],有两种操做: 操作一:给序列的第i个数加上X (X可以为负数) 操作二:询问序列中最大的数是什么? 格式query(start, end)，表示区间[start, end]内，最大值是多少？

思路解析
我们很容易得到一个朴素的算法: 将这些数存入一个数组, 由于要询问最大值, 我们只需要遍历这个区间[start, end]即可，找出最大值。对于改变一个数, 我们就在这个数上加上X，比如A[i] = A[i] + X。这个算法的缺点是什么呢？Query询问最大值复杂度O(N), 修改复杂度为O(1)，在有Q个query的情况下这样总的复杂度为O(QN), 那么对于查询来说这样的复杂度是不可以接受的，太高了！然后我们开始优化，如果你没有学过线段树，那么对于这个问题的优化是很难做的，甚至毫无头绪，基本上无从无从入手。

如果你学习了线段树，这个问题很容易解决，线段树就是一把区间问题解决的利刃，很多没有头绪的区间查询，修改问题都可以使用线段树解决。那么这道题线段树应该怎么做？希望大家带着疑问阅读线段树的入门教程。

线段树的结构

首先线段树是一棵二叉树, 平常我们所指的线段树都是指一维线段树。故名思义, 线段树能解决的是线段上的问题, 这个线段也可指区间. 我们先来看线段树的逻辑结构。

一颗线段树的构造就是根据区间的性质的来构造的, 如下是一棵区间[0, 3]的线段树，每个[start, end]都是一个二叉树中的节点。

         [0,3]
        /     \
   [0,1]       [2,3]
   /   \       /   \
[0,0] [1,1] [2,2] [3,3]

区间划分大概就是上述的区间划分。可以看出每次都将区间的长度一分为二,数列长度为n,所以线段树的高度是log(n),这是很多高效操作的基础。上述的区间存储的只是区间的左右边界。我们可以将区间的最大值加入进来,也就是树中的Node需要存储left，right左右子节点外，还需要存储start, end, val区间的范围和区间内表示的值。

            [0,3]
           (val=4)
         /         \
     [0,1]         [2,3]
    (val=4)       (val=3)
    /    \         /    \
 [0,0]  [1,1]   [2,2]  [3,3]
(val=1)(val=4) (val=2)(val=3)

区间的第三维就是区间的最大值。加这一维的时候只需要在建完了左右区间之后，根据左右区间的最大值来更新当前区间的最大值即可，即当前子树的最大值是左子树的最大和右子树的最大值里面选出来的最大值。

因为每次将区间的长度一分为二,所有创造的节点个数，即底层有n个节点，那么倒数第二次约n/2个节点，倒数第三次约n/4个节点，依次类推：

1
2
3

    n + 1/2 * n + 1/4 * n + 1/8 * n + ...
=   (1 + 1/2 + 1/4 + 1/8 + ...) * n
=   2n

所以构造线段树的时间复杂度和空间复杂度都为O(n)

二叉树的节点区间定义，[start, end]代表节点的区间范围，max 是节点在[start, end]区间上的最大值 left , right 是当前节点区间划分之后的左右节点区间

// 节点区间定义
// [start, end] 代表节点的区间范围
// max 是节点在(start,end)区间上的最大值
// left , right 是当前节点区间划分之后的左右节点区间
public class SegmentTreeNode {
    public int start, end, max;
    public SegmentTreeNode left, right;
    public SegmentTreeNode(int start, int end, int max) {
        this.start = start;
        this.end = end;
        this.max = max
        this.left = this.right = null;
    }
}

线段树区间最大值维护

给定一个区间，我们要维护线段树中存在的区间中最大的值。这将有利于我们高效的查询任何区间的最大值。给出A数组，基于A数组构建一棵维护最大值的线段树，我们可以在O(logN)的复杂度内查询任意区间的最大值：

比如原数组 A = [1, 4, 2, 3]

            [0,3]
           (val=4)
         /         \
     [0,1]         [2,3]
    (val=4)       (val=3)
    /    \         /    \
 [0,0]  [1,1]   [2,2]  [3,3]
(val=1)(val=4) (val=2)(val=3)

// 构造的代码及注释
public SegmentTreeNode build(int[] A) {
    // write your code here
    return buildhelper(0, A.length - 1, A);
}
public SegmentTreeNode buildhelper(int left, int right, int[] A){
    if(left > right){
        return null;
    }
    SegmentTreeNode root = new SegmentTreeNode(left, right, A[left]); // 根据节点区间的左边界的序列值为节点赋初值
    if(left == right){
        return root; // 如果左边界和右边界相等,节点左边界的序列值就是线段树节点的接节点值
    }
    int mid = (left + right) / 2; // 划分当前区间的左右区间
    root.left = buildhelper(left, mid, A);
    root.right = buildhelper(mid + 1, right, A);
    root.max = Math.max(root.left.max, root.right.max); // 根据节点区间的左右区间的节点值得到当前节点的节点值
    return root;
}

举一反三：如果需要区间的最小值: root.min = Math.min(root.left.min, root.right.min); 如果需要区间的和: root.sum = root.left.sum + root.right.sum;

线段树的区间查询

1. 如何更好的查询Query

构造线段树的目的就是为了更快的查询。

给定一个区间，要求区间中最大的值。线段树的区间查询操作就是将当前区间分解为较小的子区间,然后由子区间的最大值就可以快速得到需要查询区间的最大值。

            [0,3]
           (val=4)
         /         \
     [0,1]         [2,3]
    (val=4)       (val=3)
    /    \         /    \
 [0,0]  [1,1]   [2,2]  [3,3]
(val=1)(val=4) (val=2)(val=3)

1	query(1,3) = max(query(1,1),query(2,3)) = max(4,3) = 4

上述例子将[1, 3]区间分为了[1, 1]和[2, 3]两个区间,因为[1, 1]和[2, 3]存在于线段树上，所以区间的最大值已经记录好了,所以直接拿来用就可以了。所以拆分区间的目的是划分成为线段树上已经存在的小线段。

2. 如何拆分区间变成线段树上有的小区间：

在线段树的层数上考虑查询考虑长度为8的序列构造成的线段树区间[1, 8], 现在我们查询区间[1, 7]

第一层会查询试图查询[1, 7], 发现区间不存在，然后根据mid位置拆分[1, 4]和[5, 7] 第二层会查询[1, 4],[5, 7], 发现[1, 4]已经存在，返回即可，[5, 7]仍旧需要继续拆分第三层会查询[5, 6],[7, 7], 发现[5, 6]已经存在，返回即可，[7, 7]仍旧需要继续拆分第四层会查询[7, 7]

任意长度的线段，最多被拆分成logn条线段树上存在的线段，所以查询的时间复杂度为O(log(n)) 记住就好：）

// 区间查询的代码及注释
public int query(TreeNode root, int start, int end) {
    if (start <= root.start && root.end <= end) {
        // 如果查询区间在当前节点的区间之内,直接输出结果
        return root.max;
    }
    int mid = (root.start + root.end) / 2; // 将当前节点区间分割为左右2个区间的分割线
    int ans = Integer.MIN_VALUE; // 给结果赋初值
    if (mid >= start) {   // 如果查询区间和左边节点区间有交集,则寻找查询区间在左边区间上的最大值
        ans = Math.max(ans, query(root.left, start, end));
    }
    if (mid + 1 <= end) { // 如果查询区间和右边节点区间有交集,则寻找查询区间在右边区间上的最大值
        ans = Math.max(ans, query(root.right, start, end));
    }
    return ans; // 返回查询结果
}

线段树的单点更新

1. 更新序列中的一个点

            [0,3]
           (val=4)
         /         \
     [0,1]         [2,3]
    (val=4)       (val=3)
    /    \         /    \
 [0,0]  [1,1]   [2,2]  [3,3]
(val=1)(val=4) (val=2)(val=3)

更新序列中的一个节点，如何把这种变化体现到线段树中去，例如，将序列中的第4个点A[3]更新为5, 要变动3个区间中的值,分别为[3,3],[2,3],[0,3]

提问：为什么需要更新这三个区间？：因为只有这三个在线段树中的区间，覆盖了3这个点。

           [0,3]
          (val=5)
        /         \
    [0,1]         [2,3]
   (val=4)       (val=5)
   /    \         /    \
[0,0]  [1,1]   [2,2]  [3,3]

1	(val=1)(val=4) (val=2)(val=5)

可以这样想,改动一个节点,与这个节点对应的叶子节点需要变动。因为叶子节点的值的改变可能影响到父亲节点，然后叶子节点的父亲节点也可能需要变动。

如果我们继续把A[2]从2变成4，线段树又该如何更新呢？线段树变化后的状态为：

           [0,3]
          (val=5)
        /         \
    [0,1]         [2,3]
   (val=4)       (val=5)
   /    \         /    \
[0,0]  [1,1]   [2,2]  [3,3]

1	(val=1)(val=4) (val=4)(val=5)

如果我们继续把A[1]从4变成3，线段树又该如何更新呢？线段树变化后的状态为：


           [0,3]
          (val=5)
        /         \
    [0,1]         [2,3]
   (val=3)       (val=5)
   /    \         /    \
[0,0]  [1,1]   [2,2]  [3,3]

1	(val=1)(val=3) (val=4)(val=5)

更新所以需要从叶子节点一路走到根节点, 去更新线段树上的值。因为线段树的高度为log(n),所以更新序列中一个节点的复杂度为log(n)。因为每次从父节点走到子节点的时候，区间都是一分为二，那么我们要修改index的时候，我们从root出发，判断index会落在左边还是右边，然后继续递归，这样就可以很容易从根节点走到叶子节点，然后更新叶子节点的值，递归返回前不断更新每个节点的最大值即可。具体代码实现如下：

// 单点更新的代码及注释
public void modify(SegmentTreeNode root, int index, int value) {
    // write your code here
    if(root.start == root.end && root.start == index) { // 找到被改动的叶子节点
        root.max = value; // 改变value值
        return ;
    }
    int mid = (root.start + root.end) / 2; // 将当前节点区间分割为2个区间的分割线
    if(index <= mid){ // 如果index在当前节点的左边
        modify(root.left, index, value); // 递归操作
        root.max = Math.max(root.right.max, root.left.max); // 可能对当前节点的影响
    }
    else {            // 如果index在当前节点的右边
        modify(root.right, index, value); // 递归操作
        root.max = Math.max(root.left.max, root.right.max); // 可能对当前节点的影响
    }
    return ;
}

如果需要区间的最小值或者区间的和，构造的时候同理。

线段树模板-线段树动态开点

来自线段树动态开点+线段树图解

动态开点的线段树节点

/**
     * 线段树的结点
     */
    static class Node {
        //左范围
        private int left;
        //右范围
        private int right;
        //区间和
        private int sum;
        //懒标记 0表示不需要操作
        private int lazy;
        //左子树和右子树
        Node leftChild, rightChild;

        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

动态开点的更新

/**
     * 区间更新
     *
     * @param root  树的根
     * @param left  左边界
     * @param right 有边界
     * @param value 更新值
     */
    public void update(Node root, int left, int right, int value) {
        //不在范围内 直接返回
        if (root.left > right || root.right < left) {
            return;
        }
        //修改的区间包含当前结点
        if (root.left >= left && root.right <= right) {
            root.lazy = value;
            root.value += (root.right - root.left + 1) * value;
        } else {
            //动态开点
            lazyCreate(root);
            //下传lazy
            pushDown(root);
            //更新左子树
            update(root.leftChild, left, right, value);
            //更新右子树
            update(root.rightChild, left, right, value);
            //上传结果
            pushUp(root);
        }
    }

    /**
     * 创建左右子树
     *
     * @param root
     */
    public void lazyCreate(Node root) {
        if (root.leftChild == null) {
            root.leftChild = new Node(root.left, root.left + (root.right - root.left) / 2);
        }
        if (root.rightChild == null) {
            root.rightChild = new Node(root.left + (root.right - root.left) / 2 + 1, root.right);
        }
    }

    /**
     * 下传lazy
     *
     * @param root
     */
    public void pushDown(Node root) {
        if (root.lazy == 0) {
            return;
        }
        int value = root.lazy;
        root.leftChild.lazy = value;
        root.rightChild.lazy = value;
        root.leftChild.value += (root.leftChild.right - root.leftChild.left + 1) * value;
        root.rightChild.value += (root.rightChild.right - root.rightChild.left + 1) * value;
        root.lazy = 0;
    }

    /**
     * 上传结果
     *
     * @param root
     */
    public void pushUp(Node root) {
        root.value = root.leftChild.value + root.rightChild.value;
    }

动态开点的查询




public int query(Node root, int left, int right) {
    if (left <= root.left && root.right <= right) {
        return root.value;
    }
    lazyCreate(root);
    pushDown(root);
    int mid = root.left + (root.right - root.left) / 2;
    if (right <= mid) {
        return query(root.leftChild, left, right);
    } else if (left > mid) {
        return query(root.rightChild, left, right);
    } else {
        return query(root.leftChild, left, mid) + query(root.rightChild, mid + 1, right);
    }
}

实战面试题

实战面试题1 - 731. 我的日程安排表 II

leetcode原题：https://leetcode.cn/problems/my-calendar-ii/

题目大意：

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

解题思路：
标准的区间求最大值，直接套用模板

题解：

class MyCalendarTwo {
    /**
     * 线段树的结点
     */
    static class Node {
        //左范围
        private int leftX;
        //右范围
        private int rightX;
        //最大值
        private int max;
        //懒标记 0表示不需要操作
        private int lazy;
        //左子树和右子树
        Node leftChild, rightChild;

        public Node(int leftX, int rightX) {
            this.leftX = leftX;
            this.rightX = rightX;
        }
    }

    private Node root;

    /**
     * 区间更新
     *
     * @param root  树的根
     * @param left  左边界
     * @param right 有边界
     * @param value 更新值,删除则相当于置为0
     */
    public void update(Node root, int left, int right, int value) {
        //不在范围内 直接返回
        if (root.leftX > right || root.rightX < left) {
            return;
        }
        //修改的区间包含当前结点
        if (root.leftX >= left && root.rightX <= right) {
            root.max += value;
            root.lazy += value;
        } else {
            //动态开点
            lazyCreate(root);
            //下传lazy
            pushDown(root);
            //更新左子树
            update(root.leftChild, left, right, value);
            //更新右子树
            update(root.rightChild, left, right, value);
            //上传结果
            pushUp(root);
        }
    }

    public int query(Node root, int left, int right) {
        if (left <= root.leftX && root.rightX <= right) {
            return root.max;
        }
        lazyCreate(root);
        pushDown(root);
        int mid = root.leftX + (root.rightX - root.leftX) / 2;
        if (right <= mid) {
            return query(root.leftChild, left, right);
        } else if (left > mid) {
            return query(root.rightChild, left, right);
        } else {
            return Math.max(query(root.leftChild, left, mid), query(root.rightChild, mid + 1, right));
        }
    }

    /**
     * 创建左右子树
     *
     * @param root
     */
    public void lazyCreate(Node root) {
        if (root.leftChild == null) {
            root.leftChild = new Node(root.leftX, root.leftX + (root.rightX - root.leftX) / 2);
        }
        if (root.rightChild == null) {
            root.rightChild = new Node(root.leftX + (root.rightX - root.leftX) / 2 + 1, root.rightX);
        }
    }

    /**
     * 下传lazy
     *
     * @param root
     */
    public void pushDown(Node root) {
        if (root.lazy > 0) {
            int value = root.lazy;
            root.leftChild.lazy += value;
            root.rightChild.lazy += value;
            root.leftChild.max += value;
            root.rightChild.max += value;
            root.lazy = 0;
        }
    }

    /**
     * 上传结果
     *
     * @param root
     */
    public void pushUp(Node root) {
        root.max = Math.max(root.leftChild.max, root.rightChild.max);
    }

    public MyCalendarTwo() {
        root = new Node(0, (int) 1e9);
    }

    public boolean book(int start, int end) {
        int query = query(root, start, end - 1);
        if (query >= 2) {
            return false;
        }
        update(root, start, end - 1, 1);
        return true;
    }
}

问题集

发表于 2022-07-15 更新于 2023-04-26 分类于问题集 Valine：

技术问题

股票

从哪下载上市公司财报

证监会指中国证券监督管理委员会
中核集团指中国核能电力股份有限公司控股股东，中国核工业集团有限公司
公司、本公司、
中国核电指中国核能电力股份有限公司
秦山核电指
秦山核电有限公司、核电秦山联营有限公司和秦山第三核电有限公
司三家公司的简称
秦山一核指
秦山核电有限公司，原秦山核电公司，为本公司直接持有 72%股权的
控股子公司
秦山二核指核电秦山联营有限公司，为本公司直接持有 50%股权的控股子公司
秦山三核指秦山第三核电有限公司，为本公司直接持有 51%股权的控股子公司
方家山核电指秦山核电有限公司所属的秦山核电厂扩建项目
田湾核电指江苏核电有限公司，为本公司直接持有 50%股权的控股子公司
三门核电指三门核电有限公司，为本公司直接持有 56%股权的控股子公司
福清核电指福建福清核电有限公司，为本公司直接持有 51%股权的控股子公司
海南核电指海南核电有限公司，为本公司直接持有 51%股权的控股子公司
漳州能源指
中核国电漳州能源有限公司，为本公司直接持有 51%股权的控股子公
司
辽宁核电指中核辽宁核电有限公司，为本公司直接持有 54%股份的控股子公司
中核苏能指中核苏能核电有限公司，为本公司直接持有 51%股权的控股子公司
桃花江核电指
湖南桃花江核电有限公司,为本公司直接持有 51.16%股权的控股子
公司
中核汇能指中核汇能有限公司，为本公司直接持有 100%股权的控股子公司
中核燕龙指中核燕龙科技有限公司，为本公司直接持有 51%股权的控股子公司
中核武汉指
中核武汉核电运行技术股份有限公司,为本公司直接和间接持有
55.72%股权的控股子公司
华龙一号指
中国拥有完全自主知识产权的三代压水堆技术，采用“能动与非能
动”相结合的安全设计理念，首堆示范工程电功率 116.1 万千瓦，
设计寿命 60 年
CP300 指中核集团自主设计的 30 万千瓦的压水堆技术
CP600 指
中核集团在吸收国际压水堆技术的基础上，自主设计的 60 万千瓦二
代改进型压水堆技术
CP1000 指
中核集团在吸收国际压水堆技术的基础上，自主设计的 100 万千瓦
二代改进型压水堆技术
VVER-1000 指
俄罗斯设计准三代压水堆技术，设置双层安全壳、堆芯捕集器，电功
率 100 万千瓦，设计寿命 40 年
VVER-1200 指
俄罗斯设计的三代压水堆技术，设置双层安全壳、堆芯捕集器，采用
“能动与非能动”相结合的安全设计理念。电功率 120 万千瓦，设
计寿命 60 年
AP1000 指
西屋公司开发的三代压水堆技术，采用非能动安全设施和简化的电
厂设计，电功率 125 万千瓦，设计寿命 60 年
重水堆、
CANDU-6 指
加拿大设计的以重水作为慢化剂和冷却剂、天然铀为燃料、采用不
停堆更换燃料的反应堆技术，电功率 70 万千瓦，设计寿命 40 年
玲龙一号指
以我国现有压水堆设计为基础，采用一体化反应堆技术路线，以热、
水、电多用途为目标,安全性可达到第三代核能系统技术水平的一体
化小型压水堆（简称 ACP100）。电功率 12.5 万千瓦，设计寿命 60
年
核电设备利用
小时数指
机组在统计期内的发电量除以机组装机容量，如统计期内有新机组
首次并网，则新机组的装机容量应折算，折算比例为该机组实际运
行小时数除以统计期日历小时数
能力因子指
机组可用发电量与额定发电量的比值，用百分比表示，机组能力因
子反映核电厂在优化计划停堆活动和降低非计划能量损失方面管理
的有效性，全部机组的平均能力因子为各机组能力因子的算数平均
值
敏捷端新产业指
指高新技术产业投资开发。强调技术自主，重研发，相对轻资产，可
快速进入领先梯队，重点孵化符合国家战略方向，市场前景广阔的
高新技术产业。
WANO 指
世界核电运营者协会（World Association of Nuclear Operators，
WANO），为 1985 年 5 月在莫斯科成立的非营利性、非政府的世界性
组织，联合世界范围内所有运行商用核电站的

中国核电分析

搞钱

小工厂是如何盈利的？

trie tree (字典树)

发表于 2022-07-14 更新于 2023-04-26 分类于技术 Valine：

什么是字典树(rie tree)

字典树，英文名 trie。顾名思义，就是一个像字典一样的树。

trie tree

可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子，表示的就是字符串 caa。

trie 的结构非常好懂，我们用 $\delta(u,c)$ 表示结点 $u$ 的 $c$ 字符指向的下一个结点，或着说是结点 $u$ 代表的字符串后面添加一个字符 $c$ 形成的字符串的结点。

有时需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。

代码模板

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

trie tree 的应用

检索字符串
字典树最基础的应用——查找一个字符串是否在“字典”中出现过。
AC 自动机
trie 是 AC 自动机的一部分。
维护异或极值
将数的二进制表示看做一个字符串，就可以建出字符集为的 trie 树

参考资料

字典树 (Trie)
实现 Trie (前缀树)

ngrok+nginx实现windows远程桌面连接

发表于 2022-07-12 更新于 2023-04-26 分类于技术 Valine：

前言

最近想在公司远程连接家里的电脑，但苦于现在的家庭网络没有独立ip，导致无法通过ip直连。

作为一个程序员，这怎么能难倒我们，通过网上搜索找到以下几个解决方法
1、打电话给运营商让给外网ip

这个方法随着ip4资源越来越少，估计越来越不现实

2、通过网络穿透，类似花生壳或ngrok这些服务，把局域网服务通过服务器暴露给外网调用。

此方案靠谱，本人最后选择了自建ngrok服务搭建网络穿透。

NGROK简介

官方的解释为

ngrok 是一个反向代理，它创建从公共端点到本地运行的 Web 服务的安全隧道。 ngrok 捕获并分析隧道上的所有流量，以供以后检查和重放。

简单来说，你个人本地web服务，通过与ngrok的服务建立隧道连接，然后别人就可以通过访问ngrok服务来访问你的本地服务了。

ngrok的git地址： https://github.com/inconshreveable/ngrok

ngrok的官网： https://ngrok.com/

商业版本的ngrok已经到2.0了，但是源码并不开源，开源的只是1.0。官方也不建议使用1.0，因为客户端和服务器都存在严重的可靠性问题，包括内存和文件描述符泄漏以及崩溃。

使用ngrok有两种方法

直接使用官方ngrok服务，服务端是现成的，分为国外和国内，我们只需安装客户端即可，操作手册参见ngrok官网
使用ngrok1.0git源码，自行编译和搭建ngrok服务端和客户端。

本人最后采用了编译ngrok源码的方式，搭建服务端和客户端，并最后实现windows远程连接。

NGROK的安装

网上的相关资料比较多，这里就不展开说了，本人参考了以下两篇。
云服务器搭建自己的ngrok服务-实现内网穿透
 https://cloud.tencent.com/developer/article/1100382

个人最后总的命令如下

# 设置域名
NGROK_DOMAIN=ngrok.oxxx.com

# 使用openssl证书域名跳过，本人最后采用阿里云免费证书的方式 具体可以参考 https://blog.csdn.net/qq_42063179/article/details/120620693 
# 证书的替换方式为：
xxx.pem > assets/server/tls/snakeoil.crt
xxx.pem > assets/client/tls/ngrokroot.cr
xxx.key > assets/server/tls/snakeoil.key

# openssl genrsa -out rootCA.key 2048
# openssl req -x509 -new -nodes -key rootCA.key -subj "/CN=$NGROK_DOMAIN" -days 5000 -out rootCA.pem
# openssl genrsa -out device.key 2048
# openssl req -new -key device.key -subj "/CN=$NGROK_DOMAIN" -out device.csr
# openssl x509 -req -in device.csr -CA rootCA.pem -CAkey rootCA.key -CAcreateserial -out device.crt -days 5000

# cat rootCA.pem > assets/client/tls/ngrokroot.crt
# cat device.crt > assets/server/tls/snakeoil.crt
# cat device.key > assets/server/tls/snakeoil.key

# 关闭模块
go env -w GO111MODULE=off

# 开启模块，使用代理
go env -w GO111MODULE=on 
go env -w GOPROXY=https://goproxy.cn,direct


#编译服务端 linux 64位 服务器
GOOS=linux GOARCH=amd64 make release-server

# 编译客户端 64位windows客户端: 
GOOS=windows GOARCH=amd64 make release-client
#编译客户端 mac 64 位 客户端
GOOS=darwin GOARCH=amd64 make release-client
#编译客户端 linux 64 位客户端
GOOS=linux GOARCH=amd64 make release-client

# 启动服务
nohup /opt/soft/ngrok/bin/ngrokd  -tlsKey=/opt/soft/ngrok/assets/server/tls/snakeoil.key -tlsCrt=/opt/soft/ngrok/assets/server/tls/snakeoil.crt -domain="ngrok.xxx.com" -httpAddr=":9101" -httpsAddr=":9104" -tunnelAddr=":9103" > /opt/soft/ngrok/logs/ngrok.log 2>&1 &
tail -f /opt/soft/ngrok/logs/ngrok.log


# 进入客户端ngrok目录
cd ngrok
# 新增客户端配置文件 ngrok.cfg
vi ngrok.cfg

#ngrok.cfg 文件内容
server_addr: "ngrok.xxx.com:9103"
trust_host_root_certs: false
tunnels: #可定义多个域名
    test1:
        subdomain: "test1" #定义服务器分配域名前缀
        proto:
            http: 8089 #映射端口，不加ip默认本机

    mstsc: # windows 远程桌面
        remote_port: 4499
        proto:
            tcp: 3389 #映射端口，不加ip默认本机

# 启动客户端
./ngrok -config=ngrok.cfg -log=ngrok.log start test2 

# 访问远程左面地址 
ngrok.xxx.com:4499

安装避坑指南

1、使用go编译ngrok卡住
因为go需要依赖第三方工程，由于伟大的长城在，网络不通畅，可以关闭模块或配置代理，都有效。

# 关闭模块
go env -w GO111MODULE=off

# 开启模块，使用代理
go env -w GO111MODULE=on 
go env -w GOPROXY=https://goproxy.cn,direct

2、openssl证书认证错误

1	ngrok certificate relies on legacy Common Name field, use SANs instead

这是因为common name field 模式计划删除了20年都没删除，go语言在1.15之后之后不再支持。

解决方式吗，要么降低go语言版本(不推荐)，要么使用推荐的SAN替换(本人没跑通)，要么直接使用现成的证书(本人使用了阿里云的免费证书)

1、阿里云免费证书申请参见 2022阿里云免费SSL证书申请全过程（图文详解）

2、证书下载方式为其他，下载后替换如下
xxx.pem > assets/server/tls/snakeoil.crt
xxx.pem > assets/client/tls/ngrokroot.cr
xxx.key > assets/server/tls/snakeoil.key

WINDOWS 远程桌面开启&ngrok客户端配置

如何开启远程桌面，这个网上较多，可以参考如何使用远程桌面
如果处于安全考虑，可以修改远程桌面端口，可参考修改远程桌面端口

ngrok 客户端配置，可参考使用ngrok实现远程桌面连接

乐观锁，悲观锁，共享锁和排它锁

发表于 2022-06-01 更新于 2023-04-26 分类于技术 Valine：

乐观锁

乐观锁不是数据库自带的，需要我们自己去实现。乐观锁是指操作数据库时(更新操作)，想法很乐观，认为这次的操作不会导致冲突，在操作数据时，并不进行任何其他的特殊处理（也就是不加锁），而在进行更新后，再去判断是否有冲突了。

通常实现是这样的：在表中的数据进行操作时(更新)，先给数据表加一个版本(version)字段，每操作一次，将那条记录的版本号加1。也就是先查询出那条记录，获取出version字段,如果要对那条记录进行操作(更新),则先判断此刻version的值是否与刚刚查询出来时的version的值相等，如果相等，则说明这段期间，没有其他程序对其进行操作，则可以执行更新，将version字段的值加1；如果更新时发现此刻的version值与刚刚获取出来的version的值不相等，则说明这段期间已经有其他程序对其进行操作了，则不进行更新操作。

举例：

下单操作包括3步骤：

查询出商品信息

1	select (status,status,version) from t_goods where id=#{id}

根据商品信息生成订单
修改商品status为2
1
2
3
update t_goods
set status=2,version=version+1
where id=#{id} and version=#{version};
除了自己手动实现乐观锁之外，现在网上许多框架已经封装好了乐观锁的实现，如hibernate，需要时，可能自行搜索”hiberate 乐观锁”试试看。

悲观锁

与乐观锁相对应的就是悲观锁了。悲观锁就是在操作数据时，认为此操作会出现数据冲突，所以在进行每次操作时都要通过获取锁才能进行对相同数据的操作，这点跟java中的synchronized很相似，所以悲观锁需要耗费较多的时间。另外与乐观锁相对应的，悲观锁是由数据库自己实现了的，要用的时候，我们直接调用数据库的相关语句就可以了。

说到这里，由悲观锁涉及到的另外两个锁概念就出来了，它们就是共享锁与排它锁。共享锁和排它锁是悲观锁的不同的实现，它俩都属于悲观锁的范畴。

共享锁（S锁）

共享锁（S锁）：共享 (S) 指的就是对于多个不同的事务，对同一个资源共享同一个锁. 用于不更改或不更新数据的操作（只读操作），如 SELECT 语句。

如果事务T对数据A加上共享锁后，则其他事务只能对A再加共享锁，不能加排他锁。获准共享锁的事务只能读数据，不能修改数据。

刚刚说了，对于悲观锁，一般数据库已经实现了，共享锁也属于悲观锁的一种，那么共享锁在mysql中是通过什么命令来调用呢。通过查询资料，了解到通过在执行语句后面加上lock in share mode就代表对某些资源加上共享锁了。
比如，我这里通过mysql打开两个查询编辑器，在其中开启一个事务，并不执行commit语句
city表DDL如下：

CREATE TABLE `city` (
`id` bigint(20) NOT NULL AUTO_INCREMENT,
`name` varchar(255) DEFAULT NULL,
`state` varchar(255) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=18 DEFAULT CHARSET=utf8;

begin;
SELECT * from city where id = "1" lock in share mode;

然后在另一个查询窗口中，对id为1的数据进行更新

update city set name="666" where id ="1";
此时，操作界面进入了卡顿状态，过几秒后，也提示错误信息
[SQL]update city set name="666" where id ="1";
[Err] 1205 - Lock wait timeout exceeded; try restarting transaction

那么证明，对于id=1的记录加锁成功了，在上一条记录还没有commit之前，这条id=1的记录被锁住了，只有在上一个事务释放掉锁后才能进行操作，或用共享锁才能对此数据进行操作。

排他锁（X锁）

排他锁（X锁）：排它锁与共享锁相对应，就是指对于多个不同的事务，对同一个资源只能有一把锁。用于数据修改操作，例如 INSERT、UPDATE 或 DELETE。确保不会同时同一资源进行多重更新。

如果事务T对数据A加上排他锁后，则其他事务不能再对A加任任何类型的封锁。获准排他锁的事务既能读数据，又能修改数据。

我们在操作数据库的时候，可能会由于并发问题而引起的数据的不一致性（数据冲突）

行锁

行锁，由字面意思理解，就是给某一行加上锁，也就是一条记录加上锁。

比如之前演示的共享锁语句

1	SELECT * from city where id = "1" lock in share mode;

由于对于city表中,id字段为主键，就也相当于索引。执行加锁时，会将id这个索引为1的记录加上锁，那么这个锁就是行锁。

表锁

表锁，和行锁相对应，给这个表加上锁。

什么是 Base64 编码？

发表于 2022-05-16 更新于 2023-04-26 分类于技术 Valine：

建立对象就是为了使用对象，我们的 Java 程序通过栈上的 reference 数据来操作堆上的具体对象。对象的访问方式由虚拟机实现而定，目前主流的访问方式有：使用句柄、直接指针。

句柄
如果使用句柄的话，那么 Java 堆中将会划分出一块内存来作为句柄池，reference 中存储的就是对象的句柄地址，而句柄中包含了对象实例数据与类型数据各自的具体地址信息。

直接指针
如果使用直接指针访问，那么 Java 堆对象的布局中就必须考虑如何放置访问类型数据的相关信息，而 reference 中存储的直接就是对象的地址。

这两种对象访问方式各有优势。使用句柄来访问的最大好处是 reference 中存储的是稳定的句柄地址，在对象被移动时只会改变句柄中的实例数据指针，而 reference 本身不需要修改。使用直接指针访问方式最大的好处就是速度快，它节省了一次指针定位的时间开销。

二分查找，一个看似简单却复杂的算法解析

发表于 2022-05-16 更新于 2023-04-26 分类于技术 Valine：

引言

二分查找的大名，如雷贯耳，它可以在有序的一个数组中实现实现$O(logn)$的复杂度查找。

然而，业界还流传着一句话

十个二分九个错

这句调侃的话可谓精准的描述了二分查找的特性，二分查找从实现思路上是非常简单的，利用有序特性，对半查找，不断缩小范围，直到找到结果。然而在细节边界问题上，二分查找可以说是难得过分，如：

退出循环的标准，是< 还是 <= ?
mid的计算标准，是(left+right)/2还是 (left+right+1)/2 ?
折半的移动标准，是 =mid 还是 =mid-1 ?
返回值的选定，怎么有写是left，有写是right，有写还要额外判断？

因为这些边界问题，导致二分查找以为懂了的你，写出的代码总是不行，本文为个人为了彻底弄懂二分查找，一劳永逸的从根本上理解的沉淀。

二分查找的核心思想

二分查找的核心思想就是对半查找，如下图所示，有一个[1,2,3,4,5,6,7] 数组，要判断2是否存在于这个数据中。

二分查找的方法为：

数组[1,2,3,4,5,6,7]的中间值为 (1+7)/2=4，找第四个数字，该值为4，由于4!=2，因此需要继续判断，又由于4>2，因此得出目标值在左边这个区间，即[1,2,3]这里面
数组[1,2,3]的中间值为 (1+3)/2=2，找第二个数字，该值为2，是期望要找的目标，返回ture。

核心思想非常简单，非常简介。

二分查找的分类

二分查找的类型可以分为

寻找target值的下标
寻找左侧边界
寻找右侧边界
寻找小于target值的最大值
寻找>target值的最小值

其中
寻找左侧边界= 寻找>=target值的最小值
寻找右侧边界= 寻找<=target值的最大值

不同类型的二分代码

先直接给代码，之后再通过分析代码直接的异常点来确认为什么代码要这么写。

最简单的二分，寻找target值的下标

 /**
 * 最简单的二分，不会出错，判断目标值是否在array中
 * */
public int binarySearch(int[] array,int target){
    int l=0;
    int r=array.length-1;
    while (l<=r){
        int mid=(l+r)>>1;
        if(array[mid]==target){
            return mid;
        }else if(array[mid]<target){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return -1;
}

寻找左侧边界

/**
 * 寻找左侧边界
 * */
public int binarySearchLeft(int[] array,int target){
    int l=0;
    int r=array.length-1;
    while (l<r){
        int mid=(l+r)>>1;
        if(array[mid]>=target){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    return array[l]==target?l:-1;
}

寻找右侧边界

/**
 * 寻找右侧边界
 * */
public int binarySearchRight(int[] array,int target){
    int l=0;
    int r=array.length-1;
    while (l<r){
        int mid=(l+r+1)>>1;
        if(array[mid]<=target){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    return array[r]==target?r:-1;
}

寻找小于target的最大值

/**
 * 寻找小于target的最大值
 * */
public int binarySearchLtTarget(int[] array,int target){
    int l=0;
    int r=array.length-1;
    while (l<r){
        int mid=(l+r+1)>>1;
        if(array[mid]>=target){
            r=mid-1;
        }else{
            l=mid;
        }
    }
    return array[r]<target?r:-1;
}

寻找大于target的最小值

/**
 * 寻找大于target的最小值
 * */
public int binarySearchGtTarget(int[] array,int target){
    int l=0;
    int r=array.length-1;
    while (l<r){
        int mid=(l+r)>>1;
        if(array[mid]<=target){
            l=mid+1;
        }else{
            r=mid;
        }
    }
    return array[l]>target?l:-1;
}

区间判断采用闭区间

4步掌握二分查找写法

要想写出不出错的二分查找，必须得有区间思维，带着去见思维去写代码。个人总结了4步操作

1.二分查找框架模板伪代码

掌握二分查找框架模板，之后再一步一步实现细节，一个通用的模板如下

/**
 *  二分查找通用伪代码
 * */
public int binarySearch(int[] array,int target){
    int l=0;
    int r=array.length-1;
    while (loopCondition(l,r)){
        int mid=calcMid(l,r);
        if(check(array[mid],target)){
            l=changeLeft(mid);
        }else{
            r=changeRight(mid);
        }
    }
    return rs;
}

其中，exitLoopCondition,calcMid,check,changeLeft,changeRight,rs等都为伪代码，需要后续去实现。

2. 确认进入循环条件

确认进入循环的条件，即确认上文伪代码中的exitLoopCondition片段。

确认循环进入条件，首先确认我们的左右查询区间。

如果是$[l,r]$的闭区间，那么判断条件应该为 l<=r
如果是$[l,r)$的左闭又开区间，那么判断条件应该为 l<r

至于$(l,r]$左开右闭及$(l,r)$左开右开，由于太过特例独行，本篇就不进行考虑，当人个人可以进行推导。

所以，为什么$[l,r]$的闭区间，判断条件应该为$l<=r？$，而$[l,r)$的左闭又开区间，判断条件应该为 l<r？

对于二分查找，如果区间内不为空且存在值，那么就应该进入循环继续判断。
那么进入循环的条件判断就转化为，l，r满足什么条件，区间内存在值且不为空？
这个问题只要动用简单的数学知识，就能知道。

对于闭区间$[l,r]$，当边界区间内有值的条件为$l<=r$，因此当$l<=r$时，都应该进入循环。
而对于左闭右开区间$[l,r)$,边界的有值条件为$l<r$

是不是感觉和之前的话一模一样，但是视角不一样了。

3. mid值的计算

mid值的计算写法有很多种，本文列举几种

# 左边界
int mid=(l+r)/2;
int mid=(l+r)>>1;
int mid=l+(r-l)/2;
int mid=l+((r-l)>>1);
# 右边界
int mid=(l+r+1)/2;
int mid=(l+r+1)>>1;
int mid=l+(r-l+1)/2;
int mid=l+((r-l+1)>>1);

tips

mid值可能溢出，因此如果可以，将int升级为long类型
位运算符比除号性能更好
求右边界时，需要+1
使用位运算符，注意位运算的计算优先级

4. 区间结果判断&区间变更

本段主要确认的代码为

if(check(array[mid],target)){
    l=changeLeft(mid);
}else{
    r=changeRight(mid);
}

从代码上来说，则是确认 l=mid,r=mid-1还是l=mid-1,r=mid

还是区间的概念，只要简单分析就明白了。

对于左开右闭区间$[l,r)$，二分后的区间应该为$[l,mid)$和$[mid,r)$

4.1 确认mid的归属，归属左半边还是右半边

常见问题

边界分类

文章参考

二叉树的前序、中序和后序

发表于 2022-05-16 更新于 2023-04-26 分类于技术 Valine：

二叉树的遍历主要有3中，前序、中序和后序。

很多人经常只记住了名字，但是记不住前序、中序和后序到底是如何遍历的。

这里我们只要记住，前序，中序和后序指的是根节点的位置即可，即(根)前序，(根)中序，(根)后序，意思就是根节点在根节点、左节点，右节点这三个节点时遍历的顺序。
(根前序)根左右

(根中序)左根右

(根后序)左右根

这样子就非常形象了。

下面，根据实际的一个二叉树举例说明

前序遍历结果为：FDBACEGIHJ

中序遍历结果为：ABCDEFGIHJ

后序遍历结果为：ACBEDHJIGF

CAP 定理的含义【转载】

发表于 2022-05-13 更新于 2023-04-26 分类于技术 Valine：

转载

本文转自 CAP 定理的含义

前言

分布式系统（distributed system）正变得越来越重要，大型网站几乎都是分布式的。

分布式系统的最大难点，就是各个节点的状态如何同步。CAP 定理是这方面的基本定理，也是理解分布式系统的起点。

本文介绍该定理。它其实很好懂，而且是显而易见的。下面的内容主要参考了 Michael Whittaker 的文章。

一、分布式系统的三个指标

1998年，加州大学的计算机科学家 Eric Brewer 提出，分布式系统有三个指标。

1
2
3

Consistency
Availability
Partition tolerance

它们的第一个字母分别是 C、A、P。

Eric Brewer 说，这三个指标不可能同时做到。这个结论就叫做 CAP 定理。

二、Partition tolerance

先看 Partition tolerance，中文叫做”分区容错”。

大多数分布式系统都分布在多个子网络。每个子网络就叫做一个区（partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。

上图中，G1 和 G2 是两台跨区的服务器。G1 向 G2 发送一条消息，G2 可能无法收到。系统设计的时候，必须考虑到这种情况。

一般来说，分区容错无法避免，因此可以认为 CAP 的 P 总是成立。CAP 定理告诉我们，剩下的 C 和 A 无法同时做到。

三、Consistency

Consistency 中文叫做”一致性”。意思是，写操作之后的读操作，必须返回该值。举例来说，某条记录是 v0，用户向 G1 发起一个写操作，将其改为 v1。

接下来，用户的读操作就会得到 v1。这就叫一致性。

问题是，用户有可能向 G2 发起读操作，由于 G2 的值没有发生变化，因此返回的是 v0。G1 和 G2 读操作的结果不一致，这就不满足一致性了。

为了让 G2 也能变为 v1，就要在 G1 写操作的时候，让 G1 向 G2 发送一条消息，要求 G2 也改成 v1。

这样的话，用户向 G2 发起读操作，也能得到 v1。

四、Availability

Availability 中文叫做”可用性”，意思是只要收到用户的请求，服务器就必须给出回应。

用户可以选择向 G1 或 G2 发起读操作。不管是哪台服务器，只要收到请求，就必须告诉用户，到底是 v0 还是 v1，否则就不满足可用性。

五、Consistency 和 Availability 的矛盾

一致性和可用性，为什么不可能同时成立？答案很简单，因为可能通信失败（即出现分区容错）。

如果保证 G2 的一致性，那么 G1 必须在写操作时，锁定 G2 的读操作和写操作。只有数据同步后，才能重新开放读写。锁定期间，G2 不能读写，没有可用性不。

如果保证 G2 的可用性，那么势必不能锁定 G2，所以一致性不成立。

综上所述，G2 无法同时做到一致性和可用性。系统设计时只能选择一个目标。如果追求一致性，那么无法保证所有节点的可用性；如果追求所有节点的可用性，那就没法做到一致性。

在什么场合，可用性高于一致性？

举例来说，发布一张网页到 CDN，多个服务器有这张网页的副本。后来发现一个错误，需要更新网页，这时只能每个服务器都更新一遍。

一般来说，网页的更新不是特别强调一致性。短时期内，一些用户拿到老版本，另一些用户拿到新版本，问题不会特别大。当然，所有人最终都会看到新版本。所以，这个场合就是可用性高于一致性。

什么是 Base64 编码？

发表于 2022-05-06 更新于 2023-04-26 分类于技术 Valine：

Base64 是网络中存储和传输的二进制数据的普遍用法。Base64 一个字节只能表示 64 种情况，且编码格式每个字节的前两位都只能是 0，使用剩下的 6 位表示内容。

看到这里相信大家也能够意识到，这种编码格式无法充分利用存储资源，效能较低。那为什么还会成为网络中的普遍用法呢？

其实 Base64 最早是应用在邮件传输协议中的。当时邮件传输协议只支持 ASCII 字符传递，使用 ASCII 码来表示所有的英文字符和数字还有一些符号。这里有一个问题，如果邮件中只传输英文数字等，那么 ASCII 可以直接支持。但是如果要在文件中传输图片、视频等资源的话，这些资源转成 ASCII 的时候会出现非英文数字的情况。而且邮件中还存在很多控制字符，这些控制字符又会成为不可见字符。非英文字符和控制字符在传输过程中很容易产生错误，影响邮件的正确传输。为此才有了诞生了一个新的编码规则，把二进制以 3 个字节为一组，再把每组的 3 个字节（24 位）转换成 4 个 6 位，每 6 位根据查表对应一个 ASCII 符号，这就是 Base64。

Base64 将 8 位为一个单元的字节数据，拆分为 6 位为一个单元的二进制片段。每一个 6 位单元对应 Base64 索引表中的一个字符。简单举个例子，下图中 M 的 ASCII 码是 77 , 而转换为二进制后前六位二进制对应值为 19，为 Base64 字典中的 T。

当然这里也会有一个问题，如果要编码的二进制数据不是 3 的倍数，那就会剩下一至二个字节。为此 Base64 使用 000000 字节值在末尾补足，使其字节数能够被 3 整除，补位用 = 表示，= 的个数可表示补了多少字节，并在解码时自动去除。总体来看相比编码前，Base64 编码后的字符增加了约 33%。