算法小结--解题常用Utility code

0.常用代码整理 https://docs.google.com/document/d/1LWDEUkNAG7zlk8IQ_yBlIrly0evdP2wsCaVGTcnmn5c/edit?ts=58753f2a
Arrays.asList(arr)；//arr is array
Queue.addAll(Arrays.asList(arr)) 

1. Min Heap
PriorityQueue<Integer> minheap = new PriorityQueue<Integer>(); --default min heap
PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>(10(initial capacity), Collections.reverseOrder()); 
Heap - poll(), peek(), offer()

 // Use a min heap to track the minimum end time of merged intervals
    PriorityQueue<Interval> heap = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
        public int compare(Interval a, Interval b) { return a.end - b.end; }
    });

Similar syntax

Arrays.sort(intervals, (a,b)->(a.start - b.start));

2. Comparator

 @Override instruct instruct you want to override a method in superclass
compare(a, b) utility func to sort
a.compareTo(b) return int 
应用1： sort func
应用2： priority Queue

class RecipeCompare implements Comparator<Recipe> {

    @Override
    public int compare(Recipe o1, Recipe o2) {
        // write comparison logic here like below , it's just a sample
        return o1.getID().compareTo(o2.getID());
    }
}

LeetCode实例
»  56. Merger Intervals -- Collections.sort for 'List<Interval>' 各大家
http://rainykat.blogspot.com/2017/02/leetcode-56-merge-intervalcomparator.html

Collections.sort(intervals, new Comparator<Interval>() {//Collections(obj: List<Interval> intervals)
            @Override//can have or not
            public int compare(Interval i1, Interval i2) {
                return Integer.compare(i1.start, i2.start);//same as return i1.start - i2.start
            }
        });

» 252. Meeting Rooms -- Arrays.sort for 'Interval[]' F家
http://rainykat.blogspot.com/2016/12/facebook-can-single-person-attend-all.html

Arrays.sort(intervals,new Comparator<Interval>(){//Arrays(obj: Interval[])
           //@Override
           public int compare(Interval o1, Interval o2) {
               return o1.start-o2.start;//小的在前面，即min
            }
        });

Reference:
sort(T[] a, Comparator<? super T> c)

 » 451.Sort Characters By Frequency G家，亚麻
http://rainykat.blogspot.com.tr/2017/01/leetcodeg-451-sort-characters-by.html

PriorityQueue<Character> heap = new PriorityQueue<Character>(new Comparator<Character>(){
            @Override
            public int compare(Character c1, Character c2) {
                return map.get(c2) - map.get(c1);//大的val在前面，即max
            }
        });

Reference:
PriorityQueue(Comparator<? super E> comparator)//capacity not mandatory
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

3. Split string by space
String[] splited = str.split(" "); -- -- split into string[] where each element is each word
str = "/a/s/v//b/c"
String[] splited = str.split("/") --''//'will result in "" -- empty string cell. watch!  

4. length
arr.length
str.length()
arrlist.size() 

5.Scanner
For String: next(), For Int: nextInt() .Check if empty: hasNext() 
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] array1= new int[n];    
for(int i=0;i<n;i++) array1[i]=sc.nextInt();
 
6.Throw Exception
ex: if(arr.get(index)==null)//error!! use error catch to avoid或者用arr.size()来判断

try {
    list.get( index );
} catch ( IndexOutOfBoundsException e ) {
    list.add( index, new Object() );
}

7. String, Int, Char conversion
    string a = b.substring(0,3);//[0,3)
    char to int: int a = charA-'0';
    int to char: char a = (char) b;
    int to string: Integer.toString(a);
    s = "123"; 
    Character to int: int foo = Character.getNumericValue(c); 
    Character to String: String s = Character.toString(c);
    String to Character:  s.getCharAt(i)
    String to Int: int foo = Integer.parseInt(s); // return int
    Integer.valueOf(s.substring(1, 3))//23 return Integer(same thing, just you can do keep do Integer.)
    String.valueOf(boolean,int)...
    Int to String: Integer.toString(a)

8. String, char array conversion
    char[] arr = str.toCharArray();
    Arrays.sort(arr);//sort array alphabetically
    String str = new String(arr); OR srt.valueOf(arr); //for char array only
    String str = Arrays.toString(arr);

9. Max/Min Integer
    Integer.MAX_VALUE (2^31-1)
    Integer.MIN_VALUE (2^-31)

10. String performance
String adding is expensive - use StringBuilder (eg: sb.setCharAt(index,c);)
substring is expensive - use char[] (str.toCharArray())

11.Character for palindrome)
Character.isDigit(c)
Character.isLetter(c)
Character.isLetterOrDigit(c) //--  check if notation (true: letter|| digit, false: notation)
Character.toUpperCase(s.charAt(i)); //convert to uppercase

12. Deque- double ended queue for Queue & Stack

Deque<String> deque = new LinkedList<String>();

 

• Queue.add - throws an exception if the operation fails,
• Queue.offer- returns a special value (either null or false, depending on the operation).
• Queue.remove - if q is empty, throw error
• Queue.poll - if q is empty, return null(perferred)