Thứ Sáu, 9 tháng 9, 2005

Bài viết hay về Collections

Lập trình Java, bạn thường xuyên phải làm việc với Vector, List, LinkList,... Bạn luôn phải đau đầu với các kỹ thuật sắp xếp, tìm kiếm, dịch chuyển phần tử . Hãy tham khảo một bài viết rất hay từ www.math.ucla.edu. Bạn sẽ rành hơn về kỹ thuật này, chương trình của bạn sẽ nhanh hơn, mã sẽ sáng sủa hơn nhé.

3 nhận xét:

  1. Sorting
    Sort the followling list of integers {51, 12, 13, 18, 34, 29, 53, 91, 16, 24, 22, 33, 44, 35, 53, 80, 89} in ascending order.
    import java.util.*;

    public class Sort {
    public static void main(String[] args) {
    int[] array = {51, 12, 13, 18, 34, 29, 53, 91,
    16, 24, 22, 33, 44, 35, 53, 80, 89};
    List list = new ArrayList();
    for(int i = 0; i < array.length; i++) {
    list.add(new Integer(array[i]));
    }

    Collections.sort(list);
    System.out.println(list);
    }
    }

    Output
    [12, 13, 16, 18, 22, 24, 29, 33, 34, 35, 44, 51, 53, 53, 80, 89, 91]

    Descending order
    Sort the list of numbers given above in descending order.
    Method 1

    import java.util.*;

    public class Sort {
    public static void main(String[] args) {
    int[] array = {51, 12, 13, 18, 34, 29, 53, 91,
    16, 24, 22, 33, 44, 35, 53, 80, 89};
    List list = new ArrayList();
    for(int i = 0; i < array.length; i++) {
    list.add(new Integer(array[i]));
    }

    Collections.sort(list);
    Collections.reverse(list);
    System.out.println(list);
    }
    }

    Method 2
    import java.util.*;

    public class Sort {
    public static void main(String[] args) {
    int[] array = {51, 12, 13, 18, 34, 29, 53, 91,
    16, 24, 22, 33, 44, 35, 53, 80, 89};
    List list = new ArrayList();
    for(int i = 0; i < array.length; i++) {
    list.add(new Integer(array[i]));
    }

    Collections.sort(list, Collections.reverseOrder());
    System.out.println(list);
    }
    }

    Sorting by Comparator Interface
    Sort the integers by the sum of the digits. If the sum of the digits are the same, sort them by natural order. Example, the list is {{151, 112, 121, 13, 234, 207, 456, 654, 243};. Then the output is
    [13, 112, 121, 151, 207, 234, 243, 456, 654]

    SortDigit.java
    import java.util.*;

    public class SortDigit {
    public static void main(String[] args) {
    int[] array = {151, 112, 121, 13, 234, 207, 456, 654, 243};
    List list = new ArrayList();
    for(int i = 0; i < array.length; i++) {
    list.add(new Integer(array[i]));
    }

    Collections.sort(list, new DigitComparator());

    System.out.println(list);
    }
    }

    class DigitComparator implements Comparator {
    public int compare(Object o1, Object o2) {
    int x1 = ((Integer)o1).intValue();
    int x2 = ((Integer)o2).intValue();

    int sum1 = sumOfDigit(x1);
    int sum2 = sumOfDigit(x2);

    if(sum1 < sum2) {
    return -1;
    } else if(sum1 > sum2) {
    return 1;
    } else { // sum of digits are equal
    if(x1 < x2) {
    return -1;
    } else if(x1 > x2) {
    return 1;
    } else {
    return 0;
    }
    }
    }

    // sum of digits of number x
    public static int sumOfDigit(int x) {
    if(x < 0) {
    x = -x;
    }

    if(x < 10) {
    return x;
    } else {
    return sumOfDigit(x/10) + x%10;
    }

    }
    }

    Shuffling
    Randomize a list.
    import java.util.*;

    public class Shuffle {
    public static void main(String[] args) {
    List list = new ArrayList();
    for(int i = 1; i <= 10; i++) {
    list.add(new Integer(i));
    }

    System.out.println("Before shuffling: ");
    System.out.println(list);
    Collections.shuffle(list);
    System.out.println("After shuffling:");
    System.out.println(list);
    }
    }

    Output
    Before shuffling:
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    After shuffling:
    [2, 9, 3, 6, 10, 5, 8, 4, 7, 1]

    Data Manipulation
    static void copy(List dest, List src): Copies all of the elements from one list into another.
    static void fill(List list, Object obj) : Replaces all of the elements of the specified list with the specified element.
    static List nCopies(int n, Object o): Returns an immutable list consisting of n copies of the specified object.
    static boolean replaceAll(List list, Object oldVal, Object newVal): Replaces all occurrences of one specified value in a list with another.
    static void reverse(List list) : Reverses the order of the elements in the specified list.
    static void reverse(List list) : Reverses the order of the elements in the specified list.
    static void rotate(List list, int distance) Rotates the elements in the specified list by the specified distance.
    static Set singleton(Object o): Returns an immutable set containing only the specified object.
    static List singletonList(Object o) : Returns an immutable list containing only the specified object.
    static Map singletonMap(Object key, Object value): Returns an immutable map, mapping only the specified key to the specified value.
    static void swap(List list, int i, int j) : Swaps the elements at the specified positions in the specified list.
    Searching
    public static int binarySearch(List list, Object key)
    public static int binarySearch(List list, Object key, Comparator c)
    Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the specified comparator (as by the Sort(List, Comparator) method, above), prior to making this call.
    They returns the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
    Search.java

    import java.util.*;

    public class Search {
    public static void main(String[] args) {
    int[] array = {16, 24, 22, 33, 44, 35, 53, 80, 89};
    List list = new ArrayList();
    for(int i = 0; i < array.length; i++) {
    list.add(new Integer(array[i]));
    }
    Collections.sort(list);
    System.out.println(list);
    int indexOf35 = Collections.binarySearch(list, new Integer(35));
    int indexOf34 = Collections.binarySearch(list, new Integer(34));
    System.out.println(indexOf35);
    System.out.println(indexOf34);
    }
    }

    Output
    [16, 22, 24, 33, 35, 44, 53, 80, 89]
    4
    -5

    Finding max/min
    static Object max(Collection coll)
    static Object max(Collection coll, Comparator comp)
    static Object min(Collection coll)
    static Object min(Collection coll, Comparator comp)
    Max.java
    import java.util.*;

    public class Max {
    public static void main(String[] args) {
    Collection c= new ArrayList();
    c.add(new Employee("Charles", 123456.7));
    c.add(new Employee("Amy", 33333.33));
    c.add(new Employee("Betty", 23453.21));
    c.add(new Employee("Denny", 512121.22));
    c.add(new Employee("Eve", 455322.2));

    Object obj = Collections.max(c,
    new Comparator() { // annoymous class
    public int compare(Object o1, Object o2) {
    double s1 = ((Employee)o1).salary;
    double s2 = ((Employee)o2).salary;
    if(s1 > s2) {
    return 1;
    } else if (s1 < s2) {
    return -1;
    } else {
    return 0;
    }
    }
    }); // end of annymous class
    System.out.println("The employee with highest salary is: ");
    System.out.println(obj);
    }
    }

    class Employee implements Comparable {
    String name;
    double salary;

    public Employee(String name, double salary) {
    this.name = name;
    this.salary = salary;
    }

    public String toString() {
    return "name: "+ name + "\t" + "salary: " + salary ;
    }

    public int compareTo(Object obj) {
    return name.compareTo(((Employee)obj).name);
    }
    }

    Output

    The employee with highest salary is:
    name: Denny salary: 512121.22

    Trả lờiXóa
  2. Nhận xét này đã bị tác giả xóa.

    Trả lờiXóa

nhudinhthuan@gmail.com