package heap;

import java.math.BigInteger;

/**
 * 最大堆最小堆性质：
 * 完全二叉树
 * left=2i;
 * right=2i+1;
 * 最大堆：除根节点外，子节点<父节点
 * 最小堆：除根节点外，子节点>父节点
 * 堆排序算法复杂度：o(n*lgn)
 * 
 * @author B.Chen
 *
 */
public class MaxHeap {

    public int heapSize;

    public int parent(int i) {
        return i / 2;
    }

    public int left(int i) {
        return 2 * i;
    }

    public int right(int i) {
        return 2 * i + 1;
    }

    public void maxHeapify(int[] a, int i) {
        int l = left(i);
        int r = right(i);
        int largest = i;
        if (l < heapSize) {
            if (a[l] > a[i]) {
                largest = l;
            }
        }
        if (r < heapSize) {
            if (a[r] > a[largest]) {
                largest = r;
            }
        }
        if (largest != i) {
            int temp = a[i];
            a[i] = a[largest];
            a[largest] = temp;
            maxHeapify(a, largest);
        }
    }

    public void builtMaxHeap(int[] a) {
        heapSize = a.length;
        for (int i = (a.length - 1) / 2; i >= 0; i--) {
            maxHeapify(a, i);
        }
    }

    public void heapSort(int[] a) {
        builtMaxHeap(a);
        for (int i = a.length - 1; i > 0; i--) {
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            heapSize = heapSize - 1;
            maxHeapify(a, 0);
        }
    }

    public static void main(String[] args) {
        MaxHeap mh = new MaxHeap();
        int[] a = new int[] { 7, 6, 4, 2, 8, 3, 1, 5, 9, 0 };
        mh.heapSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}

package graph;

import java.lang.reflect.Method;
import java.util.HashMap;
import java.util.Map;

import org.apache.log4j.Logger;

import net.sf.cglib.proxy.Enhancer;
import net.sf.cglib.proxy.MethodInterceptor;
import net.sf.cglib.proxy.MethodProxy;

public class MehtodProcessingTimesProxy implements MethodInterceptor {

    private Enhancer enhancer = new Enhancer();

    private Map<String, Long> map = new HashMap<String, Long>();

    Logger log = Logger.getLogger(MehtodProcessingTimesProxy.class);

    public Object intercept(Object o, Method method, Object[] args, MethodProxy proxy) throws Throwable {
        Long start = System.currentTimeMillis();
        Object result = proxy.invokeSuper(o, args);
        Long end = System.currentTimeMillis();
        if (!map.containsKey(method.toGenericString())) {
            map.put(method.toGenericString(), Long.valueOf(end - start));
            log.debug(method.toGenericString() + " " + (end - start) + "ms");
        }

        return result;
    }

    public Object ProxyFactory(Class clazz) {
        enhancer.setSuperclass(clazz);
        enhancer.setCallback(this);
        return enhancer.create();
    }

}

package graph;

public class ATest {

    public void method() {
        long j = 0;
        for (long i = 0; i < 1000000000; i++) {
            j += i;
        }
    }

    public void method1() {
        long j = 0;
        for (long i = 0; i < 1000000000; i++) {
            j += i;
        }
    }

    public void method2() {
        long j = 0;
        for (long i = 0; i < 1000000000; i++) {
            j += i;
        }
    }

    public void method3() {
        method();
        method1();
        method2();
        method();
    }

    public static void main(String[] args) {
        MehtodProcessingTimesProxy proxy = new MehtodProcessingTimesProxy();
        ATest t = (ATest) proxy.ProxyFactory(ATest.class);
        t.method();
        t.method1();
        t.method2();
        t.method();
        t.method3();
    }

}

package convex;

import java.util.Arrays;

/**
 * 输入一个C，
 * 再输入N个不同面值的纸币 
 * 组合成C，求出所用纸币的张数最少的张数 
 * 比如： C=100,N=5 有5个不同的面值，1，5，20，80，90
 * 最后输出的结果为2
 * 
 * 如果是排序的，复杂度为o(n^2),非排序的话，复杂度为o(n*logn+n^2) 采用的方法：贪婪算法
 * 
 * @author B.Chen
 */
public class CalMoney {

	public static int calMoney(int c, int[] array, int length) {
		int total = 0;
		if (c != 0) {
			while (c < array[length - 1]) {
				length--;
			}
			total = c / array[length - 1]
					+ calMoney(c % array[length - 1], array, length - 1);
		}
		return total;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 5, 1, 80, 20, 90, 200, 500, 700 };
		Arrays.sort(a);
		int min = 999;
		for (int i = a.length; i > 0; i--) {
			int count = calMoney(100, a, i);
			if (min > count) {
				min = count;
			}
		}
		System.out.println(min);
	}
}