树的子结构

2018-08-20

树的子结构

给定两棵树，判断第二棵树是不是第一棵树的子树。

规定空树不是任意树的子结构。

想到用将树的结构转为先序，中序，或者后序序列，然后比较序列的包含关系，如果两颗树的同一个序列，比如先序序列，前树包含后树，那么返回true，否则返回false.

代码如下：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.ArrayList;
public class Solution {
   public  void pre(TreeNode root,ArrayList<Integer> list) {
		 if(root==null) {
			 return;
		 }
		 list.add(root.val);
		 pre(root.left,list);
		 pre(root.right,list);
	 }
   public  boolean HasSubtree(TreeNode root1,TreeNode root2) {
    	
    	 if(root2==null) {
    		 return false;
    	 }
    	 
    	 if(root1==null) {
    		 return false;
    	 }
    	 
    	 ArrayList<Integer> list1=new ArrayList<Integer>();
    	 ArrayList<Integer> list2=new ArrayList<Integer>();
    	 
    	 pre(root1,list1);
    	 pre(root2,list2);
    	 
    	 return list1.containsAll(list2);
     }
    
}

不借用外部结构，只通过树的结点匹配与否来实现，递归版本如下：

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root2 == null || root1 == null) {
            return false;
        }
        
        boolean res = false;
        if (root1.val == root2.val) {
            res = matchTree(root1, root2);
        }
        if (!res) {
            res = matchTree(root1.left, root2);
        }
        if (!res) {
            res = matchTree(root1.right, root2);
        }
        return res;
    }
    
    private boolean matchTree(TreeNode node1, TreeNode node2) {
        if (node2 == null) {
            return true;
        }
        if (node1 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        }
        return matchTree(node1.left, node2.left) && matchTree(node1.right, node2.right);
    }
}

展开全文 >>

合并排序链表

2018-08-20

合并两个有序的链表

两个有序链表的合并，一开始想到了插入排序的思想，但是算法时间复杂度太大了o(n2)，代码如下：

/**
 * 合并两个有序的链表，插入排序思想，时间复杂度o(n2)
 */
public class MergeList {
    public static ListNode Merge(ListNode list1,ListNode list2) {
        if (list2 == null) {
            return list1;
        }
        if (list1 == null) {
            return list2;
        }
        ListNode res = null;
        if (list1.val <= list2.val) {
            res = list1;
            while (list2 != null) {
                ListNode temp1 = list1;
                while (list1 != null && list1.val < list2.val) {
                    temp1 = list1;
                    list1 = list1.next;
                    if (list1 == null) {
                        break;
                    }
                }
                ListNode temp2 = list2.next;
                temp1.next = list2;
                list2.next = list1;
                list2 = temp2;
            }
            return res;
        } else {
            res = list2;
            while (list1 != null) {
                ListNode temp2 = null;
                while (list2 != null && list2.val < list1.val) {
                    temp2 = list2;
                    list2 = list2.next;
                    if (list2 == null) {
                        break;
                    }
                }
                ListNode temp1 = list1.next;
                temp2.next = list1;
                list1.next = list2;
                list1 = temp1;
            }
            return res;
        }

    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(6);
        ListNode l4 = new ListNode(1);
        ListNode l5 = new ListNode(3);
        ListNode l6 = new ListNode(5);

        l1.next = l2;
        l2.next = l3;

        l4.next = l5;
        l5.next = l6;
        ListNode res = Merge(l1, l4);
        while (res != null) {
            System.out.println(res.val);
            res = res.next;
        }


    }

}

本地测试用例通过，但是牛客网在线提交失败，后来有看到了一个递归的解法，觉得很是巧妙，自己写了一遍，代码如下：

public class Solution {
    public static ListNode Merge(ListNode list1,ListNode list2) {
        if (list2 == null) {
            return list1;
        }
        if (list1 == null) {
            return list2;
        }
        if (list1.val <= list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}

展开全文 >>

二分快速幂

2018-08-20

二分快速幂

该算法用来计算a的b次方，通过将指数化为2的进制表示法，来降低乘法的运算次数，比如a的9次方，因为9 = 1001(二进制),所以可以写成a^9 = a^(2^0)*a^(2^3);这样可以将算法复杂度由o(n)将为o(logn).

public class Solution {
    public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        boolean flag = true;
        if (exponent < 0) {
            exponent = -exponent;
            flag = false;
        }
        double res = 1;
        while (exponent != 0) {
            if ((exponent & 1) == 1) {
                res *= base;
            }
            base *= base;
            exponent = exponent >> 1;
        }
        if (flag == false) {
            return (1 / res);
        } 
        return res;
  }
}