Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Largest Rectangle in Histogram 升级版。对于矩阵每行，可以看成是这个问题。height array对于相邻的行，假如当前的matrix[i][j] = 0，则无视上一行且当前height[j] = 0，如果matrix[i][j] = 1，则加上之前的height[j] += 1。

public class Solution {
    //Time: O(m*n)  Space: O(n)
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int max = 0;
        int[] height = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            int cur = largestRectangleArea(height);
            max = Math.max(max, cur);
        }
        return max;
    }
    
    public int largestRectangleArea(int[] height) {
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= height.length; i++) {
            int h = i == height.length ? -1 : height[i];
            while (!stack.isEmpty() && h < height[stack.peek()]) {
                int index = stack.pop();
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, w * height[index]);
            }
            stack.push(i);
        }
        return max;
    }
}

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

我们需要维护一个递增的stack。

举例现在在stack里是1，3，5，7。现在来了4，说明以7为高度生成矩阵已经不可能在增长了。把7pop出来，算出以7为高的矩阵和全局比较。在继续这么比较。在数组最后push -1进去，使stack里剩余的高度都能被计算。实际在stack里是高度对应的Index，不是高度本身。宽度：当stack已经为空了则为当前要push的i，否则为i - stack.peek() - 1。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int max = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i <= height.length; i++) {
            int h = i != height.length ? height[i] : -1;
            while (!stack.isEmpty() && height[stack.peek()] > h) {
                int index = stack.pop();
                int w = stack.isEmpty() ? i : (i - stack.peek() - 1);
                max = Math.max(max, height[index] * w);
            }
            stack.push(i);
        }
        return max;
    }
}

Java知识点总结(二)：常用API及复杂度分析

这些常用API只是本人在刷算法题中经常碰到的API，并不是指Java编程中最常用的。

Arrays

对于一个普通的array我们需要知道：insert, delete: O(n), find with index O(1).

同时要熟练各种sort algorithm。 Merge sort: Time O(nlogn)  Space: O(n)   Quick sort:  Time: average O(nlogn)  worst  O(n^2)  Space: O(1)

Arrays.fill(array, number)  O(n)

Arrays.equals(array, array)  O(n)

Arrays.sort(array);  O(nlogn)

Arrays.sort(array, comparator)  O(nlogn)

ArrayList：size动态变化

add(object)  O(1)  当需要resize时，为O(n)

addAll(object)  O(n)

contains(object)  O(n)

get(index)  O(1)

remove(index)  O(n)

remove(object)  O(n)

set(index, object)  O(1)

size()  O(n)

LinkedList

对于大部分链表的算法题，通常默认是单链表：只有val和next。

insert, delete: 只对于这步来说是O(1)，但是如果考虑找到此点的消耗则为O(n)
同时要掌握找中点，删除某个节点，找第N个点，熟练快慢指针和dummy node的用法。
Java 库中实现是双链表，常用的method和arraylist中的大部分相同，但是多了链表特有的getFirst, getLast, addFirst(), addLast().  其他一些poll(),offer()在其他数据结构中会提到。

Queue

先进先出的特性。是一个abstract class，需要用PriorityQueue或者LinkedList实现。
通常queue用在BFS。
offer(object)  O(1)
poll()  O(1)
peek()  O(1)

Stack

先进后出的特性。

pop()  O(1)

push(object)  O(1)

peek()  O(1)

StringBuilder

StringBuilder和string + string的区别是，前者只会生成1个StringBuilder object，后者每次+都生成了一个新的string object。

append(object)  O(1)

insert(index, object)  O(n)

length() 

reverse()  O(n)

String

charAt(index)  O(1)

length()

split(String)   return a String array

trim()  O(n)

static:  valueOf(object) 

toCharArray()  O(n)

HashMap

get(key)  O(1)

put(key, value)  O(1)

keySet()  return a set contains all keys

values()  return a collections contains all the value

HashSet

add(object) 

contains(object)  

PriorityQueue

constructor: new PriorityQueue(size, comparator), 这个size只是初始值，超出后会自动resize。没有comparator那默认是min-heap。
heap除了方便得到最大最小，在得到第k大(小)，或者k-way merge都可以用一个k-szie heap完成。

建立一个heap复杂度是O(n)，得到最大或最小是O(1)，但是之后重新维护这个heap是O(logn)

offer(object)

poll()

peek()

Character

isDigit(char)

isLetter(char)

Java知识点总结(一)：OOD

Class and Object

A class is an abstract definition of something that has attributes (sometimes called properties or states) and actions (capabilities or methods).

An object is a specific instance of a class that has its own state separate from any other object instance. 

Inheritance and Polymorphism

Inheritance allows a class to be defined as a modified or more specialized version of another class.

Polymorphism is the capability to provide multiple implementations of an action and to select the correct implementation based on the surrounding context.

Overloading: a class might define two versions of a method with different parameters.

Overriding: the same method might be defined both in a parent class and a subclass.

Construction and Destruction

The constructor initializes the state of the object.

Constructor has same name with class, with no return type, invoke use new operator.

Private constructor: no one outside the class can directly instantiate the class. The class can't be inherited. 

Java GC is responsible for finding and destroying unused objects, An optional finalizer method is invoked by the system prior to the object’s destruction to give it the opportunity to clean itself up before its “final” destruction.

Interfaces and Abstract Classes

An interface declares a set of related methods, the fields in interface are static and final by default.
Java is a single inheritance language. Interface makes the language more flexible and achieve multi-inheritance.

An abstract class is an incomplete class definition that declares but not define all the methods(actually a class with abstract keyword is a abstract class, we can also define a class abstract, even if the definition  of methods in this class is complete).

Before the subclass complete the implementation of all the class, we can't create objects with this abstract class.

Why need abstract?

Some classes extends from a abstract class share properties may be different on several methods. Why we don't give this method a default implementation in the abstract class. The reason is that if we forget the give a implementation in the subclass, we can find the error on compile time. Without the abstract, we need to find the error on the run time. 

We can use an interface to create a object?

In fact, during the compiling, there is a virtual class implements this interface.

public Comparator<Integer> ListCom = new Comparator<Integer>() {
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
};

Virtual Methods

In OOP, child classes can override (redefine) methods defined by ancestor classes. If the method is virtual, the method definition to invoke is determined at run time based on the actual type (class) of the object on which it is invoked. Non-static Java methods are always virtual.

Virtual methods aren’t free. It (almost always) takes longer to invoke a virtual method because the address of the appropriate method definition must be looked up in a table before it is invoked. This table also requires a small amount of extra memory.

Example of OOD

abstract class A {
    public void print() {
        System.out.println("I am class A");
    }
 
    public void print2() {
        System.out.println("I am another method in A");
    }
}

class B extends A {
    public void print() {
        System.out.println("I am class B");
    }
}

class C extends B {
    public void print() {
        System.out.println("I am class C");
    }
 
    public void print(int a) {
        System.out.println("I am another method in C");
    }
}

public class Example {
    public static void main(String[] args) {
        //A a = new A(); error
        A ab = new B();
        A ac = new C();
        B bb = new B();
        B bc = new C();
        C cc = new C();
        //C cb = new B(); error
        System.out.println("ab");
        ab.print();
        ab.print2();
        System.out.println("ac");
        ac.print();
        System.out.println("bb");
        bb.print();
        System.out.println("bc");
        bc.print();
        System.out.println("cc");
        cc.print();
        cc.print(1);
    }
}

ab
I am class B
I am another method in A
ac
I am class C
bb
I am class B
bc
I am class C
cc
I am class C
I am another method in C

Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

KMP和RK会在以后补上。暴力方法：

public class Solution {
    //Time: O(m*n)  Space: O(1)
    public String strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return null;
        }
        if (needle.length() == 0) {
            return haystack;
        }
        
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            int length = 0;
            for (int j = i; j < needle.length() + i; j++) {
                if (haystack.charAt(j) == needle.charAt(j - i)) {
                    length++;
                } else {
                    break;
                }
                if (length == needle.length()) {
                    return haystack.substring(i);
                }
            }
        }
        return null;
    }
}

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        Queue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), ListCom);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                queue.offer(lists.get(i));   
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            head.next = cur;
            if (cur.next != null) {
                queue.offer(cur.next);
            }
            head = head.next;
        }
        return dummy.next;
    }
    
    private Comparator<ListNode> ListCom = new Comparator<ListNode>() {
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }  
    };
}

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

用左右两个指针，右指针往右移同时把char加进hashset里面，当hashset出现重复时，计算当前长度，移动左指针，一直到左指针指向重复的元素，把经过的元素移除hashset。重复以上过程。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) {
            return s.length();
        }
        
        HashSet<Character> set = new HashSet<Character>();
        int left = 0;
        int i = 0;
        int max = 0;
        for (; i < s.length(); i++) {
            if (!set.contains(s.charAt(i))) {
                set.add(s.charAt(i));
            } else {
                max = Math.max(max, i - left);
                while (left < i && s.charAt(left) != s.charAt(i)) {
                    set.remove(s.charAt(left));
                    left++;
                }
                left++;
            }
        }
        max = Math.max(max, i - left);
        return max;
    }
}