2016-05-25.md

26、 Remove Duplicates from Sorted Array(删除数组中的重复元素) public class Solution {

public int removeDuplicates(int[] nums) {
    if(nums.length==0)return 0;
    int pos=0;
    for(int i=0;i<nums.length-1;){
        int t = i+1;
        nums[pos++]=nums[i];
        while(t<nums.length&&nums[i]==nums[t]){
            t++;
        }
        i=t;
    }
    if(pos==0){
        nums[pos++]=nums[nums.length-1];
    }
    else if(pos>0&&nums[pos-1]!=nums[nums.length-1]){
        nums[pos++]=nums[nums.length-1];
    }
    return pos;
}

}

102、 Binary Tree Level Order Traversal(层次遍历二叉树，根节点在上的) /**

• Definition for a binary tree node.

• public class TreeNode {

• int val;
  

• TreeNode left;
  

• TreeNode right;
  

• TreeNode(int x) { val = x; }
  

• } */
  public class Solution {

  public class Node { TreeNode treenode; int deep;

   public Node(TreeNode node,int deep){
       this.treenode=node;
       this.deep=deep;
   }
  

  }

  public int travel(TreeNode root,int deep,List list){ if(root==null)return deep;

   Node tmp = new Node(root,deep+1);
   list.add(tmp);
  
   int l = travel(root.left,deep+1,list);
   int r = travel(root.right,deep+1,list);
   return l>r?l:r;
  

  } public List<List> levelOrder(TreeNode root) { List list = new ArrayList();

   int deep = travel(root,0,list);
  
   List<List<Integer>> result = new ArrayList<List<Integer>>();
   for(int d = 1;d<=deep;d++){
       List<Integer> ttt = new ArrayList<Integer>();
       for(int i=0;i<list.size();i++){
           if(d==list.get(i).deep){
               ttt.add(list.get(i).treenode.val);
           }
       }
       result.add(ttt);
   }
   return result;
  

  }

}

88、 Merge Sorted Array(在当前数组中归并排序，不利用额外的内存空间) 思路：nums1后面的有空位，先从后面开始遍历归并填充

public class Solution {

//nums1的后面是空的，应该从后往前填充！！！！
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p=m+n;
    int p1=m-1;
    int p2=n-1;
    while(--p>=0){
        //nums1中的大就放到最后
        if((p1>=0 && p2>=0) && nums1[p1] > nums2[p2])
            nums1[p] =nums1[p1--];
        else if(p2>=0)//nums2中的大就放到最后
            nums1[p] =nums2[p2--];
        //一旦nums1中的元素用完了，就只执行第二个条件把nums2剩余的填充到后面
        //一旦nums2用完了，nums1剩下的本来就有序，不用管了。。。
    }
}

}