java刷算法题常用方法整理

数据类型、接口和类

• 接口：抽象方法的集合，但没有特定方法的实现

• 类：通过继承接口从而继承接口的抽象方法并针对不同的方法有自己的实现

常用类列表

该部分仅列出了在算法题中经常用到的类型与数据结构。

数字 & 数学 - Number & Math

Collection接口
Collection的定义如下：
public interface Collection<E> extends Iterable<E> {}
基础API接口：


abstract boolean         add(E object)
abstract boolean         addAll(Collection<? extends E> collection)
abstract void            clear()
abstract boolean         contains(Object object)
abstract boolean         isEmpty()
abstract boolean         remove(Object object)
abstract boolean         removeAll(Collection<?> collection)
abstract int             size()
abstract <T> T[]         toArray(T[] array)
abstract Object[]        toArray()

静态数组 array

属性  length

.length
 记得是属性而不是方法 arr.length
 没有()

工具类Arrays

             返回由指定数组支持的固定大小的列表返回由指定数组支持的固定大小的列表

                      sort(T[] a)

               将指定的数组按升序排序

                     String  toString(T[] a)

                    返回指定数组内容的字符串表示形式

动态数组 List & ArrayList

初始化

常规 - ArrayList更常用

     List<Integer> array = new ArrayList<>();    // 数组

     List<Integer> list = new LinkedList<>();    // 链表
ArrayList 构造器


   ArrayList()

链表 LinkedList

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有LinkedList适合频繁地对列表进行增加或删除元素操作，因此LinkedList类可用于实现堆栈和队列

public void addFirst(Object o) //在链表头增添元素
public void addLast(Object o) //在链表尾增添元素


public E getFirst() //获取链表首元素
public E getLast() //获取链表尾元素


public Object removeFirst() //删除链表头元素，并返回该元素
public Object removeLast() //删除链表尾元素，并返回该元素

 Vector（Stack）

Stack 是Vector的子类， java中Stack只有一个无参构造函数。

属于Stack的方法

push( num)   //入栈
pop()   //栈顶元素出栈 返回
empty()   //判定栈是否为空     注意这里和Collection的区别
peek()   //获取栈顶元素
search(num)  //栈顶到该元素首次出现的位置的距离

 Queue:

Queue 和List 属于同一级，都继承了Collection

//add()和remove()，element()方法在失败的时候会抛出异常(不推荐) 
Queue<String> queue = new LinkedList<String>();


offer(object)
poll() // 出队并返回
peek() 
isEmpty()//队列为空返回true，否则返回false
size()// 返回队列长度

 Deque 用LinkedList 代替使用

注意点（易错点）

java中的向下转型

List和Deque同级

List中无addLast，addFist方法

这样 List<Integer> list=new LinkedList<>();在不向下转型的情况下，是无法使用实现List接口的LinkedList中的独有方法（即addLast，addFirst）

无法使用LinkedList的addLast，addFist,除非向下转型

但是deque可以，因为Deque接口有此方法

ArrayDeque (栈和队列新生儿)

（及其好用！！！！！！！！！！）

类ArrayDeque <E>

• java.lang.Object

• 
  

• java.util.ArrayDeque <E>

• java.util.AbstractCollection <E>

• 
  

• 
  

• 所有已实现的接口：

• Serializable
  ，Cloneable
  ，Iterable<E>
  ，Collection<E>
  ，Deque<E>
  ，Queue<E>
  

• 类型参数：

• E
   -此双端队列中包含的元素类型

ArrayDeque不是线程安全的。 
ArrayDeque不可以存取null元素，因为系统根据某个位置是否为null来判断元素的存在。 
当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好

1.队列操作
        add(E e) 在队列尾部添加一个元素
        offer(E e) 在队列尾部添加一个元素，并返回是否成功
        remove() 删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的是removeFirst())
        poll()  删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())
        element() 获取第一个元素，如果没有将抛出异常
        peek() 获取第一个元素，如果返回null




2.栈操作
        push(E e) 栈顶添加一个元素
        pop(E e) 移除栈顶元素,如果栈顶没有元素将抛出异常




3.其他
        size() 获取队列中元素个数
        isEmpty() 判断队列是否为空
        iterator() 迭代器，从前向后迭代
        toArray() 转成数组
        clear() 清空队列
        clone() 克隆(复制)一个新的队列

重要方法

boolean add(E e) 在此双端队列的末尾插入指定的元素。
void addFirst(E e) 将指定的元素插入此双端队列的前面。
void addLast(E e)  在此双端队列的末尾插入指定的元素。
E getFirst() 检索但不删除此双端队列的第一个元素
E getLast()  检索但不删除此双端队列的最后一个元素
boolean isEmpty()  true如果此双端队列不包含任何元素，则返回
E remove() 检索并删除此双端队列代表的队列的头部
E removeFirst() 检索并删除此双端队列的第一个元素
E removeLast() 检索并删除此双端队列的最后一个元素
Obeject[] toArray() 以适当的顺序（从第一个元素到最后一个元素）返回一个包含此双端队列中所有元素的数组。
T[] toArray(T[] a)  返回一个数组，该数组包含此双端队列中的所有元素的顺序正确（从第一个元素到最后一个元素）；返回数组的运行时类型是指定数组的运行时类型。

PriorityQueue

是Queue接口的实现，可以对其中元素进行排序，
可以放基本数据类型的包装类（如：Integer，Long等）或自定义的类
对于基本数据类型的包装器类，优先队列中元素默认排列顺序是升序排列
但对于自己定义的类来说，需要自己定义比较器
常用方法 和上面Queue一样

小根堆

Queue<Integer> minH = new PriorityQueue<>();    // 小根堆，默认大小为11 相当于  new PriorityQueue<>(11)
Queue<Integer> minH = new PriorityQueue<>(100);  // 定义一个默认容量有100的小根堆。在当中增加元素会扩容，只是开始指定大小。不是size，是capacity

大根堆 

Queue<Integer> maxH = new PriorityQueue<>((i1, i2) -> i2 - i1);    // 大根堆，默认大小为11 相当于  new PriorityQueue<>(11, (i1, i2) -> i2 - i1)
Queue<Integer> maxH = new PriorityQueue<>(100, (i1, i2) -> i2 - i1);    // 定义一个默认容量有100的大根堆。在当中增加元素会扩容，只是开始指定大小

PriorityQueue方法(Queue接口方法)

offer

.offer(E e);  
// 在堆中加入元素e，并调整堆。若成功入堆返回值true，否则返回false
 ---
 O(logN)

poll

.poll();    // 弹出堆顶元素，并重新调整堆，返回出队元素e --- O(logN)

peek

.peek();    // 查看
堆顶元素， 返回值堆顶元素e --- O(1)

isEmpty

.isEmpty()    // 若队空返回true， 否则返回false --- O(1)

size

.size()    // 返回队中元素个数 --- O(1)

集合 Set - HashSet

性质：Set中没有重复元素，重复添加的元素抛弃

初始化

默认构造函数

Set<Integer> set = new HashSet<>();

把集合如Stack、Queue、List等Collection作为参数

// List<Integer> list = new ArrayList<>....;
   // Set<Integer> set = new HashSet<>(list);
HashSet方法(Set接口方法)

方法：add, remove, contains, isEmpty, size

add

.add(E e);   
// 在集合中添加元素E e， 若成功添加则返回true，若集合中有元素e则返回false --- O(1)

remove

.remove(E e);  
 // 在集合中删除元素e，若删除成功返回true；若集合中没有元素e，返回false --- O(1)

contains

.contains(E e);   
// 若存在元素e，则返回true，否则返回false --- O(1)

isEmpty

.isEmpty()    // 若集合为空返回true， 否则返回false --- O(1)

size

.size()    // 返回集合中中元素个数 --- O(1)

first (TreeSet)

.first()   
// 返回集合里的最小值（若给了比较器从大到小则是返回最大值）

last (TreeSet)

.last()    // 返回集合里的最大值（若给了比较器从大到小则是返回最小值
）

散列表 HashMap

初始化

<Key, Value> key和value是任何Collection或任何Object

Map<Characters, Integer> map = new HashMap<>();

HashMap方法 (Map接口方法)

put

.put(K key, V value); 
// 在Map中加入键值对<key, value>。返回value值。如果Map中有key，则replace
旧的value -
-- O(1)

get

.get(K key); 
 // 返回Map中key对应的value。若Map中没有该key，则返回null --- 
O(1)

getOrDefault

.getOrDefault(K key, V defaultValue); 
 // 返回Map中key对应的value。若Map中没有该key，则返回defaultValue --- O(1)


// For example:
// Map<Character, Integer> map = new HashMap<>();
// if (...)    // 如果发现k，则k在Map中的值加1。没一开始没有k，则从0开始加1。（相当于给了key在Map中的一个初试值）
    map.put('k', map.getOrDefault('k', 0) + 1);

containsKey

.containsKey(Key key);    
// 在Map中若存在key，则返回true，否则返回false --- O(1)

containsValue

.containsValue(V value);   
 // 在Map中若存在value，则返回true，否则返回false --- O(1)

keySet

.keySet();   
// 返回一个Set,这个Set中包含Map中所有的Key --- O(1)

// For example:
// We want to get all keys in Map
// Map<Character, Integer> map = new HashMap<>();
for (Character key : map.keySet()) {
    // Operate with each key
}

values

.values();   
 // 返回一个Collection<v>,里面全是对应的每一个value --- O(1)

// For example:
// We want to get all values in Map
// Map<Character, Integer> map = new HashMap<>();
for (Integer value : map.values()) {
    // Operate with each values
}

isEmpty

.isEmpty()    // 若Map为空返回true， 否则返回false --- O(1)

size

.size()    // 返回Map中中键值对<K, V>的个数 --- O(1)

字符串

String

初始化

字符串复制初始化

String s = "abc";

基于另外一个字符串

// s = "abc"
String s2 = new String(s);

基于char[]

// s = "abc";

// char[] c = s.toCharArray();
String s3 = new String(c);

// 可以偏移
// public String(char value[], int offset, int count)
String s4 = new String(c, 1, 2);    // [offset, offset + count)

// 把char[] 变成字符串
char[] ch = {'a', 'b', 'c'};
String.valueOf(ch);

类方法

String 方法

charAt

.charAt(int index);    // 返回index位置的char --- O(1)

length

.length();    // 返回字符串长度 --- O(1)

substring

.substring(int beginIndex, int endIndex);   
 // 返回字符片段[beginIndex, endIndex) --- O(n)

  .substring(int beginIndex);    
// 返回字符片段[beginIndex, end_of_String) 就是从beginIndex开始后面的
---- O(n)

indexOf 是（暴力查找字符串，不是KMP）

.indexOf(String str)    
// 返回str第一个出现的位置(int)，没找到则返回-1。
--- O(m * n) m为原串长度， n为str长度

// (假如要找一个字符char c，str可以表示成String.valueOf(c),然后作为参
数传进去.


   s.indexOf(String str, int fromIndex); 
 // 同上，但从fromIndex开始找 --- O(m * n)

lastIndexOf

.lastIndexOf(String str); 
// 返回str最后出现的位置(int)，没找到则返回-1。
--- O(m * n) m为原串长度， n为str长度
// (假如要找一个字符char c，str可以表示成String.valueOf(c),
然后作为参数传
进去.

.lastIndexOf(String str, int fromIndex);    // 同上，
    //但从fromIndex开始从后往前找 
[0 <- fromIndex] --- O(m * n)

replace 只能换char

.replace(char oldChar, char newChar);   
 // 返回一个新字符串String，其oldChar全部变成newChar --- O(n)

toCharArray

.toCharArray();   
 // 返回char[] 数组。把String编程字符数组 --- O(n)

trim 去除前后空格

.trim();    // 返回去除前后空格的新字符串 --- O(n)

split 以什么分开

.split(String regex);    // 返回 String[]，以regex(正则表达式)分隔好的字符换数组。---- O(n)

// For example
// 从非"/"算起 若"/a/c" -> 会变成"" "a" "c"
String[] date = str.split("/"); 
    // date[0]:1995 date[1]:12 date[2]:18 --- O(n)
复制代码

toLowerCase, toUpperCase 转换大小写

s = s.toLowerCase();    // 返回一个新的字符串全部转成小写 --- O(n)
    s = s.toUpperCase();    // 返回一个新的字符串全部转成大写 --- O(n)

技巧

初始化

StringBuilder sb = new StringBuilder();

instance方法

charaAt

.charAt(int index);    // 返回index位置的char --- O(1)

length

.length();    // 返回缓冲字符串长度 --- O(1)

setCharAt

.setCharAt(int index, char ch);   
 // 设置index位置的char为ch --- O(1)

insert

.insert(int offset, String str);    // 在offer位置的插入字符串str--- O(m + n)

deleteCharAt

.deleteCharAt(int index);   
 // 删除index位置的char --- O(n)

.deleteCharAt(sb.length() - 1);    
// 删除最后一个char --- O(1)

delete

.delete(int start, int end);    
// 删除[start, end)位置的char --- O(n)


reverse

.reverse();    // 反转缓存字符串 --- O(n)

toString

.toString();   
 // 返回一个与构建起或缓冲器内容相同的字符串 --- 
O(n)

！！！注意--StringBuffer 中没有实现equals方法，不能通过equals
比较两个字符串是否相等，而且StringBuffer是可变的，在传参时要小心，
尤其做回溯算法时，StringBuffer是引用类型变量

        与运算的用途：

        1）清零

如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。

        2）取一个数的指定位

比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。

        3）判断奇偶

只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

    异或运算符（^）

定义：参加运算的两个数据，按二进制位进行"异或"运算。

运算规则：

0^0=0  0^1=1  1^0=1  1^1=0

总结：参加运算的两个对象，如果两个相应位相同为0，相异为1。

异或的几条性质:

• 1、交换律

• 2、结合律 (a^b)^c == a^(b^c)

• 3、对于任何数x，都有 x^x=0，x^0=x

• 4、自反性: a^b^b=a^0=a;

异或运算的用途：

        1）翻转指定位

比如将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。

        2）与0相异或值不变

例如：1010 1110 ^ 0000 0000 = 1010 1110

        3）交换两个数

实例
void Swap(int &a, int &b){
    if (a != b){
        a ^= b;
        b ^= a;
        a ^= b;
    }
}