<repo_name>Yujiao001/demo<file_sep>/src/com/cn/leecode/InsertInterval.java
import java.util.ArrayList;

/*
 * Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

 * You may assume that the intervals were initially sorted according to their start times.

 * Example 1:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

 * Example 2:
 * Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10]. 
 */
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class InsertInterval {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        int left = -1, right = -1;
        boolean leftIn = false, rightIn = false;
        for(int i = 0; i < intervals.size(); i++) {
            if(newInterval.start >= intervals.get(i).start) {
                left = i;
                leftIn = (newInterval.start <= intervals.get(left).end) ? true : false;
            }
            if(newInterval.end >= intervals.get(i).start) {
                right = i;
                rightIn = (newInterval.end <= intervals.get(right).end) ? true : false;
            }
        }  
        if(left == right) {
            if(leftIn && !rightIn) 
                intervals.get(right).end = newInterval.end;
            if(!leftIn && !rightIn)
                intervals.add(left + 1, newInterval);
        } else {
            intervals.get(right).start = leftIn ? intervals.get(left).start : newInterval.start;
            if(!rightIn)
                intervals.get(right).end = newInterval.end;
            for(int i = right - 1; i >= left + 1; i--) {
                intervals.remove(i);
            }
            if(leftIn)
                intervals.remove(left);
        }
        return intervals;
    }
}
<file_sep>/src/com/cn/leecode/AddBinary.java
package com.cn.leecode;

/*
 * Given two binary strings, return their sum (also a binary string).

 * For example,
 * a = "11"
 * b = "1"
 * Return "100". 
 */
public class AddBinary {
    public String addBinary(String a, String b) {
        int len = Math.max(a.length(), b.length());
        String res = "";
        int carry = 0;
        for (int i = 0; i < len; i++) {
            int ca = i < a.length() ? a.charAt(a.length() - i - 1) - '0' : 0;
            int cb = i < b.length() ? b.charAt(b.length() - i - 1) - '0' : 0;
            res = (ca + cb + carry) % 2 + res;
            carry = (ca + cb + carry) / 2;
        }
        if (carry > 0)
            res = carry + res;
        return res;
    }
}
<file_sep>/src/com/co/sort/Removal0730.java
package com.co.sort;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/*
 * 去重排序,初步理解与运用。
 */
public class Removal0730 {

	public static void main(String[] args) {
		removal();
	}
	
	public static void removal(){
		int arr[] ={0,98,6,5,1,98,6,896,896,896,0,5,1};
		//Set的特性是没有重复元素
		//TreeSet提供自动排序功能
		Set<Integer> set =new TreeSet<Integer>(new MyComparator());
		for(int i : arr){
		set.add(i);
		}

	    /*Iterator<Integer> iter = set.iterator();
	    while(iter.hasNext()){
	    	int result = (int) iter.next();
	    	System.out.print(result + " ");
	    }*/

	    for(Iterator<Integer> iter =set.iterator();iter.hasNext();){
	    	System.out.print(iter.next() + " ");
	    }
	    
	}
}

class MyComparator implements Comparator<Integer>{

	@Override
	public int compare(Integer o1, Integer o2) {
		// TODO Auto-generated method stub
		return o2.compareTo(o1);//降序排列
	}
}
<file_sep>/src/com/co/sort/SetTest.java
package com.co.sort;

import java.util.Comparator;  
import java.util.Iterator;  
import java.util.Set;  
import java.util.TreeSet;  
  
public class SetTest {  
  
    public static void main(String[] args) {  
        Set<Person> set = new TreeSet<Person>(new PersonComparator());  
          
        Person p1 =  new Person(10);  
        Person p2 =  new Person(20);  
        Person p3 =  new Person(30);  
        Person p4 =  new Person(40);  
          
        set.add(p1);  
        set.add(p2);  
        set.add(p3);  
        set.add(p4);  
          
        for(Iterator<Person> iterator = set.iterator();iterator.hasNext();){  
            System.out.print(iterator.next().score+" ");  
        }  
    }  
}  
  
class Person{  
    int score;  
      
    public Person(int score){  
        this.score = score;  
    }  
      
    public String toString(){  
        return String.valueOf(this.score);  
    }  
}  
  
class PersonComparator implements Comparator<Person>{  
  
    @Override  
    public int compare(Person o1, Person o2) {  
          
        return o1.score - o2.score;  
    }  
      
} 
<file_sep>/src/com/cn/leecode/BinaryTreeInorderTraversal.java
package com.cn.leecode;

import java.util.ArrayList;
import java.util.Stack;

import javax.swing.tree.TreeNode;

/*
 * Given a binary tree, return the inorder traversal of its nodes' values.

 * For example:
 * Given binary tree {1,#,2,3},

 *    1
 *     \
 *      2
 *     /
 *    3
 * return [1,3,2].
 * Note: Recursive solution is trivial, could you do it iteratively?
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class BinaryTreeInorderTraversal {

/************************ updated 2013/11/30 ************************/

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (root != null) {
            result.addAll(inorderTraversal(root.left));
            result.add(root.val);
            result.addAll(inorderTraversal(root.right));
        }
        return result;
    }

/**************************************************************/

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result; 
    }

/**************************************************************/

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        TreeNode cur = root;
        while(cur != null) {
            if(cur.left != null) {
                TreeNode prev = cur.left;
                while(prev.right != null && prev.right != cur) 
                    prev = prev.right;
                if(prev.right == cur) {
                    result.add(cur.val);
                    cur = cur.right;
                    prev.right = null;
                } else {
                    prev.right = cur;
                    cur = cur.left;
                }
            } else {
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }
}
<file_sep>/src/com/co/sort/QuickSort0729.java
/**
 * 
 */
package com.co.sort;

public class QuickSort0729 {

	public static void main(String[] args) {
		int[] target = {22,45,12,1,5,7,98,34,678,321,1,4,6,9,0,5,124};
        QuickSort(target,0,target.length-1);
        for(int i = 0;i< target.length;i++){
        	System.out.print(target[i] + " ");
        }
	}
	
     static void QuickSort(int[] arr,int left,int right){
    	int pivot =partion(arr,left,right);
    	if(left<pivot-1) QuickSort(arr,left,pivot-1);
    	if(right>pivot) QuickSort(arr,pivot,right);
    	
     }
    
     static int partion(int[] arr,int left,int right){
    	int pivot = arr[(left+right)/2];
    	while(left<=right){
    		while(arr[left]<pivot) left++;
    		while(arr[right]>pivot) right--;
    		if(left<=right){
    			swap(arr,left,right);
    			left++;
    			right--;
    		}
    	}
    	return left;
       } 
    
     static void swap(int[] arr,int left,int right){
    	int temp = arr[left];
    	arr[left] =arr[right];
    	arr[right] = temp;
    }

}<file_sep>/src/com/cn/leecode/ImplementstrStr.java
package com.cn.leecode;

/* 
 * Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
 */
public class ImplementstrStr {
    public String strStr(String haystack, String needle) {
        if(needle.length() == 0 || haystack.equals(needle))
            return haystack;
        int i = 0, j = 0;
        for(; i <= haystack.length() - needle.length() && j < needle.length(); i++) {
            if(haystack.charAt(i) == needle.charAt(0)) {
                for(; j < needle.length(); j++) {
                    if(haystack.charAt(i + j) != needle.charAt(j)) {
                        j = 0;
                        break;
                    }
                }
            }
        }
        return j == needle.length() ? haystack.substring(i - 1) : null;
    }
}
