刷题常用API

数组

静态数组

1
2
3
4
5
// 一维
String[] s = new String[3];
char[] b = new char[]{'a', 'b'};  
// 二维
int[][] c = new int[10][10];

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

Arrays.sort 排序

1
2
3
4
5
Arrays.sort(int[] arr)	//从小到大排序
Arrays.sort(int[] arr, int fromIndex, int toIndex) // [)
Arrays.sort(int[] arr, int fromIndex, int toIndex, 比较器); //一定是需要泛型
Arrays.sort(arr, (o1, o2) -> o2 - o1); //数组全部 从大到小排序 跟Collections.sort()一样
Arrays.sort(arr, 0, 3, (o1, o2) -> o2 - o1); //从大到小排序，只排序[0, 3)

Arrays.fill填满一个数组

1
2
int[] a = new int[5];
Arrays.fill(a, 1);

Arrays.copyOf / arr.clone() 复制一个数组

1
2
3
4
5
int [] a =  new int [ 5 ];
int [] newA = Array.copyOf(a,  5 );
// or
int [][] a = {{ 1 }, { 1 , 2 }, { 1 , 2 , 3 }, { 1 , 2 , 3 , 4 }, { 1 , 2 , 3 , 4 , 5 }}; // 不是5*5，第一维1 2 3 4 5
int [][] newa = a.clone();  // 不是5*5矩阵

相等比较

1
System.out.println(Arrays.equals(arr1,arr2))

arr1.equals(arr2)比较的是两个对象的地址，不是里面的数，而Arrays.equals重写了equals，所以，这里能比较元素是否相等。

二分查找法找指定元素的索引值（下标）

1
2
int []arr = {10,20,30,40,50};
System.out.println(Arrays.binarySearch(arr, 20)); // 找不到的话返回-x

截取数组：copeOf和copeOfRange

1
2
3
4
int []arr = {10,20,30,40,50}; 
int []arr1 = Arrays.copyOf(arr, 3);//截取arr数组的3个元素赋值给姓数组arr1  10 20 30 
int []arr = {10,20,30,40,50};
int []arr1 = Arrays.copyOfRange(arr,1,3);// [) 10 20

动态数组

1
2
3
List<Integer> array = new ArrayList<>();    // 数组
List<Integer> list = new LinkedList<>();    // 链表
List<List<Integer>> = new ArrayList<>();	// 二维数组

List接口方法:get, size, add, remove, subList

1
2
3
4
5
6
7
.get(int index)
.size()
.add(E e)    // 在尾部添加一个元素e --- O(1)
.add(int index, E e)    // 在index位置插一个元素e --- O(n)
.remove(int index)    // 删除位于index的元素，并返回删除元素e
list.remove(list.size() - 1);
.subList(int from, int to)    // 相当于返回原数组的一个片段,但不要对其进行改动，改动会影响原数组

Collections.sort(list); 从小到大排序

Collections.sort(list, (o1, o2) -> o2 - o1); 从大到小排序， 第二个参数为一个比较器

Collections.reverse(list); 反转，倒序

Collections.max(list); 取最大值

Collections.min(list); 取最小值

StringBuilder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
StringBuilder sb = new StringBuilder();
StringBuilder sb = StringBuilder(String str);// 构建一个值为str的可变字符串。

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

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

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

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

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

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

// 在此字符串追加str。
append(String str);

// 在此字符串追加str。
append(StringBuilder str);

// 将char的子数组追加到此字符串
append(char[] str, int offset, int len);

Arrays

1
2
3
4
5
6
7
8
9
10
11
// 从小到大排序
Arrays.sort(int[] arr)
// 从小到大排序 左闭右开[)
Arrays.sort(int[] arr, int fromIndex, int toIndex)
// 数组全部 从大到小排序 跟Collections.sort()一样
Arrays.sort(arr, (o1, o2) -> o2 - o1);
// 从大到小排序，只排序[fromIndex, toIndex)
Arrays.sort(arr, fromIndex, toIndex, (o1, o2) -> o2 - o1);

// 将指定arr数组作为列表返回
Arrays.asList(arr)

集合

map

方法：put, get, getOrDefault, containsKey, containsValue, keySet, values, isEmpty, size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.HashMap; 
import java.util.Iterator; 
import java.util.Map;

public class TestMap { 
        public static void main(String[] args) { 
                Map<String, String> map = new HashMap<String, String>(); 
                map.put("1", "a"); 
                map.put("2", "b"); 
                map.put("3", "c"); 
 
                // 最简洁、最通用的遍历方式 
                for (Map.Entry<String, String> entry : map.entrySet()) { 
                        System.out.println(entry.getKey() + " = " + entry.getValue()); 
                } 
          
          //.keySet();    // 返回一个Set,这个Set中包含Map中所有的Key --- O(1)
          for (Character key : map.keySet()) {
    			// Operate with each key
					}
          //.values();    // 返回一个Collection<v>,里面全是对应的每一个value --- O(1)
          for (Integer value : map.values()) {
    			// Operate with each values
					}
        }
}

Set

1
2
3
4
Set<Integer> set = new HashSet<>();
// 把集合如Stack、Queue、List等Collection作为参数
List<Integer> list = new ArrayList<>....;
Set<Integer> set = new HashSet<>(list);

queue（队列）

方法：offer, poll, peek, isEmpty, size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Queue; 
import java.util.concurrent.LinkedBlockingQueue; 
 
public class TestQueue { 
        public static void main(String[] args) { 
           			// 初始化
                Queue<Integer> q = new LinkedBlockingQueue<Integer>();
          			// 把集合如Stack、Set、List等Collection作为参数
          			Set<Integer> s = new HashSet<>();
								Queue<Integer> q = new LinkedList<>(s);
                // 初始化队列 
                for (int i = 0; i < 5; i++) { 
                        q.offer(i); //入队
                } 
                System.out.println("-------1-----"); 
                // 集合方式遍历，元素不会被移除 
                for (Integer x : q) { 
                        System.out.println(x); 
                } 
                System.out.println("-------2-----"); 
                // 队列方式遍历，元素逐个被移除 
                while (q.peek() != null) { 
                        System.out.println(q.poll()); //出队
                } 
        } 
}

Stack（栈）

方法：push, pop, peek, isEmpty, size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Stack; 
 
public class TestStack { 
        public static void main(String[] args) { 
          			// 初始化
                Stack<Integer> s = new Stack<Integer>();
                for (int i = 0; i < 10; i++) { 
                        s.push(i); // 入栈
                } 
                // 集合遍历方式 
                for (Integer x : s) { 
                        System.out.println(x); 
                } 
                System.out.println("------1-----"); 
                // 栈弹出遍历方式 
//                while (s.peek()!=null) {     // 不健壮的判断方式，容易抛异常，正确写法是下面的 
                while (!s.isEmpty()) { 
                        System.out.println(s.pop()); // 出栈
                } 
                System.out.println("------2-----"); 
                // 错误的遍历方式 
//                for (Integer x : s) { 
//                        System.out.println(s.pop()); 
//                } 
        } 
}

Deque(双端队列)

  • addFirst() - 在双端队列的开头添加指定的元素。如果双端队列已满，则引发异常。
  • addLast() - 在双端队列的末尾添加指定的元素。如果双端队列已满，则引发异常。
  • offerFirst() - 在双端队列的开头添加指定的元素。如果双端队列已满，则返回false。
  • offerLast() - 在双端队列的末尾添加指定的元素。如果双端队列已满，则返回false。
  • getFirst() - 返回双端队列的第一个元素。如果双端队列为空，则引发异常。
  • getLast() - 返回双端队列的最后一个元素。如果双端队列为空，则引发异常。
  • peekFirst() - 返回双端队列的第一个元素。如果双端队列为空，则返回null。
  • peekLast() - 返回双端队列的最后一个元素。如果双端队列为空，则返回null。
  • removeFirst() - 返回并删除双端队列的第一个元素。如果双端队列为空，则引发异常。
  • removeLast() - 返回并删除双端队列的最后一个元素。如果双端队列为空，则引发异常。
  • pollFirst() - 返回并删除双端队列的第一个元素。如果双端队列为空，则返回null。
  • pollLast() - 返回并删除双端队列的最后一个元素。如果双端队列为空，则返回null。

双端队列作为堆栈数据结构

Java Collections框架的Stack类提供了堆栈的实现。

但是，建议Deque用作堆栈而不是Stack类。这是因为Stack的方法是同步的。

以下是Deque接口提供的用于实现堆栈的方法：

  • push() - 在双端队列的开头添加元素
  • pop() - 从双端队列的开头删除元素
  • peek() - 从双端队列的开头返回一个元素

PriorityQueue (优先级队列)

1
2
3
4
5
6
7
// 小根堆
Queue<Integer> minH = new PriorityQueue<>((i1, i2) -> i1 - i2);    // 小根堆，默认大小为11 相当于  new PriorityQueue<>(11,(i1, i2) -> i2 - i1)
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的大根堆。在当中增加元素会扩容，只是开始指定大小
  • add() - 将指定的元素插入队列。如果队列已满，则会引发异常
  • offer() - 将指定的元素插入队列。如果队列已满，则返回false
  • peek()方法。返回队列的头部元素
  • remove() - 从队列中删除指定的元素
  • poll() - 返回并删除队列的开头
  • size() - 返回优先级队列的长度