数列的特征方程（斐波那契数列）

发表于 2019-03-15 | 分类于算法技巧 | 评论数： | 阅读次数：

特征方程

¶1、一阶线性递推数列

对于数列, 递推公式为

$\begin{aligned} X_n &= aX_{(n-1)} + b \end{aligned}$

设

$\begin{aligned} X_n - m &= a(X_{(n-1)} - m) \end{aligned}$

化简

$\begin{aligned} X_n &= aX_{(n-1)} - am + m \end{aligned}$

与原递推式比较，得

$\begin{aligned} b &= m - am \end{aligned}$

¶1、二阶线性递推数列

对于数列, 递推公式为

$\begin{aligned} X_n &= aX_{(n-1)} + bX_{(n-2)} \end{aligned}$

其特征方程

$\begin{aligned} m_{^2} = am + b \end{aligned}$

¶例：求斐波那契数列0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …的通项公式

其特征方程

$\begin{aligned} m_{^2} = m + 1 \end{aligned}$

解得

$\begin{aligned} m_1 &= \frac{1+\sqrt{5}}{2} \\[2ex] m_2 &= \frac{1-\sqrt{5}}{2} \end{aligned}$

详细解答方法

Jetbrain IDEA 插件开发常用API

发表于 2019-03-13 | 更新于 2019-03-15 | 分类于 Jetbrain | 评论数： | 阅读次数：

1、API

¶1.1 项目打开事件监听

实现 StartupActivity 接口, 并且在 plugin.xml 配置

¶1.2 通过project获取module列表

ModuleManager

¶1.3 类、方法、属性的文件查找

PsiShortNamesCache

¶1.4 按键监听事件

¶1.4.1 其他按键事件

实现 TypedHandlerDelegate

¶1.4.2 退格键事件

实现 BackspaceHandlerDelegate

¶1.4.3 回车键事件

实现 EnterHandlerDelegateAdapter

¶1.5 代码补全

继承 CompletionContributor ，在 plugin.xml 文件中需要指定 language 属性
LookupElementBuilder ，代码补全条目创建类

¶1.5 File查找

FilenameIndex

旋转数组的最小数字

发表于 2019-03-08 | 更新于 2019-03-09 | 分类于算法技巧 | 评论数： | 阅读次数：

¶题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

¶递归版

/**
     * 思路: 二分法
     * 缩小范围
     * !!!!!!!注意审题：是非减序，没说不能相同
     * !!!!!!!注意审题：是非减序，没说不能相同
     * !!!!!!!注意审题：是非减序，没说不能相同
     * 递归 版
     */
    private int minNumberInRotateArray(int[] array) {

        int length = array.length;
        if (length == 0) {
            return 0;
        }
        if (length == 1) {
            return array[0];
        } else if (length == 2) {
            return Math.min(array[0], array[1]);
        }
        int midIndex = (length - 1) / 2;
        // 正序
        if (array[midIndex] > array[0] && array[midIndex] < array[length - 1]) {
            return array[0];
        }
        // 倒序
        if (array[midIndex] < array[0] && array[midIndex] > array[length - 1]) {
            return array[length - 1];
        }
        // 三点相同
        if (array[midIndex] == array[0] && array[midIndex] == array[length - 1]) {
            // 舍弃最后一位
            // 问题：如果数据全部相同 todo
            this.minNumberInRotateArray(Arrays.copyOfRange(array, 0, length - 2));
        }
        // 前两点相同
        if (array[midIndex] == array[0] && array[midIndex] != array[length - 1]) {
            this.minNumberInRotateArray(Arrays.copyOfRange(array, midIndex + 1, length));
        }
        // 后两点相同
        if (array[midIndex] != array[0] && array[midIndex] == array[length - 1]) {
            this.minNumberInRotateArray(Arrays.copyOfRange(array, 0, midIndex + 1));
        }
        // 正常情况
        if (array[midIndex] < array[0]) {
            this.minNumberInRotateArray(Arrays.copyOfRange(array, 0, midIndex + 1));
        } else {
            this.minNumberInRotateArray(Arrays.copyOfRange(array, midIndex + 1, length));
        }

        return 0;

    }

¶For版

/**
     * 思路: 二分法
     * 缩小范围
     * !!!!!!!注意审题：是非减序，没说不能相同
     * !!!!!!!注意审题：是非减序，没说不能相同
     * !!!!!!!注意审题：是非减序，没说不能相同
     * for 版
     */
    private int method2(int[] array) {

        while (true) {

            int length = array.length;
            if (length == 0) {
                return 0;
            }
            if (length == 1) {
                return array[0];
            } else if (length == 2) {
                return Math.min(array[0], array[1]);
            }
            int midIndex = (length - 1) / 2;
            // 正序
            if (array[midIndex] > array[0] && array[midIndex] < array[length - 1]) {
                return array[0];
            }
            // 倒序
            if (array[midIndex] < array[0] && array[midIndex] > array[length - 1]) {
                return array[length - 1];
            }
            // 三点相同
            if (array[midIndex] == array[0] && array[midIndex] == array[length - 1]) {
                // 舍弃最后一位
                // 问题：如果数据全部相同 todo
                array = Arrays.copyOfRange(array, 0, length - 2);
                continue;
            }
            // 前两点相同
            if (array[midIndex] == array[0] && array[midIndex] != array[length - 1]) {
                array = Arrays.copyOfRange(array, midIndex + 1, length);
                continue;
            }
            // 后两点相同
            if (array[midIndex] != array[0] && array[midIndex] == array[length - 1]) {
                array = Arrays.copyOfRange(array, 0, midIndex + 1);
                continue;
            }
            // 正常情况
            if (array[midIndex] < array[0]) {
                array = Arrays.copyOfRange(array, 0, midIndex + 1);
                continue;
            } else {
                array = Arrays.copyOfRange(array, midIndex + 1, length);
                continue;
            }

        }

    }

线程池模拟高并发

发表于 2019-03-08 | 分类于 Java | 评论数： | 阅读次数：

Integer taskCount =700;
// 锁住所有线程，等待并发执行
final CountDownLatch begin =new CountDownLatch(1);
final ExecutorService exec =Executors.newFixedThreadPool(taskCount);
for (int index =0; index < taskCount; index++){
final int NO= index +1;
Runnable run =new Runnable() {
        @Override
        public void run() {
            try {
                // 等待，所有一起执行
                begin.await();
                //开始模拟等待。。。
                //Thread.sleep((long) (Math.random() * 10000));
            }catch (InterruptedException e){
                e.printStackTrace();
            }finally {
            }
        }
    };
    exec.submit(run);
}
System.out.println("开始执行");
// begin减一，开始并发执行
begin.countDown();
//关闭执行
exec.shutdown();

Hash算法

发表于 2019-03-08 | 分类于 Java | 评论数： | 阅读次数：

取余：X % a == X & (a – 1)
注意点：

¶The default initial capacity - MUST be a power of two.

Why：为了保证得到的数组下标完全取决于 hash 值，与数组长度无关

1
2
3

16 -> 10000    15 -> 01111
32 -> 100000   31 -> 011111
64 -> 1000000  63 -> 0111111

¶为什么在定义HashMap的时候要尽量指定大小

扩容的时候回重新分配值，占用性能
尽量让hashMap 不要转红黑树，因为转红黑树非常占用性能

¶hash 高低位

为了保证尽量低位的值是不一样的

docker in docker

发表于 2019-03-08 | 分类于 Docker | 评论数： | 阅读次数：

sudo docker pull docker:dind
sudo docker run -itd --privileged --name master docker:dind
sudo docker run -itd --privileged --name master docker:18.06-dind
## 修改国内源
sed -i 's/dl-cdn.alpinelinux.org/mirrors.aliyun.com/g'/etc/apk/repositories
## 清缓存
echo 1 > /proc/sys/vm/drop_caches

docker 使用 systemctl Failed to get D-Bus connection Operation not permitted

发表于 2019-03-08 | 分类于 Docker ，踩过的坑 | 评论数： | 阅读次数：

docker run -d -name 别名 --privileged=true imageName /usr/sbin/init

window10 ubuntu安装docker

发表于 2019-03-08 | 分类于 Docker | 评论数： | 阅读次数：

windows10子系统有其特殊性，需要安装docker for windows，这个就是docker daemon，然后打开如下选项：

![docker daemon设置图](docker daemon设置图.png)

然后，执行docker -H tcp://0.0.0.0:2375 info就可以返回docker信息了。但是这样很麻烦，所以可执行如下操作

1 2	echo "export DOCKER_HOST='tcp://0.0.0.0:2375'" >> ~/.bashrc source ~/.bashrc

然后就可以直接执行docker info了。

汇编的四则运算

发表于 2019-03-08 | 分类于汇编 | 评论数： | 阅读次数：

加法

    eg：4+5
    0100
    0101 
1、异或： 0001   不考虑进位的情况下的最终值
2、与： 0100   判断是否有进位，如果==0 就是不进位, return 
3、（2）左移一位 

function add(value1, value2){
    newValue1 = (1);
    (2);
    newValue2 = (3):
    add(newValue1, newValue2);
}

减法

1 2	4+5 == 4+（-5）执行加法的逻辑

乘法

1 2	4*5 == 4个5相加循环执行加法操作

除法

1 2	5/4 5能够减去几个4

汇编二进制、十六进制常用符号

发表于 2019-03-08 | 分类于汇编 | 评论数： | 阅读次数：

单位长度：1byte

10进制	2进制	16进制
1	0000 0001	1
2	0000 0010	2
3	0000 0011	3
4	0000 0100	4
5	0000 0101	5
6	0000 0110	6
7	0000 0111	7
8	0000 1000	8
9	0000 1001	9
10	0000 1010	10
11	0000 1011	11
12	0000 1100	12
13	0000 1101	13
14	0000 1110	14
15	0000 1111	15
-1	1111 1111	FF
-2	1111 1110	FE
-3	1111 1101	FD
-4	1111 1100	FC
-5	1111 1011	FB
-6	1111 1010	FA
-7	1111 1001	F9
-8	1111 1000	F8
-9	1111 0111	F7
-10	1111 0110	F6
-11	1111 0101	F5
-12	1111 0100	F4
-13	1111 0011	F3
-14	1111 0010	F2
-15	1111 0001	F1