Sep 23, 2014 · Sep 23, 2014 · Sep 25, 2014 · Sep 25, 2014 · Sep 25, 2014 · Sep 26, 2014
diff --git a/Divide2/Pow.java b/Divide2/Pow.java
 package Algorithms.Divide2;

 public class Pow {
    public static void main(String[] strs) {
        System.out.println(pow(-3, -2147483648));

    }

    public static double pow(double x, int n) {
        if (x == 0) {
            return 0;
        }

        if (x == 1 || n == 0) {
            return 1;
        }

        // Because when we deal with -2147483648, we can't get right -n
        // cause -n == n when it is -2147483648.
        // 注意 这样写是不行的，因为-n在n到最小值会出错，
        // int的最小值（负数）取-n仍然是n 这样就错了。
        if (n < 0) {
            double ret1 = x * pow(x, -(1 + n));
            return 1/(double)ret1;
        }

        int m = n%2;

        // count
        double ret = pow(x, n/2);
        ret *= ret;
        if (m == 1) {
            ret *= x;
        }

        return ret;
    }
 }
diff --git a/Flatten.java b/Flatten.java
 package Algorithms;
 import java.util.Stack;

 import Algorithms.tree.TreeNode;



 public class Flatten {
diff --git a/GraphDemo.java b/GraphDemo.java
 package Algorithms;

 import java.util.ArrayList;

 public class GraphDemo {
    private static int M = Integer.MAX_VALUE;  // 表示此路不可通

    // http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
    // 以上为不能再优美的C语言实现。
    public static void main(String[] args) {
        int[][] w = {  // 用邻接表矩阵表示的无向图
                {0, 3, 2000, 7, M},
                {3, 0, 4, 2, M},
                {M, 4, 0, 5, 4},
                {7, 2, 5, 0, 6},
                {M, M , 4, 6, 0}
        };

        int[][] w2 = {  // 用邻接表矩阵表示的无向图
                {0, 10, M, 30, 100},
                {M, 0, 50, M, M},
                {M, M, 0, M, 10},
                {M, M, 20, 0, 60},
                {M, M, M, M, 0}
        };

        int start = 0;

        int[] shortPath = dijkstra(w2, start);

        for (int i = 0; i < shortPath.length; i++) {
            System.out.println("The shortest path length from start to " + i + " is:" + shortPath[i]);
        }
    }

    public static int[] dijkstra(int[][] graph, int src) {
        if (graph == null || graph.length == 0 || graph[0].length == 0) {
            return null;
        }

        // get to know the number of the vertexs.
        int v = graph.length;

        // We need a indicator to know if we have visited the vertex.
        boolean visit[] = new boolean[v];

        // record the length result.
        int[] pathLen = new int[v];

        // record the path.
        ArrayList<ArrayList<Integer>> path = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < v; i++) {
            path.add(new ArrayList<Integer>());
            path.get(i).add(0);
            path.get(i).add(i);
        }

        // setup the source vertex;
        visit[0] = true;
        pathLen[0] = 0;

        // stop when all the vertices has been added into the result set.
        for (int i = 0; i < v - 1; i++) {

            int minLen = M;
            int minIndex = -1;
            for (int j = 0; j < v; j++) {
                // sometimes there is no route, so just let equal also return.
                // so we use graph[src][j] <= minLen
                if (!visit[j] && graph[src][j] <= minLen) {
                    minLen = graph[src][j];
                    minIndex = j;
                }
            }

            // get the new shortest path, add it into the solution set.
            visit[minIndex] = true;
            pathLen[minIndex] = graph[src][minIndex];

            // update all the neighbors of the new vertex.
            for (int k = 0; k < v; k++) {
                // if the path which pass the minIndex is shorter than the former path,
                // just update it.
                if (!visit[k]
                        && graph[src][minIndex] != M
                        && graph[minIndex][k] != M
                        && graph[src][minIndex] + graph[minIndex][k] < graph[src][k]) {
                    graph[src][k] = graph[src][minIndex] + graph[minIndex][k];

                    path.set(k, new ArrayList<Integer>(path.get(minIndex)));
                    path.get(k).add(k);
                }
            }
        }

        for (ArrayList<Integer> array: path) {
            System.out.println(array.toString());
        }

        return pathLen;
    }

 }
diff --git a/InOrderTraversal.java b/InOrderTraversal.java
 import java.util.ArrayList;
 import java.util.Stack;

 import Algorithms.tree.TreeNode;


 public class InOrderTraversal {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
diff --git a/IsSymmetric.java b/IsSymmetric.java

 import java.util.ArrayDeque;

 import Algorithms.tree.TreeNode;

 public class IsSymmetric {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
diff --git a/KthSort.java b/KthSort.java
 packageAlgorithms;

 importjava.util.HashMap;

 publicclassKthSort {
 publicstaticclassGraph {
 Stringname;
 HashMap<Graph,Integer>subs;
 publicGraph(Stringname) {
 this.name =name;
        }
    }

 publicstaticvoidmain(String[]strs) {
 //        int[] input = new int[]{1,2,4,3,9,11,0};
 //        sort(input);
 //        for(int n: input) {
 //            System.out.print(n + " ");
 //        }
 Graphc1 =newGraph("c1");

 //for()
    }

 publicstaticvoidsort(int[]input) {
 if (input ==null) {
 return;
        }

 intlen =input.length;
 for (inti =1;i <len;i++) {
 intcur =input[i];
 intj =i -1;
 while (j >=0 &&input[j] >cur) {
 input[j +1] =input[j];
 j--;
            }

 input[j +1] =cur;
        }
    }

 }
diff --git a/ListNodeDemo.java b/ListNodeDemo.java
        ListNode c1 = new ListNode(1);
        ListNode c2 = new ListNode(12);
        c1.next = c2;
        c2.next = n1;
 //c2.next = n1;

        //ListNode mergeNode = mergeSortedListRec(m1, c1);
        ListNode mergeNode = mergeLink(m1, c1);
        //ListNode mergeNode2 = mergeLink(m1, c1);
        //ListNode mergeNode = mergeSortedList(m1, c1);
        //printList(mergeNode);
        printList(mergeNode);
        //printList(mergeNode2);

        System.out.println();

        n1.next = n2;
        n2.next = n3;
        return dummyNode.next;
    }

    static class Node {
        Node next;
        int val;
        Node (int val) {
            this.val = val;
        }
    }

    public static ListNode mergeLink (ListNode aLink, ListNode bLink) {
        ListNode dummy = new ListNode(0);

        ListNode root = dummy;

        while (aLink != null && bLink != null) {
            if (aLink.val < bLink.val) {
                dummy.next = aLink;
                dummy = aLink;
                aLink = aLink.next;

            } else {
                dummy.next = bLink;
                dummy = bLink;
                bLink = bLink.next;

            }
        }

        if (aLink != null) {
            dummy.next = aLink;
        } else {
            dummy.next = bLink;
        }

        return root.next;
    }

    /*
     * 先完成的算法，应该会简单一点儿。
     * 简直是优雅的算法啊！太棒了！只不过 为什么自己很难想出这么棒的算法呢？
diff --git a/Max_path_BinaryTree.java b/Max_path_BinaryTree.java
 package Algorithms;
 import java.util.ArrayList;

 import Algorithms.tree.TreeNode;


 public class Max_path_BinaryTree {
    public static void main(String args[]){
diff --git a/Populate2.java b/Populate2.java
 package Algorithms;

 import Algorithms.tree.TreeLinkNode;

 public class Populate2 {
    public static void main(String[] args) {
        TreeLinkNode root = new TreeLinkNode(2);
diff --git a/PostOrder.java b/PostOrder.java
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,38 @@
		package Algorithms.Divide2;

		public class Pow {
		public static void main(String[] strs) {
		System.out.println(pow(-3, -2147483648));

		}

		public static double pow(double x, int n) {
		if (x == 0) {
		return 0;
		}

		if (x == 1 \|\| n == 0) {
		return 1;
		}

		// Because when we deal with -2147483648, we can't get right -n
		// cause -n == n when it is -2147483648.
		// 注意这样写是不行的，因为-n在n到最小值会出错，
		// int的最小值（负数）取-n仍然是n 这样就错了。
		if (n < 0) {
		double ret1 = x * pow(x, -(1 + n));
		return 1/(double)ret1;
		}

		int m = n%2;

		// count
		double ret = pow(x, n/2);
		ret *= ret;
		if (m == 1) {
		ret *= x;
		}

		return ret;
		}
		}
Original file line number	Diff line number	Diff line change
		@@ -1,6 +1,8 @@
		package Algorithms;
		import java.util.Stack;

		import Algorithms.tree.TreeNode;



		public class Flatten {
Expand Down
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,103 @@
		package Algorithms;

		import java.util.ArrayList;

		public class GraphDemo {
		private static int M = Integer.MAX_VALUE; // 表示此路不可通

		// http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
		// 以上为不能再优美的C语言实现。
		public static void main(String[] args) {
		int[][] w = { // 用邻接表矩阵表示的无向图
		{0, 3, 2000, 7, M},
		{3, 0, 4, 2, M},
		{M, 4, 0, 5, 4},
		{7, 2, 5, 0, 6},
		{M, M , 4, 6, 0}
		};

		int[][] w2 = { // 用邻接表矩阵表示的无向图
		{0, 10, M, 30, 100},
		{M, 0, 50, M, M},
		{M, M, 0, M, 10},
		{M, M, 20, 0, 60},
		{M, M, M, M, 0}
		};

		int start = 0;

		int[] shortPath = dijkstra(w2, start);

		for (int i = 0; i < shortPath.length; i++) {
		System.out.println("The shortest path length from start to " + i + " is:" + shortPath[i]);
		}
		}

		public static int[] dijkstra(int[][] graph, int src) {
		if (graph == null \|\| graph.length == 0 \|\| graph[0].length == 0) {
		return null;
		}

		// get to know the number of the vertexs.
		int v = graph.length;

		// We need a indicator to know if we have visited the vertex.
		boolean visit[] = new boolean[v];

		// record the length result.
		int[] pathLen = new int[v];

		// record the path.
		ArrayList<ArrayList<Integer>> path = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < v; i++) {
		path.add(new ArrayList<Integer>());
		path.get(i).add(0);
		path.get(i).add(i);
		}

		// setup the source vertex;
		visit[0] = true;
		pathLen[0] = 0;

		// stop when all the vertices has been added into the result set.
		for (int i = 0; i < v - 1; i++) {

		int minLen = M;
		int minIndex = -1;
		for (int j = 0; j < v; j++) {
		// sometimes there is no route, so just let equal also return.
		// so we use graph[src][j] <= minLen
		if (!visit[j] && graph[src][j] <= minLen) {
		minLen = graph[src][j];
		minIndex = j;
		}
		}

		// get the new shortest path, add it into the solution set.
		visit[minIndex] = true;
		pathLen[minIndex] = graph[src][minIndex];

		// update all the neighbors of the new vertex.
		for (int k = 0; k < v; k++) {
		// if the path which pass the minIndex is shorter than the former path,
		// just update it.
		if (!visit[k]
		&& graph[src][minIndex] != M
		&& graph[minIndex][k] != M
		&& graph[src][minIndex] + graph[minIndex][k] < graph[src][k]) {
		graph[src][k] = graph[src][minIndex] + graph[minIndex][k];

		path.set(k, new ArrayList<Integer>(path.get(minIndex)));
		path.get(k).add(k);
		}
		}
		}

		for (ArrayList<Integer> array: path) {
		System.out.println(array.toString());
		}

		return pathLen;
		}

		}
Original file line number	Diff line number	Diff line change
Expand Up		@@ -2,6 +2,8 @@
		import java.util.ArrayList;
		import java.util.Stack;

		import Algorithms.tree.TreeNode;


		public class InOrderTraversal {
		public ArrayList<Integer> inorderTraversal(TreeNode root) {
Expand Down
Original file line number	Diff line number	Diff line change
Expand Up		@@ -2,6 +2,8 @@

		import java.util.ArrayDeque;

		import Algorithms.tree.TreeNode;

		public class IsSymmetric {
		public boolean isSymmetric(TreeNode root) {
		if (root == null) {
Expand Down
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,43 @@
		packageAlgorithms;

		importjava.util.HashMap;

		publicclassKthSort {
		publicstaticclassGraph {
		Stringname;
		HashMap<Graph,Integer>subs;
		publicGraph(Stringname) {
		this.name =name;
		}
		}

		publicstaticvoidmain(String[]strs) {
		// int[] input = new int[]{1,2,4,3,9,11,0};
		// sort(input);
		// for(int n: input) {
		// System.out.print(n + " ");
		// }
		Graphc1 =newGraph("c1");

		//for()
		}

		publicstaticvoidsort(int[]input) {
		if (input ==null) {
		return;
		}

		intlen =input.length;
		for (inti =1;i <len;i++) {
		intcur =input[i];
		intj =i -1;
		while (j >=0 &&input[j] >cur) {
		input[j +1] =input[j];
		j--;
		}

		input[j +1] =cur;
		}
		}

		}
Original file line number	Diff line number	Diff line change
Expand Up		@@ -57,11 +57,15 @@ public static void main(String[] args) {
		ListNode c1 = new ListNode(1);
		ListNode c2 = new ListNode(12);
		c1.next = c2;
		c2.next = n1;
		//c2.next = n1;

		//ListNode mergeNode = mergeSortedListRec(m1, c1);
		ListNode mergeNode = mergeLink(m1, c1);
		//ListNode mergeNode2 = mergeLink(m1, c1);
		//ListNode mergeNode = mergeSortedList(m1, c1);
		//printList(mergeNode);
		printList(mergeNode);
		//printList(mergeNode2);

		System.out.println();

		n1.next = n2;
		n2.next = n3;
Expand DownExpand Up		@@ -433,6 +437,42 @@ public static ListNode mergeSortedList(ListNode head1, ListNode head2) {
		return dummyNode.next;
		}

		static class Node {
		Node next;
		int val;
		Node (int val) {
		this.val = val;
		}
		}

		public static ListNode mergeLink (ListNode aLink, ListNode bLink) {
		ListNode dummy = new ListNode(0);

		ListNode root = dummy;

		while (aLink != null && bLink != null) {
		if (aLink.val < bLink.val) {
		dummy.next = aLink;
		dummy = aLink;
		aLink = aLink.next;

		} else {
		dummy.next = bLink;
		dummy = bLink;
		bLink = bLink.next;

		}
		}

		if (aLink != null) {
		dummy.next = aLink;
		} else {
		dummy.next = bLink;
		}

		return root.next;
		}

		/*
		* 先完成的算法，应该会简单一点儿。
		* 简直是优雅的算法啊！太棒了！只不过为什么自己很难想出这么棒的算法呢？
Expand Down
Original file line number	Diff line number	Diff line change
		@@ -1,4 +1,7 @@
		package Algorithms;

		import Algorithms.tree.TreeLinkNode;

		public class Populate2 {
		public static void main(String[] args) {
		TreeLinkNode root = new TreeLinkNode(2);
Expand Down