CS2040 Sit-in Lab 2 review

 

CS2040 Sit-in Lab 2

Sorting

Sorting a list

Primitive types

List<Integer> listOfInts = new ArrayList<>();
listOfInts.addAll(Arrays.asList(new Integer[] {3,2,1}));
Collections.sort(listOfInts);
// Custom class
class Point {
	int x,y;
}
List<Point> pts = new ArrayList<>();
Collections.sort(pts, (a,b)->a.x-b.x);
// or using a comparator
class PointComparator implements Comparator<Point> {
	public int compare(Point p1, Point p2) {
		return p1.x-p2.x;
	}
	public boolean equals(Object obj) {
		return this==obj;
	}
}
Collections.sort(pts, new PointComparator());

Sorting an array

int[] l = {3,5,1,2,6};
Arrays.sort(l);
Point[] pts = {...};
Arrays.sort(pts, new PointComparator());

// Sorting multiple keys (advanced)

import java.util.*;
class PQ {
    public static void main(String[] args) {
        List<MyClass> list = new ArrayList<>();
        list.add(new MyClass(2,1,1));
        list.add(new MyClass(1,2,3));
        list.add(new MyClass(1,3,2));
        list.sort(Comparator.comparing(MyClass::getx)
                            .thenComparing(MyClass::gety)
                            .thenComparing(MyClass::getz));
        for(MyClass i: list)
            System.out.println(i);
    }
    static class MyClass {
        int x,y,z;
        public MyClass(int a,int b,int c) {
            x=a; y=b; z=c;
        }
        public int getx() { return x; }
        public int gety() { return y; }
        public int getz() { return z; }
        @Override
        public String toString() {
            return String.format("(%d %d %d)",x,y,z);
        }
    }
}

Merge sort for reversed pairs

import java.util.*;

class PSI {
    static int count=0;

    static void merge(int[] arr, int left, int mid, int right) {
        int[] C = new int[right-left+1];
        int a=left, b=mid, c=0;
        while(a<mid && b<=right) {
            if(arr[a] < arr[b]) { C[c++] = arr[a++]; } 
            else {
                count += mid-a;
                C[c++] = arr[b++];
            }
        }
        if(a==mid) {
            while(b<=right) { C[c++] = arr[b++]; }
        } else {
            while(a<mid) { C[c++] = arr[a++]; }
        }
        for(int i=0;i<C.length;i++) {
            arr[left+i] = C[i];
        }
    }

    static void mergesort(int[] arr, int left, int right) {
        if(left>=right) return;
        mergesort(arr, left, (left+right)/2);
        mergesort(arr, (left+right)/2 + 1, right);
        merge(arr, left, (left+right)/2+1, right);
    }

    static void run() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] sum = new int[n+1];
        sum[0] = 0;
        int neg = 0;
        for(int i=0;i<n;i++) {
            int cur = sc.nextInt();
            if(cur<=0) neg++;
            if(i==0) sum[i+1] = cur;
            else { sum[i+1] = sum[i] + cur; }
        }
        mergesort(sum,0,sum.length-1);
        System.out.println(n*(n+1)/2-count);
    }

    public static void main(String[] args) {
        run();
    }
}

PriorityQueue

PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<MyClass> pq2 = new PriorityQueue<>(new MyClassComparator());
// methods:
MyClass ex = new MyClass();
pq2.add(ex); pq2.remove(ex); // removes one if there exists at least one, 
// then return true; otherwise return false
pq.add(1); pq.add(2); pq.peek(); pq.poll();
pq.size();
pq2.toArray(new MyClass[0]); // simply use toArray would result in an array of Object

BBST (TreeMap/TreeSet)

Search, findMax, findMin, ceilingKey, floorKey: O(log n)

Hashing (HashMap/HashSet)

int[] a = {x,y,z};
return Arrays.hashCode(a);

Recursion

Permutation and substrings

import java.util.*;

public class Generate {
  private List<String> perm(String s) {
    List<String> res = new ArrayList<>();
    if (s.length() <= 1) {
      res.add(s);
    } else {
      List<String> temp = null;
      for (int i = 0; i < s.length(); i++) {
        temp = perm(s.substring(0, i) + s.substring(i + 1, s.length()));
        for (int j = 0; j < temp.size(); j++) {
          temp.set(j, s.substring(i, i + 1) + temp.get(j));
        }
        res.addAll(temp);
      }
    }
    return res;
  }

  private List<String> subseq(String s) {
    List<String> res = new ArrayList<>();
    if (s.length() <= 0) {
      res.add("");
    } else {
      List<String> temp = subseq(s.substring(1, s.length()));
      res.addAll(temp);
      for (String ss : temp) {
        res.add(s.substring(0, 1) + ss);
      }
    }
    return res;
  }
}

Choose k chars from String of n

static List<String> f(int k, String src) {
  List<String> res = new ArrayList<>();
  System.out.printf("%d %s\n", k, src);
  if (k == 0) {
    res.add("");
    return res;
  } else if (src.length() == k) {
    res.add(src);
    return res;
  } else {
    List<String> temp;
    String cur = src.substring(0, 1);
    temp = f(k - 1, src.substring(1, src.length()));
    for (String i : temp)
      res.add(cur + i);
    res.addAll(f(k, src.substring(1, src.length())));
    return res;
  }
}

Subset

static List<List<String>> subsets(List<String> set) {
  List<List<String>> res = new ArrayList<>();
  if (set.size() == 0) {
    res.add(new ArrayList<String>());
    return res;
  }
  List<String> withoutThis = new ArrayList<>();
  for (int i = 1; i < set.size(); i++) {
    withoutThis.add(set.get(i));
  }
  List<List<String>> subsetsWithoutThis = subsets(withoutThis);
  for (List<String> i : subsetsWithoutThis) {
    List<String> cur = new ArrayList<>();
    for (String j : i) {
      cur.add(j);
    }
    cur.add(set.get(0));
    res.add(cur);
  }
  res.addAll(subsetsWithoutThis);
  return res;
}

Subset (with restriction)

pos代表当前考虑的物品编号, len表示物品列表的长度, space表示空间限制

static int f(int pos, int len, int[] items, int space) {
  if(pos>=len || space<=0) return 1;
  if(items[pos]<=space) {
    return f(pos+1,len,items,space-items[pos])
         + f(pos+1,len,items,space);
  }
  return f(pos+1,len,items,space);
}

BackPack problem

public static ArrayList<Item> select(ArrayList<Item> remaining, ArrayList<Item> selected, int remainingSpace) {
  if (remainingSpace <= 0)
    return selected;
  ArrayList<Item> res = selected;
  int maxvalue = totalValue(res);

  for (Item i : remaining) {
    if (i.size <= remainingSpace) {
      ArrayList<Item> temp = new ArrayList<>();
      for (Item j : remaining) {
        if (j != i)
          temp.add(j);
      }
      ArrayList<Item> newSel = Packing.copy(selected);
      newSel.add(i);
      ArrayList<Item> temp2 = select(temp, newSel, remainingSpace - i.size);
      int t = totalValue(temp2);
      if (t > maxvalue) {
        maxvalue = t;
        res = temp2;
      }
    }
  }
  return res;
}