天天看點
傳回

面試刷算法，這些api不可不知！集合數學

大家好，我是老三，最近在刷算法，發現有些api記得不熟，是以整理了一波，如果你也在刷題，趕緊

收藏

吧！

集合

在刷題中，各種資料結構是我們常常用到的，例如棧實作疊代、哈希存儲鍵值對等等，我們來看看常用集合和相關api。

類/接口 描述 方法
String 字元串 charAt toCharArray split substring indexOf lastIndexOf replace length
List 清單 add remove get size subList
Stack 棧 push pop peek isEmpty size
Queue 隊列 offer poll peek isEmpty size
Deque 雙向隊列 offerFirst offerLast pollFirst pollLast peekFirst peekLast isEmpty size
PriorityQueue 優先隊列
Set add remove contains isEmpty size first(TreeSet) last(TreeSet)
Map put get getOrDefault containsKey containsValue keySet values isEmpty size

數組

數組就不用多說什麼了，大家最熟悉的資料結構。

Arrays

Arrays是比較常用的數組工具類，可以完成排序、拷貝等功能。

  • 從小到大排序：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)
  • 拷貝：Array.copyOf 
int[] a = new int[5];
int[] newA = Array.copyOf(a, 5);

清單主要有兩種實作，分别是順序表和連結清單。

面試刷算法，這些api不可不知！集合數學

順序表本質是一個可以動态擴容的數組，在Java中的實作是

ArrayList

。

連結清單是一個雙向連結清單，Java中連結清單的實作為

LinkedList

LinkedList

在Java中可謂是非常強大的一個集合類，它還可以作為雙向隊列、棧來使用。

注意，ArrayList的擴容需要将舊的數組的元素複制到新的數組，時間複雜度為O(n)。

基本方法

  • 構造 
List<Integer> array = new ArrayList<>();    // 順序表
// Set<Integer> a = new HashSet....
List<Integer> b = new ArrayList<>(a);     //接受一個集合容器
  • get 
get(int index)    // 傳回元素位置在index的元素e --- array O(1), list O(n)
  • size 
size()    // 傳回數組/連結清單長度 --- O(1)
  • add 
add(E e)    // 在尾部添加一個元素e --- O(1)
add(int index, E e)    // 在index位置插一個元素e --- O(n)
  • remove 
.remove(int index)    // 删除位于index的元素，并傳回删除元素e --- 删除最後元素為O(1)， 其餘為O(n)
//删除最後元素 list.remove(list.size() - 1);
  • subList 
.subList(int from, int to)    // 相當于傳回原數組的一個片段,但不要對其進行改動，改動會影響原數組 --- O(1)
// List<Integer> list, 對原來的list和傳回的list做的“非結構性修改”(non-structural changes)，
//都會影響到彼此對方. 如果你在調用了sublist傳回了子list之後，如果修改了原list的大小，那麼之前産生的子list将會失效，變得不可使用

集合工具

Collections是集合工具類，提供了一些操作集合的方法。

  • 排序 
Collections.sort(list); 從小到大排序
Collections.sort(list, (o1, o2) -> o2 - o1); 從大到小排序， 第二個參數為一個比較器

兩種實作，ArrayList利于查找，LinkedList利于增删。

大概對比如下：

操作 ArrayList LinkedList
get(int index) O(1) O(n)，平均 n / 4步
add(E element) 最壞情況（擴容）O(n) ，平均O(1)
add(int index, E element) O(n) ,平均n / 2步
remove(int index) O(n) 平均n /2步

Java中定義了

Stack

接口，實作類是

Vector

Vector

是一個祖傳集合類，不推薦使用。

那應該用什麼呢？

Deque

接口實作了完善堆棧操作集合，它有一個我們熟悉的實作類

LinkedList
面試刷算法，這些api不可不知！集合數學
Deque<Integer> stack=new LinkedList<>();
  • push 
push(E e);    // 入棧元素e， 傳回值為元素e --- O(1)
  • pop 
.pop();    // 出棧一個元素，傳回出棧元素e --- O(1)
  • peek 
peek();    // 檢視棧頂元素， 傳回值為棧頂元素e --- O(1)
  • isEmpty 
isEmpty()    // 若棧空傳回true， 否則傳回false --- O(1)      
size()    // 傳回棧中元素個數 --- O(1)

隊列s是一種先進先出的結構，在Java中的接口定義是

Queue

，具體實作還是我們的老朋友

LinkedList

 
Queue<Integer> q = new LinkedList<>();
  • offer 
offer(E e);    // 隊尾加入元素e。 若成功入隊傳回值true，否則傳回false --- O(1)
  • poll 
poll();    // 出隊頭，傳回出隊元素e --- O(1)      
peek();    // 檢視隊頭元素， 傳回值隊首元素e --- O(1)      
isEmpty()    // 若隊空傳回true， 否則傳回false --- O(1)      
size()    // 傳回隊中元素個數 --- O(1)

Queue

有一個子接口

Dueue

，即雙向隊列，和單向隊列不同，它的出隊入隊可以從兩個方向。

面試刷算法，這些api不可不知！集合數學
Dueue<Integer> q = new LinkedList<>();
  • offFirst 
offFirst(Object e)   // 将指定元素添加到雙端隊列的頭部 --- O(1)
  • offLast 
offLast(Object e)   //将指定元素添加到雙端隊列的尾部 --- O(1)
  • pollFirst 
pollFirst()   //擷取并删除雙端隊列的第一個元素 --- O(1)
  • pollLast 
pollLast()   //擷取并删除雙端隊列的最後一個元素 --- O(1)
  • peekFirst 
peekFirst()   //擷取但不删除雙端隊列的第一個元素 --- O(1)
  • peekLast 
peekLast()   //擷取但不删除雙端隊列的最後一個元素 --- O(1)

優先隊列是一種比較特殊的隊列，儲存隊列元素的順序不是按照元素添加的順序來儲存的，而是在添加元素的時候對元素的大小排序後再儲存。

是以在隊頭的元素不是按照先後順序，而是按照大小順序。

在Java中的實作是

PriorityQueue

，底層是一棵樹， 以小根堆為例。對于任意結點來說，該節點的值比其左右孩子的值都要小。 （就是最上面的結點最小）。 大根堆類似，最上面結點最大

    • 小根堆 
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的大根堆。在當中增加元素會擴容，隻是開始指定大小      
offer(E e);    // 在堆中加入元素e，并調整堆。若成功入堆傳回值true，否則傳回false --- O(logN)      
poll();    // 彈出堆頂元素，并重新調整堆，傳回出隊元素e --- O(logN)      
peek();    // 檢視堆頂元素， 傳回值堆頂元素e --- O(1)

散清單

散清單示一種<key,value>型的資料結構，在Java中的實作是

HashMap

 
Map<Characters, Integer> map = new HashMap<>();
  • put 
put(K key, V value);    // 在Map中加入鍵值對<key, value>。傳回value值。如果Map中有key，則replace舊的value --- O(1)      
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)

get(x) == null // 可以代替改用法
  • 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()    // 若Map為空傳回true， 否則傳回false --- O(1)      
.size()    // 傳回Map中中鍵值對<K, V>的個數 --- O(1)

Set是一種沒有重複元素的集合，常用的實作是

HashSet

 
Set<Integer> set = new HashSet<>();
List<Integer> list = new ArrayList<>....;
Set<Integer> set = new HashSet<>(list);      
.add(E e);    // 在集合中添加元素E e， 若成功添加則傳回true，若集合中有元素e則傳回false --- O(1)      
remove(E e);    // 在集合中删除元素e，若删除成功傳回true；若集合中沒有元素e，傳回false --- O(1)
  • contains 
contains(E e);    // 若存在元素e，則傳回true，否則傳回false --- O(1)      
isEmpty()    // 若集合為空傳回true， 否則傳回false --- O(1)
• 1      
isEmpty()    // 若集合為空傳回true， 否則傳回false --- O(1)
  • first 
first()    // 傳回集合裡的最小值（若給了比較器從大到小則是傳回最大值）
  • last 
last()    // 傳回集合裡的最大值（若給了比較器從大到小則是傳回最小值）

不可變量(相當于隻讀final修飾)，每個位置元素是個char。

  • 初始化

字元串複制初始化

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);
  • 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 
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 
replace(char oldChar, char newChar);    // 傳回一個新字元串String，其oldChar全部變成newChar --- O(n)
  • toCharArray 
toCharArray();   // 傳回char[] 數組。 把String程式設計字元數組 --- O(n)
• 1
  • 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

由于String是所謂的不可變類，使用

str+

這種形式拼接字元串實際上，是JVM幫助循環建立StringBuilder來拼接，是以拼接字元串最好用StringBuilder。

StringBuilder sb = new StringBuilder();      
charAt(int index);    // 傳回index位置的char --- O(1)      
length();    // 傳回緩沖字元串長度 --- O(1)
  • apped 
append(String str)   // 拼接字元串 --- O(n)
  • toString 
toString();    // 傳回一個與建構起或緩沖器内容相同的字元串 --- O(n)

數學

最大最小值

在一些題目裡，需要用到最大，最小值，Java中各個資料類型的最大最小值定義如下：

fmax = Float.MAX_VALUE;

fmin = Float.MIN_VALUE;

dmax = Double.MAX_VALUE;

dmin = Double.MIN_VALUE;

bmax = Byte.MAX_VALUE;

bmin = Byte.MIN_VALUE;

cmax = Character.MAX_VALUE;

cmin = Character.MIN_VALUE;

shmax = Short.MAX_VALUE;

shmin = Short.MIN_VALUE;

imax = Integer.MAX_VALUE;

imin = Integer.MIN_VALUE;

lmax = Long.MAX_VALUE;

lmin = Long.MIN_VALUE;

Math

  • max 
Math.max(long a, long b);    //傳回兩個參數中較大的值
  • sqrt 
Math.sqrt(double a);    //求參數的算術平方根
  • abs 
Math.abs(double a);  //傳回一個類型和參數類型一緻的絕對值
  • pow 
Math.pow(double a, double b);  //傳回第一個參數的第二個參數次方。
  • ceil 
Math.ceil(double x);   //向上取整
  • floor 
Math.floor(double x);  //向下取整
  • round 
Math.round(double x);   //四舍五入

“簡單的事情重複做，重複的事情認真做，認真的事情有創造性地做！”——

我是

三分惡

 ，一個能文能武的全棧開發。

點贊

 、

關注

 不迷路，咱們下期見！
存儲 算法 java api java雜湊演算法 java算法支援 存儲自定義java java最短路算法 安全存儲java
上一篇: 新基建下的智能安防：緣何在科技探索的道路越來越“複雜化”？
下一篇: 【ECS常見問題】搶占式執行個體問題搶占式執行個體問題

繼續閱讀