算法小结--编程常识

➤ Unit of memory size
1byte = 8 bit
1MB = 1024byte = 2^10 bit
1KB = 1024 MB = 2^10*2^10 = 2^20
1GB = 1024 KB = 2^10*2^10 = 2^30
4GB = 2^30*2^2 = 2^32
1TB = 2^40

➤ Unary & Binary operator
Unary: 没几个, &(地址)，*(pointer ref), !,~(complement) ,+(positive),-(negation),++,--
Binary: logical,math operators: &(bitwise and),&&(logical and), +(add), - (minus)...

➤ Array
contiguous memory allocated for array so no growth

➤  HashTable - array with hash function
function take key to hash value for mapping index in hashtable
and store key
 *make use all info provided by key
 *uniformly distribute output across table
 *map similar keys to very different hash values

deal with collections(avoid by good hash function)
-linear probing
 assign to next available slot
 * increase loop up time to O(N)
 * increase chance of collision - clustering
-sepearate chaining
 array points to linked list
 * search O(n/k) - k lists n keys, distribute evenly

➤ Graph
BFS:Time O(V+E), Space O(V) - tree or known, O(V+E) - adjacency list, O(V^2) - adjacency matrix
DFS:  Time O(V+E), Space O(V) - worst case all vertices in path to store in the stack

Applications：
1.social network (union find)
2.city road
3.precedence constraint(topological sort)

Adjacency Matrix: v*v
--diagnal 0 means no itself loop
--symetric only in undriected graph
Pros:
*easy implement
*remove is O(1)
*O(1) to check for specific edge

Cons:
!O(v^2)more space
!adding vertex cause O(v^2), rewrite all list.

Adjacency list --java ArrayList<List<Integer>> eg: [0][1,2,3]
-- use linkedlist
Pros
*O(v+E)spaces, worst case O(v^2)
*Adding vertex is easirer

Cons
!Query of specified edge takes O(v)

➤Other

"The idea behind bidirectional search is to run two simultaneous searches—one forward from
the initial state and the other backward from the goal—hoping that the two searches meet in
the middle. The motivation is that b^(d/2) + b^(d/2) is much less than b^d. b is branch factor, d is depth. "

----- section 3.4.6 in Artificial Intelligence - A modern approach by Stuart Russel and Peter Norvig

算法小结--解题常用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)