数据结构复习10.刷题常用点总结

Integer.bitCount(int i) 一. Array (1) array.length; //没有括号 (2) Reference类型注意检测null (3) Arrays.sort(a);//排序 (4) Arrays.toString(a)//print (5) copy: a = Arrays.copyOf(b, b.length); System.arrayCopy(a, 0, b, 0, b.length); (6) print: System.out.println(Arrays.toString(a)); (7) Arrays.fill()填充一段数组 Arrays.fill(E[] a, E b); Arrays.fill(E[] a, E b, int fromIndex, int toIndex) 二. 通用二分查找 public class BinarySearch { public static void main(String[] args) { int[] a = {1, 2, 3}; System.out.println(binarySearch(a, 2)); } static int binarySearch(int[] A, int target) { if (A.length == 0) { return -1; }

int start = 0;
    int end = A.length - 1; //注意-1
    int mid;
    while (start + 1 < end) { //注意是+1
        mid = start + (end - start) / 2;
        if (A[mid] == target) {
            end = mid; //如果不找第一个，可以直接返回。
        } else if (A[mid] < target){
            start = mid;
        } else {
            end = mid;
        }
    }

    //注意输出
    if (A[start] == target) {
        return start;
    }
    if (A[end] == target) {
        return end;
    }
    return -1;
}

}

三. ArrayList add(Object); add(index, Object); set(index, Object); get(index); remove(index); size(); 反转list， Collections.reverse(res);

四. LinkedList addFirst(Object); addLast(Object); getFirst(); getLast(); removeFirst(); removeLast(); add(index，Object); 反转list， Collections.reverse(res);

五. iterator List numbers = new LinkedList(); numbers.add(1); Iterator itr = numbers.iterator(); 迭代器使用期间，不能添加/删除元素。否则回报错 java.util.ConcurrentModificationException。

六. Stack push(); pop(); peek(); isEmpty();

七. Queue offer(); poll(); peek(); isEmpty();

八.compare 1. comparator Collections.sort(listA, new myComparator() { @override public int compare(Myclass obj1, Myclass obj2) { return 1; } }) 2. comparable public class Myclass implements Comparable{ @override public int compareTo(Myclass obj2) { return 1; } }

九. Hash 1.HashMap map.keySet();//得到键set map.entrySet();//得到value集合 map.values()//返回一个值的集合 map.containsKey(key); put(key, value) get(key) 2.HashSet add(key); contains(key); iterator()

十.Tree 1.TreeMap and TreeSet public static void main(String args[]) {

/* This is how to declare TreeMap */
  TreeMap<Integer, String> tmap = 
         new TreeMap<Integer, String>();

  /*Adding elements to TreeMap*/
  tmap.put(1, "Data1");
  tmap.put(23, "Data2");
  tmap.put(70, "Data3");
  tmap.put(4, "Data4");
  tmap.put(2, "Data5");

  /* Display content using Iterator*/
  Set set = tmap.entrySet();
  Iterator iterator = set.iterator();
  while(iterator.hasNext()) {
     Map.Entry mentry = (Map.Entry)iterator.next();
     System.out.print("key is: "+ mentry.getKey() + " & Value is: ");
     System.out.println(mentry.getValue());
  }

} or new TreeMap