2019-03-05

Algorithm

Sort Algrothm

快速排序

快速排序主要的思想是分而治之，先选取一个基准数，第一次排序的时候将比基准数小的全部移到左边，而比基准数大的全部移到右边。这样就分成了两个数组，然后递归排序即可。

时间复杂度：

Worst: O(n^2)
Best: O(nLogn)

下面这种以最后一个值作为基准值。假设原数组为10, 7, 8, 9, 1, 5

第一次排序：指针为low - 1也就是-1，当找到比5小的元素时，也就是1，就将指针右移一位，并且与1交换。

当之后再也找不到比5小的元素的时候就将指针+1的索引和基准值交换

public int partition(int input[], int low, int high) {
    int pivot = input[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (input[j] < pivot) {
            i++;

            int tmp = input[i];
            input[i] = input[j];
            input[j] = tmp;
        }
    }
    int tmp = input[i + 1];
    input[i + 1] = input[high];
    input[high] = tmp;
    return i + 1;
}

public void quickSort(int input[], int low, int high) {
    if (low < high) {
        int pi = partition(input, low, high);

        quickSort(input, low, pi - 1);
        quickSort(input, pi + 1, high);
    }
}

快速排序还有另一种是有两个指针的，如果以第一个元素作为基准值，那么就先从右边找比基准值小的，找到了之后从左边开始找比基准值大的，然后交换元素，当两个指针相遇之后将基准值归为。

而如果以最后一个元素作为基准值，那么就从左边找比基准值大的，找到了之后从右边找比基准值小的，然后交换元素，当两个指针相遇之后将基准值归为。

public void sort(int input[], int low, int high) {
    if (low > high) return;
    int start = low;
    int end = high;
    int pivot = input[low];
    while (start < end) {
        while (start < end && input[end] >= pivot) {
            end--;
        }
        while (start < end && input[start] <= pivot) {
            start++;
        }
        if (start < end) {
            int tmp = input[start];
            input[start] = input[end];
            input[end] = tmp;
        }
    }
    input[low] = input[start];
    input[start] = pivot;

    sort(input, start + 1, high);
    sort(input, low, start - 1);
}

冒泡排序

冒泡排序的基本思想就是两两比较，小的往左，大的往右。

时间复杂度:

Best: n
Worst: n^2
Average: n^2

代码中的内层循环减去i的原因是每一轮排序结束之后都会把最大的移到最右边。swapped的作用是如果已经排序ok了则不需要再循环。

public void bubbleSort(int array[]) {
    for (int i = 0; i < array.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

选择排序

选择排序的主要思路是从数组中找出最小的一个数放在新的数组第一个，对剩下的数组作同样处理。

时间复杂度:

Best: n^2
Worst: n^2
Average: n^2

public void selectionSort(int array[]) {
    for (int i = 0; i < array.length; i++) {
        int min_index = i;
        for (int j = i; j < array.length; j++) {
        	if (array[j] < array[min_index]) {
            	min_index = j;
        	}
    	}
    	int tmp = array[min_index];
    	array[min_index] = array[i];
    	array[i] = tmp;
    }
}

合并排序

合并排序是先将数组拆分然后挨个合并。

时间复杂度:

Best: n*Log(n)
Worst: n*Log(n)
Average: n*Log(n)

 public void merge(int arr[], int l, int m, int r) {
    int tmp[] = new int[r - l + 1];
    int i = l;
    int j = m + 1;
    int k = 0;

    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) {
            tmp[k] = arr[i];
            i++;
        } else {
            tmp[k] = arr[j];
            j++;
        }
        k++;
    }

    while (i <= m) {
        tmp[k] = arr[i];
        i++;
        k++;
    }

    while (j <= r) {
        tmp[k] = arr[j];
        j++;
        k++;
    }
        
    for (i = l; i <= r; i++) {
        arr[i] = tmp[i - l];
    }
}

public void sort(int arr[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;

        sort(arr, l, m);
        sort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

插入排序

选择排序的思想是假设第0个元素为一张扑克牌，之后将数组中剩余的元素挨个交到你手中并放入牌堆中。

比如有个数组为12,11,13,5,6 ，12是牌堆原有的，从索引1开始拿到了11，将其插入12之前，继续拿到索引2 - 13，放在11、12之后，之后都这样处理。

时间复杂度：

Best: O(n^2)

Worst: O(n)

public void selectionSort(int array[]) {
    for (int i = 0; i < array.length; i++) {
        int min_index = i;
        for (int j = i; j < array.length; j++) {
            if (array[j] < array[min_index]) {
                min_index = j;
            }
        }
        int tmp = array[min_index];
        array[min_index] = array[i];
        array[i] = tmp;
    }
}

2019-02-19

Java

Class Loader

概述

Class文件被加载到内存中需要以下几步

加载
验证 ——
准备 | 连接阶段
解析 ——
初始化
使用
卸载

解析阶段可能在初始化之前也可能在初始化之后，为了支持Java的运行时绑定。
加载、验证、准备一定要在初始化之前完成

类初始化的时机

虚拟机严格规定了有且只有5种情况必须立即对类进行初始化：

遇到new、getstatic、putstatic、invokestatic这4条字节码指令，最常见的就是new一个对象或者访问static变量
对类进行反射调用
初始化一个类时如果其父类未被初始化时
虚拟机启动时会初始化main方法的那个类
使用JDK1.7的动态语言支持时，如果一个java.lang.MethodHandle实例最后的解析结果REF_getStatic,REF_putStatic,REF_invokeStatic的方法句柄，并且这个方法所对应的类没有进行过初始化。

类加载

主要有三步

通过一个类的全限定名来获取定义此类的二进制字节流。（例如jar、zip文件，网络等等）
将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构。（方法区存储类信息、常量和静态变量）
在内存中生成一个代表这个类的java.lang.class对象。

验证

目的是为了确保Class文件的字节流符合虚拟机的要求，并且不会危害到虚拟机。

文件格式验证：主要是验证Class文件格式的规范，并且能被当前版本的虚拟机处理。例如是否魔数CAFEBABE开头，版本是否在范围内等等
元数据验证：对类的描述进行语义分析即语法。例如是否有父类，是否继承了不应该继承的类，类中的字段或方法是否会和父类发生冲突。
字节码验证：目的是为了确保程序语义是合法并合乎逻辑的。比如类型转换是否有效等等
符号引用验证：这个阶段校验是在解析阶段中发生，即将符号引用转化为直接引用。主要是对类自身以外的信息进行匹配性校验，例如访问域是否符合规范，根据全限定名是否能找到对应的类等等。这个阶段的验证目的主要是为了解析动作能正常执行。

准备

准备阶段是正式为类变量（静态变量）分配内存并设置类变量初始值的阶段。这些变量使用的内存都将在方法区中进行分配。这时候分配的还不包括实例变量，实例变量将在对象初始化之后分配在Java堆中，并且这里为类变量设置的初始值不是代码中的默认值而是虚拟机为它赋的初始值，例如有如下这个类变量

1	public static int value = 123;

value在准备阶段之后被赋值为0而不是123，要等到类构造器方法<clinit>调用的时候才会赋值为123。但是有种特殊情况：如果这个值用final修饰，那么在编译的时候就会生成一个ConstantValue（假设123），之后在准备阶段就会直接用ConstantValue（123）赋值。

解析

解析阶段主要是将符号引用转为直接引用。这两者之间的概念参考了这篇回答：https://www.zhihu.com/question/30300585

由于编译的时候不知道class文件会被加载到内存的哪一块地址，因此只能用符号来代替，例如A要调用test()方法（假设对应的符号是#6），但是不知道test()方法会存在哪儿，只能用A.#6来表述，而当加载到了内存之后就可以将#6替换为实际的内存地址，而解析阶段干的就是这个工作。

初始化

初始化阶段是执行类构造器<clinit>方法的过程，<clinit>是由编译器自动收集类中的所有类变量的赋值动作和静态语句块中的语句合并生成的。当然也是按照顺序收集的，因此如下代码会报错

public class Test {
    static {
        i = 0;                  //可以赋值
        System.out.print(i);    //不能访问，会提示 Illegal forward reference
    }
    static int i = 1;
}

对于class来说，子类的<clinit>方法执行之前一定会执行父类的，但对接口来说并不需要先执行父类的<clinit>方法，只有在使用的时候才会执行。

<clinit>方法对于类或接口来说不是必须的，如果没有静态语句块或者类变量的话，编译器可以不为这个class生成<clinit>方法。

类加载器

类加载阶段中的“通过一个类的全限定名来获取定义此类的二进制字节流”被放到了JVM外部去实现，而实现这个模块的代码就是类加载器。

每一个类加载器都有一个独立的类名称空间，比较两个类是否相等，只有在两者是由同一个加载器加载的前提下才有意义，例如ClassLoader1和ClassLoader2都加载了HelloWorld.class，但其实两个HelloWorld.class并不同。

从JVM来看三种不同的类加载器

启动类加载器(Bootstrap ClassLoader): 用C++实现，是虚拟机自身的一部分。负责加载<JAVA_HOME>\lib目录下的文件。比如 java.util.、java.io.、java.nio.*。
扩展类加载器(Extension ClassLoader): 负责加载<JAVA_HOME>\lib\ext目录下的文件。比如 swing 系列、xml 解析器等等。
应用程序类加载器(Application ClassLoader): 这个加载器是ClassLoader.getSystemClassLoader()的返回值，因此也叫系统类加载器。负责加载用户类路径下的文件。如果没有自定义，那么一般默认是使用这个类加载器。

双亲委派模型

工作原理是：如果一个类加载器收到了类加载的请求，他不会自己加载，而是委派给父类加载，并且每层如此，只有当父类加载器无法完成这个加载请求时，才会由子加载器尝试加载。

这个模型的好处一个是避免了重复加载的情况发生，保证同一个class被加载之后不会产生不同的结果，另一个是为了安全性，核心的类永远只会由启动类加载器加载。

关于破坏双亲委派模型的内容需要重新写一篇。

2019-02-13

C++

virtual table

和同事在讨论设计api接口什么方法该设置为virtual时，他说一般有子类会覆写该方法的时候用virtual修饰下，但是不能全用virtual因为开销会大一些。之后在网上查了和virtual相关的资料。

C++中关于Virtual function的意义在StackOverflow上有很多很好的解释，这里想看下具体的原理。

https://stackoverflow.com/questions/2391679/why-do-we-need-virtual-functions-in-c

有个答案是说：如果没有virtual关键字那么就是early binding，意味着这个方法的实现在编译期间就根据指针的类型来决定了，而如果有virtual关键字那么就是late binding，它的方法的实现是在运行期间根据指针所指向的那个对象所决定的。

假设有两个类：

class Animal
{
    public:
        void eat() { std::cout << "I'm eating generic food."; }
};

class Cat : public Animal
{
    public:
        void eat() { std::cout << "I'm eating a rat."; }
};

定义一个函数来传入这个类

1	void func(Animal *xyz) { xyz->eat(); }

写入main函数测试下

Animal *animal = new Animal;
Cat *cat = new Cat;

func(animal); // Outputs: "I'm eating generic food."
func(cat);    // Outputs: "I'm eating generic food."

根据early binding，在调用该函数的时候就已经决定了eat()的实现是在Animal中的。当然如果用virtual修饰的话，那么根据late binding，eat()的实现是根据new关键字之后来决定的。

那么为什么用virtual修饰的就是late binding呢，这就涉及virtual table这个late binding的特殊形式，virtual table可以理解为每个有虚函数类的一组索引，这是编译器在编译期间就设置了的，同时编译器会设置一个隐藏的指针指向这个vtable，叫做*_vptr。再决定某个函数的具体实现时就是根据这个索引来查找的。

一个基类可以抽象成这样：

class Base
 *_vptr       ---------------------->       Base VTable
 func1()      <----------------------        func1()
 func2()      <----------------------        func2()

假设D1继承Base，并且覆写了func1()，

class D1
 *_vptr            ---------------------->       Base VTable
 func1()           <----------------------        func1()
 Base::func2()     <----------------------        func2()

D1中的VTable的func1()指向D1的原因是virtual table的填充原则是选择相对于这个类most-derived的函数，由于D1覆写了func1()，因此VTable中的func1()指向的是D1中的func1()。

main函数如下：

int main()
{
    D1 d1;
    Base *dPtr = &d1;
    dPtr->function1();
}

虽然dPtr声明的时候是Base类，但是d1中的VTable赋值给了dPtr，或者说dPtr的*_vptr指向的是d1中的*_vptr，因此在调用函数的时候根据*_vptr的VTable来查找，而*_vptr的VTable其实就是d1的VTable，结果调用的是D1中的func1()。

因此virtual function需要分配的更多就是因为多了virtual table。

2019-02-01

Shell

Delete half of files randomly

Marvel中的灭霸可以打个响指就灭掉一半的人，然后在网上看到有个开源库，是执行脚本随机删除一半的文件。

https://github.com/hotvulcan/Thanos.sh

不过该库中用的是PowerShell Script，由于之前学过一点shell，这次就用shell试试，就当练习下shell的语法了。

用find命令列出路径下的所有文件，这个脚本是这样

1 2	#!/bin/sh find . -type f

其中type属性可以传递以下的参数，表示需要找到什么类型的文件

-type c

File is of type c:

b      block (buffered) special

c      character (unbuffered) special

d      directory

p      named pipe (FIFO)

f      regular file

l      symbolic link; this is never true if the -L option or the  -follow  option  is  in  effect,
       unless the symbolic link is broken.  If you want to search for symbolic links when -L is in
       effect, use -xtype.

s      socket

D      door (Solaris)

由于是随机删除一半，因此我们需要把find输出的内容砍掉一半并且打乱。打乱需要用到shuf指令，mac上这个命令默认不支持需要执行brew install coreutils安装下。

shuf可以传递-n的参数，表示最多输出的行数。

这时候指令变成了find . -type f | shuf -n $[总文件数/2]。

还需要获取到总文件数，可以用wc(Word count)来统计。由于文件名是按行输出，因此我们需要使用-l参数来统计行数。

这时候脚本变成了

#!/bin/sh
count=`find . -type f | wc -l`
echo $[count/2]
find . -type f | shuf -n  $[count/2]

接下来只需要把find并且用shuf打乱后的结果放在rm -rf后面，需要用到xargs指令。

xargs表示可以把输出传递给xargs之后的指令。最后生成的脚本就是这样的，功能就是随机删除path路径下一半的文件。

#!/bin/sh
count=`find . -type f | wc -l`
echo $[count/2]
find [path] -type f | shuf -n  $[count/2] | xargs rm -rf

2019-01-16

C++

make_shared vs shared_ptr

最近在使用shared_from_this的时候发生了crash，具体原因是throw_bad_weak_ptr，查了Stack Overflow，root cause是因为想在object A上使用shared_from_this,但是却没有一个shared_ptr指向他，这违反了使用shared_from_this的前提条件：至少有一个shared_ptr被创建并指向A。

查了下代码发生确实在实例化的时候是用new出来的裸指针

1	ObjectA m_ObjectA = new ObjectA();

应该变成

1	shared_ptr<ObjectA> m_ObjectA = make_shared<ObjectA>();

但是shared_ptr又有两种创建方式

1 2	std::shared_ptr<Object> p1 = std::make_shared<Object>("foo"); std::shared_ptr<Object> p2(new Object("foo"));

最主要的差别在于make_shared执行一次堆分配(将shared_ptr执行的两次堆分配合在一起)，而shared_ptr会执行两次堆分配。由于make_shared只执行一次堆分配因此效率更高。但make_shared只有一次堆分配，因此只有当两者都没有被引用时才会释放。

Shared_ptr：
1. 引用计数
2. 对象数据
Make_shared：
1. 引用计数和对象数据

2018-12-19

Algorithm

Power of N

在判断是否为n的次方时发现有很多种有意思的解法。当然最容易想到的是一定是不断除n，观察最后是否能除干净。这里以2为例子，之后都可以讲2替换成3或者i来使用loop。

public  boolean isPowerOfTwo(int n) {
    if (n < 1) return false;
    while (n % 2 == 0) {
         n /= 2;
    }
    return n == 1;
}

2的次方

由于如果n是2的次方，那么转换成2进制一定会是1 + n个0的形式。因此可以考虑将其转为2进制然后再判断

public  boolean isPowerOfTwo(int n) {
    if (n < 1) return false;
    String str = Integer.toBinaryString(n);
    System.out.println(str);
    char array[] = str.toCharArray();
    if (array[0] != '1') return false;
    for (int i = 1; i < array.length; i++) {
        if (array[i] != '0') return false;
    }
    return true;
}

网上还看到一种比较tricky的，那就是如果n是2的次方，那么n-1对应的二进制一定全是1，只要将两者做与运算即可

public  boolean isPowerOfTwo(int n) {
    if (n < 1) return false;
    int ret = n & (n - 1);
    return ret == 0;
}

还可以使用正则表达式来对n的二进制进行判断

public  boolean isPowerOfTwo(int n) {
    if (n < 1) return false;
    String str = Integer.toBinaryString(n);
    return str.matches("^10*$");
}

3的次方

Java中提供了将传入的数转化成你想要的进制数，Integer.toString(n, radix)，意思是将n转化为radix进制的数。

1 2	Integer.toString(8, 2) -> log2(8) = 3, return 1000 Integer.toString(81, 3) -> log3(81) = 4, return 10000

因此可以使用这个api然后判断是否为1 + n个0的形式

public static boolean isPowerOfThree(int n) {
    String baseChange = Integer.toString(n, 3);
    return baseChange.matches("^10*$");
}

还有就是用数学上的log公式了，logb(n) / logb(m) = logm(n),同时由于Math的log方法返回的是double类型，需要用 % 1 是否为零来判断是否为integer类型。

1
2
3

public static boolean isPowerOfThree(int n) {
    return (Math.log10(n) / Math.log10(3)) % 1 == 0;
}

最后一种也非常的tricky，由于int类型是有范围的，因此可以取最大的3的次方数来除以n。

1
2
3

public boolean isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

4的次方

由于4的次方和2的次方，因此可以在2的次方上过滤。首先4的次方一定也是1 + n个0的形式，但不同的是它的零的个数一定是偶数。

1
2
3

public  boolean isPowerOfFour(int num) {
    return Integer.bitCount(num) == 1 && (Integer.toBinaryString(num).length() - 1) % 2 == 0;
}

还有种方式同样是用二进制，由于4的次方数转化成2进制之后，1所在的位置一定是奇数位，从0计数
eg.
8 -> 1000
16 -> 10000
32 -> 100000
因此只需要过滤到偶数位的即可

num&(num-1)是为了判断是否为2的次方，而由于5 -> 0101，是用来过滤偶数位的1。

1	return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;

2018-12-07

Java

HashMap Infinite Loop

最近在网上看到HashMap无限循环的情况，感觉很有意思，因此记录一下。

Load factor

先来确认下HashMap默认的容量是16，Load factor则是0.75,Load factor的意思是当容量超过了16 * 0.75（12）的时候，该HashMap就会扩容，也就是说当存入第13个键值对的时候，Hash
map就会扩容，也就是rehashing操作。

/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

Rehashing

Rehashing操作中主要干了以下几件事：

建立一个双倍于之前size的数组
将键值对从旧数组转移到新数组
键值对会反向添加因为每次在新的数组中插入键值对都是从头部插入的

Infinite Loop

由于HashMap是非线程安全的，因此当线程1和线程2同时想插入第13个键值对的时候可能会发生无限循环的情况。

扩容这一块jdk1.8前后不太一样，在1.8中使用了两个Node来确保transfer之后顺序不会改变。

//jdk 1.8之前
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

//jdk 1.8之后

final Node<K,V>[] resize() {
                    ......
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                    ......
}

旧数组中index为0的链表结构为 90 -> 1 -> null，假设新数组的index依旧为0。

首先线程1执行，准备插入第13个键值对，这时候需要扩容，就会调用resize方法，当执行完了第一行代码next = e.next;，这时候线程2开始执行。

线程2全部执行完之后，新数组中index为0的链表结构为 1 -> 90 -> null。

这时候1继续执行，90移到新数组，1从队头插入，新index 0变成了1 -> 90，然而由于线程2将1的next赋值为90，（正常情况1的next是null），然后1的next也就是90继续移动到新数组，同样的插入队头，这时的新index 0的数据结构变成了90(由线程2设置的) -> 1 -> 90。

那么其实变相等于90的next指向1，1的next指向90，如果这时候再来对index为0的链表进行put操作就会陷入无限循环中。

参考文章：http://javabypatel.blogspot.com/2016/01/infinite-loop-in-hashmap.html

2018-12-04

Algorithm

Traversal Binary Tree

遍历二叉树主要有三种方式

中序(Inorder)
前序(Preorder)
后序(Postorder)

假设有一个这样的二叉树
5
/ \
1 3
/ \ / \
4 2 6 7

前序：5 - 1 - 4 - 2 - 3 - 6 - 7
后序：4 - 2 - 1 - 6 - 7 - 3 - 5
中序：4 - 1 - 2 - 5 - 6 - 3 - 7

然后看下如何用代码实现这些,可以看到区别在于是先遍历还是先处理节点上的数据。

private static void printPostorder(List list, TreeNode node) {
    if (node == null) return;
    printPostorder(list, node.left);
    printPostorder(list, node.right);
    list.add(node.val);
}

private static void printPreorder(List list, TreeNode node) {
    if (node == null) return;
    list.add(node.val);
    printPreorder(list, node.left);
    printPreorder(list, node.right);
}

private static void printInorder(List list, TreeNode node) {
    if (node == null) return;
    printInorder(list, node.left);
    list.add(node.val);
    printInorder(list, node.right);
}

除了递归能遍历二叉树以外，我们还可以用stack来实现二叉树的遍历

public static void visitWithStackPreorder(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode tmp = stack.pop();
        System.out.println(tmp.val);
        if (tmp.right != null) {
            stack.push(tmp.right);
        }
        if (tmp.left != null) {
            stack.push(tmp.left);
        }

    }
}

public static void visitWithStackInorder(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    TreeNode tmp = stack.pop();
    while (!stack.empty() || tmp != null) {
        while (tmp != null) {
            stack.push(tmp);
            tmp = tmp.left;
        }
        tmp = stack.pop();
        System.out.println(tmp.val);
        tmp = tmp.right;
    }
}

public static void visitTreeWithStackPostorder(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur;
    cur = root;
    while (cur != null || !stack.empty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            TreeNode tmp = stack.peek().right;
            //检查右边是否还有节点
            if (tmp == null) {
                tmp = stack.pop();
                System.out.println(tmp.val);
                while (!stack.empty() && tmp == stack.peek().right) {
                    tmp = stack.pop();
                    System.out.println(tmp.val);
                }
            } else {
                cur = tmp;
            }
        }
    }
}

除了stack还有一种叫Morris Traversal的遍历方式，这种方法连stack都不需要

public static void morrisPreorderTraverse(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            System.out.println(cur.val);
            cur = cur.right;
        } else {
            TreeNode pre = cur.left;
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }

            if (pre.right == cur) {
                pre.right = null;
                cur = cur.right;
            } else {
                pre.right = cur;
                System.out.println(cur.val);
                cur = cur.left;
            }
        }
    }
}

参考文章：http://www.learn4master.com/algorithms/morris-traversal-inorder-tree-traversal-without-recursion-and-without-stack

2018-12-03

Algorithm

Dynamic Programming

动态规划

动态规划的原则就是讲复杂问题分为若干个简单的子问题依次求解，在某些地方有那么一点像递归，不过由于递归的循环调用会使得某些计算重复，使用动态规划的优化思路就是保存已经计算好的值。

Fibonacci

Fibonacci以前都是用递归写的，但是这样的话就会有很多重复的值或者是已经计算好的值没有重复利用。

private void fib() {
    fibresult[0] = 1;
    fibresult[1] = 1;
    for (int i = 2; i < n; i++) {
        fibresult[i] = fibresult[i - 1] + fibresult[i - 2];
    } 
}

不过如图中所示，fib(4)调用了两次，fib(3)调用了三次等等。

因此如果能把fib(4)和fib(i)保存起来的话会好很多。

private void fib() {
    DP[0] = DP[1] = 1; 
    for (i = 2; i <= n; i++) {
        DP[i] = DP[i-1] + DP[i-2];
    }
}

卖酒的最高收益

酒架上有N瓶酒，每瓶酒的价格不同，分别为pi，酒的价格随着年份增长，比如一瓶酒原来10，假设今年为year 1，等到了year y，酒的价格就变为了10 * y。

现在你想把这些酒全卖了，但是有两个规定，一是一年只能卖一瓶，二是每次都只能从酒架上的最左边或者最右边卖酒。要求出最高收益。

比如有这四瓶酒，p1=1, p2=4, p3=2, p4=3，那么最高收益就是1 1 + 3 2 + 2 3 + 4 4 = 29。

很明显需要用到递归，每一次都取最左边的收益和最右边收益之间的最大值即可。

private static int maximumSellWineProfie(int year, int begin, int end) {
    if (begin > end) {
        return 0;
    }
    return Math.max(maximumSellWineProfie(year + 1, begin + 1, end) + year * p[begin],
            maximumSellWineProfie(year + 1, begin, end - 1) + year * p[end]);
}

不过year这个变量似乎是用不上的，因为他是可以根据酒瓶的数量计算出来的。因此将year去掉的话

private static int maximumSellWineProfie(int begin, int end) {
    if (begin > end) {
        return 0;
    }
    int year = p.length - (end - begin + 1) + 1;
    return Math.max(maximumSellWineProfie(begin + 1, end) + year * p[begin],
                    maximumSellWineProfie(begin, end - 1) + year * p[end]);
}

ok，现在开始有点像之前的Fibonacci了，那么接下来的任务就是将计算的值保存下来，因为有两个变量所以需要一个二维数组。

int N;
int p[N];
int cache[N][N];

private int profit(int be, int en) {
    if (be > en)
        return 0;
    // initial value
    if (cache[be][en] != -1)
        return cache[be][en];
    int year = N - (en-be+1) + 1;
    return cache[be][en] = max(
        profit(be+1, en) + year * p[be],
        profit(be, en-1) + year * p[en]);
}

可以发现动态规划也不是一步实现的，而是先用递归或者循环，然后删除一些不需要的变量，避免重复的计算加以优化即可。

2018-11-26

C++

使用Jansson产生的引用计数bug

最近在使用Jannson的时候，偶现了一个bug。

1	JanssonTest(83740,0x1003ac380) malloc: *** error for object 0x100600058: incorrect checksum for freed object - object was probably modified after being freed.

跟踪了一下代码发现是在free的时候出现的问题。由于是free的时候出现的，因此crash的堆栈还有所不同。

void jsonp_free(void *ptr)
{
    if(!ptr)
        return;

    (*do_free)(ptr);
}

可以看到是在执行do_free的时候产生的crash。一开始产生的堆栈一直指向的是将json转成string的一个函数，但是仔细查看了之后发现这一块逻辑没有问题，考虑到是在free的时候出现的问题，就去查看了free相关的函数，最后通过注释排查法找到了原因所在。

void ProximityRequestBodyBuilder::buildInitConnection(const InitConnectionRequest& request,std::string & requestBody){
    std::string tmp;
    json_t *methodParaJson = json_object();
    
    tmp = request.displayName;
    json_object_set_new(methodParaJson, "displayName", json_string(tmp.c_str()));
    
    json_t *requestJson = wrapper(methodParaJson, "initConnection");

    char *requestStr = json_dumps(requestJson, 0);
    requestBody = std::string(requestStr);
    
    free(requestStr);
    json_decref(requestJson);
    json_decref(methodParaJson);//导致了crash
}

json_t *ProximityRequestBodyBuilder::wrapper(json_t *parameterJson, const std::string &methodName)
{
    json_t *root = json_object();
    
    //wrap token
    json_object_set_new(root, "token", json_string("ed2f"));
    
    //wrap method
    json_t *methodPara = json_object();
    json_object_set_new(methodPara, methodName.c_str(), parameterJson);

    //wrap request
    json_object_set_new(root, "request", methodPara);

    return root;
}

在Jannson中使用的引用计数法，也就是哪里用到了这个对象就+1，对应的函数是json_incref，如果这个对象之后没用的话要-1，对应的函数是json_decref。

但是在调用了json_decref(requestJson)之后，methodParaJson的引用计数也-1，那么之后再调用json_decref(methodParaJson)，就出现了各种问题。

至于两者为什么会有耦合关系，是因为用requestJson将methodParaJson包装了一次。不过这边既然他自动给我-1，那讲道理在包装的时候应该也自动+1比较合理。

后来check了一下源码才发现不应该用json_object_set_new,而应该用json_object_set。因为json_object_set才是真正+1的地方，而json_object_set_new并没有+1，其实感觉new这个关键字有一点误导人。

int json_object_set(json_t *object, const char *key, json_t *value)
{
    return json_object_set_new(object, key, json_incref(value));
}

int json_object_set_new(json_t *json, const char *key, json_t *value)
{
    if(!key || !utf8_check_string(key, strlen(key)))
    {
        json_decref(value);
        return -1;
    }

    return json_object_set_new_nocheck(json, key, value);
}

关于这点已经提了issue：https://github.com/akheron/jansson/issues/449