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)