ArrayList原始碼深度剖析
本篇文章主要跟大家分析一下ArrayList的源代碼，閱讀本文你首先得對ArrayList有一些基本的了解，至少使用過它，如果你對ArrayList的一些基本使用還不太熟悉或者在閱讀本文的時候感覺有點困難，你可以先閱讀這篇文章ArrayList設計與實作，自己動手寫ArrayList，
ArrayList繼承體系分析
RandomAccess，這個介面的含義表示可以隨機訪問ArrayList當中的資料，拿什么是隨機訪問呢？隨機訪問就是表示我們可以在常量時間復雜度內訪問資料，也就是時間復雜度是O(1)，因為在ArrayList當中我們使用的最基本的資料型別是陣列，而陣列是可以隨機訪問的，比如像下面這樣，
public static void main(String[] args) {
int[] data = https://www.cnblogs.com/Chang-LeHung/p/new int[10];
for (int i = 0; i < 10; i++)
data[i] = i;
System.out.println("data[5] = " + data[5]);
}
而鏈表是不可以隨機訪問的，比如說我們想通過下標訪問鏈表當中的某個資料，需要從頭結點或者尾節點開始遍歷，直到遍歷到下標對應的資料，比如下圖中的單鏈表找到第3個資料，需要從頭開始遍歷，而這個時間復雜度為O(n)，
Serializable，這個介面主要用于序列化，所謂序列化就是能將物件寫入磁盤，反序列化就是能夠將物件從磁盤當中讀取出來，如果想序列化和反序列化ArrayList的實體物件就必須實作這個介面，如果沒有實作這個介面，在實體化的時候程式執行會報錯，比如下面就是一個序列化的例子，
import java.io.*;
import java.util.Objects;
class TestPerson implements Serializable{
String name;
Integer age;
private static final long serialVersionUID = 9999L;
@Override
public String toString() {
return "TestPerson{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
TestPerson that = (TestPerson) o;
return that.age.equals(this.age) && that.name.equals(this.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
public TestPerson(String name, Integer age) {
this.name = name;
this.age = age;
}
}
public class SerialTest {
public static void main(String[] args) throws IOException, ClassNotFoundException {
TestPerson leHung = new TestPerson("LeHung", 18);
FileOutputStream os = new FileOutputStream("objtest");
ObjectOutputStream outputStream = new ObjectOutputStream(os);
// 序列化資料
outputStream.writeObject(leHung);
FileInputStream is = new FileInputStream("objtest");
ObjectInputStream stream = new ObjectInputStream(is);
// 反序列化資料
TestPerson object = (TestPerson) stream.readObject();
System.out.println(object);
System.out.println(object == leHung);
System.out.println(object.equals(leHung));
}
}
如果上面程式當中的TestPerson沒有implements Serializable，則上述代碼會報例外java.io.NotSerializableException:，
-
Cloneable，實作Cloneable介面那么實作Cloneable的類就能夠呼叫clone這個方法，如果沒有實作Cloneable介面就呼叫方法，則會拋出例外java.lang.CloneNotSupportedException， -
List，這個介面主要定義了一些集合常用的方法讓ArrayList進行實作，比如add，addAll，contains，remove，set，size，indexOf等等方法， -
AbstractList，這個抽象類也實作了List介面里面的方法，并且為其提供了默認代碼實作，比如說AbstractList中對indexOf的實作如下：
// 這個方法的作用就是回傳物件 o 在容器當中的下標
public int indexOf(Object o) {
// 通過迭代器去遍歷資料
ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
// 回傳資料 o 的下標
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))
// 回傳資料 o 的下標
return it.previousIndex();
}
return -1;
}
集合的addAll方法實作如下：
// 這個函式的作用就是在 index 的位置插入集合 c 當中所有的元素
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
boolean modified = false;
for (E e : c) {
add(index++, e);
modified = true;
}
return modified;
}
ArrayList關鍵欄位分析
在ArrayList當中主要有以下這些欄位：
// ArrayList 當中默認初始化容量，也就是初始化陣列的大小
private static final int DEFAULT_CAPACITY = 10;
// 存放具體資料的陣列 ArrayList 底層就是使用陣列進行存盤的
transient Object[] elementData;
// size 表示容器當中資料的個數 注意和容器的長度區分開來
private int size;
// 當容器當中沒有元素的時候將 elementData 賦值為以下資料（不同情況不一樣）
private static final Object[] EMPTY_ELEMENTDATA = https://www.cnblogs.com/Chang-LeHung/p/{};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 下面兩個函式是 ArrayList 的建構式，從下面兩個函式當中
// 我們可以看出 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 使用區別
// EMPTY_ELEMENTDATA 是容器當中沒有元素時使用，DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 是默認構造的時候使用
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = https://www.cnblogs.com/Chang-LeHung/p/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
ArrayList主要方法分析
add方法，這個方法用于往容器的末尾增加資料，也是ArrayList當中最核心的方法，他的主要作業流程如下圖所示：
他首先呼叫函式ensureCapacityInternal確保ArrayList當中的陣列長度能夠滿足需求，不然陣列會報陣列下標越界例外，add函式呼叫程序當中所涉及到的函式如下，
public boolean add(E e) {
// 這個函式的主要目的是確保 elementData 的容量有 size + 1
// 否則存盤資料的時候陣列就會越界
ensureCapacityInternal(size + 1);
// size 表示容器當中資料的個數 注意和容器的長度區分開來
// 加入資料之后 容器當中資料的個數也要 + 1
elementData[size++] = e;
return true;
}
// minCapacity 表示 ArrayList 中的陣列最小的長度
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(
// 這個函式計算陣列的最小長度
calculateCapacity(elementData, minCapacity)
);
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是無參構造的話，取默認長度和需求長度 minCapacity 中比較大的值
if (elementData =https://www.cnblogs.com/Chang-LeHung/p/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 這個表示容器發生改變的次數，我們在后續分析迭代器的時候進行分析
// 它跟容器擴容沒關系，現在可以不用管他
modCount++;
// 如果最小的需求容量 minCapacity 大于現在容器當中陣列的長度，則需要進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新陣列的長度為原陣列的長度的1.5倍，右移一位相當于除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新陣列的長度，小于需要的最小的容量，則更新陣列的長度為 minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 這個函式的主要目的是判斷整數是否發生溢位
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
上述代碼的呼叫流程如下：
get函式，獲取對應下標的資料，
public E get(int index) {
// 進行陣列下標的檢查，如果下標超過 ArrayList 中資料的個數，則拋出例外
// 注意這里是容器當中資料的個數 不是陣列的長度
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
// 回傳對應下標的資料
return (E) elementData[index];
}
remove函式，洗掉ArrayList當中的資料，
// 通過下標洗掉資料，這個函式的意義是洗掉下標為 index 的資料
public E remove(int index) {
// 首先檢查下標是否合法，如果不合法，拋出下標越界例外
rangeCheck(index);
modCount++;
E oldValue = https://www.cnblogs.com/Chang-LeHung/p/elementData(index);
// 因為洗掉某個資料，需要將該資料后面的資料往陣列前面移動
// 這里需要計算需要移動的資料的個數
int numMoved = size - index - 1;
if (numMoved > 0)
// 通過拷貝移動資料
// 這個函式的意義是將 index + 1和其之后的資料整體移動到 index
// 的位置
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 因為最后一個資料已經拷貝到前一個位置了，所以可以設定為 null
// 可以做垃圾回收了
elementData[--size] = null;
return oldValue;
}
// 這個函式的意義是洗掉容器當中的第一個等于 o 的資料
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 這個方法和第一個 remove 方法原理一致
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
set方法，這個方法主要是用于設定指定下標的資料，這個方法比較簡單，
public E set(int index, E element) {
rangeCheck(index);
E oldValue = https://www.cnblogs.com/Chang-LeHung/p/elementData(index);
elementData[index] = element;
return oldValue;
}
ArrayList中那些不為人知的方法
ensureCapacity方法
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
這個方法我們在前面已經提到過了，不知道大家有沒有觀察到他的訪問修飾符是public，為什么要設定為public呢？這個意思很明顯，我們可以在使用ArrayList的時候自己呼叫這個方法，防止當我們在往容器中加入資料的時候頻繁因為陣列長度不夠重新申請記憶體，而原來的陣列需要從新釋放，這會給垃圾回收器造成壓力，我們在ArrayList設計與實作，自己動手寫ArrayList這篇文章當中寫過一段測驗程式去測驗這個方法，感興趣的同學可以去看看！！！
toString方法
我們首先來看一下下面代碼的輸出
public class CodeTest {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
}
System.out.println(list);
}
}
// 輸出結果：
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
執行上面一段代碼我們可以在控制臺看見對應的輸出，我們知道最終列印在螢屏上的是一個字串，那這個字串怎么來的呢，我們列印的是一個物件，它是怎么得到字串的呢？我們可以查看System.out.println的源代碼：
public void println(Object x) {
String s = String.valueOf(x);
synchronized (this) {
print(s);
newLine();
}
}
從上述代碼當中我們可以看見通過String s = String.valueOf(x);這行代碼得到了一個字串，然后進行列印，我們在進入String.valueOf方法看看是如何得到字串的：
public static String valueOf(Object obj) {
return (obj == null) ? "null" : obj.toString();
}
我們可以看到如果物件不為 null 最終是呼叫物件的toString方法得到的字串，因此當列印一個物件的時候，最侄訓列印這個物件的toString方法回傳的字串，
toString方法沒有直接在ArrayList當中實作，而是在它繼承的類AbstractList當中實作的，toString的源代碼如下所示：
public String toString() {
// 得到 ArrayList 的迭代器 這個迭代器我們稍后細說
Iterator<E> it = iterator();
// 如果容器當中沒有資料則回傳空
if (! it.hasNext())
return "[]";
// 額，寫這個代碼的工程師應該不懂中文 哈哈哈
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
// 將物件加入到 StringBuilder 當中，這里加入的也是一個物件
// 但是在 append 源代碼當中會同樣會使用 String.ValueOf
// 得到物件的 toString 方法的結果
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
上述代碼的整個程序還是比較清晰的，大致程序如下：
- 如果容器當中沒有資料，直接回傳[]，
- 如果容器當中有資料的話，那么通過迭代每個資料，呼叫
StringBuilder的append方法，將資料加入到輸出的StringBuilder物件當中，下面是append的源代碼，
// StringBuilder 的 append 方法
@Override
public StringBuilder append(Object obj) {
return append(String.valueOf(obj));
}
// StringBuilder 的 append 方法的多載方法
@Override
public StringBuilder append(String str) {
super.append(str);
return this;
}
// String 類中的 valueOf方法
public static String valueOf(Object obj) {
return (obj == null) ? "null" : obj.toString();
}
我們可以發現最終append到StringBuilder當中的字串仍然是ArrayList當中資料物件的toString方法回傳的資料，
equals方法
在ArrayList當中的equals方法和toString方法一樣，equlas方法也是在類AbstractCollection當中實作的，其源代碼如下：
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof List))
return false;
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return !(e1.hasNext() || e2.hasNext());
}
上面代碼的主要流程：
- 首先判斷
o和this是否是同一個物件，如果是則回傳true，比如下面這種情況：
ArrayList<Object> list = new ArrayList<>();
list.equals(ArrayList);
- 如果物件沒有實作
List介面回傳false， - 逐個判斷鏈表里面的物件是否相等（呼叫鏈表當中存盤的物件的
equals方法），如果兩個鏈表當中節點數目一樣而且都相等則回傳true否則回傳false，
通過上面的分析我們可以發現ArrayList方法并沒有讓比較的物件是ArrayList物件，只需要實作List介面并且資料數目和內容都相同，這樣equals方法回傳的結果就是true，比如下面代碼就驗證的這個結果：
LinkedList<Integer> list = new LinkedList<>();
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
arrayList.add(i);
}
System.out.println(arrayList.equals(list)); // 結果為 true
clone方法
ArrayList的方法比較簡單，就是拷貝了原ArrayList當中的陣列中的資料，
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = https://www.cnblogs.com/Chang-LeHung/p/Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
整個拷貝程序如下如所示：
雖然發生了陣列的拷貝，但是拷貝之后的陣列中資料的指向并沒有發生變化，也就是說兩個陣列指向的內容是一樣的，如果一個陣列改變了所指向的資料，另外一個陣列當中的資料也會發生變化，比如下面的代碼：
package makeyourowncontainer.test;
import java.util.ArrayList;
class Person {
String name;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
'}';
}
}
public class ArrayListTest {
public static void main(String[] args) {
ArrayList<Person> o1 = new ArrayList<>();
Person person = new Person();
person.setName("一無是處的研究僧");
o1.add(person);
Object o2 = o1.clone();
System.out.println("o1 = " + o1);
System.out.println("o2 = " + o2);
((ArrayList<Person>) o2).get(0).setName("LeHung");
System.out.println("改變資料之后");
System.out.println("o1 = " + o1);
System.out.println("o2 = " + o2);
}
}
// 輸出結果
o1 = [Person{name='一無是處的研究僧'}]
o2 = [Person{name='一無是處的研究僧'}]
改變資料之后
o1 = [Person{name='LeHung'}]
o2 = [Person{name='LeHung'}]
神秘的迭代器Iterator
Iterator介紹
我們在分析toString方法的時候，有下面這樣一行代碼：
Iterator<E> it = iterator();
然后不斷通過迭代器的hasNext和next方法對資料進行迭代，比如下面這個例子：
public void testArrayList() {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++)
list.add(i);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
// iterator 方法回傳的物件
public Iterator<E> iterator() {
return new Itr();
}
Iterator欄位分析
Itr類是ArrayList的內部類，接下來我們仔細分析Itr類的實作，
在Itr類當中主要有一下幾個欄位：
int cursor; // 下一個元素的下標 當我們 new 這個物件的時候這個值默認初始化為0
// 我們使用的時候也是0這個值，因此不用顯示初始化
int lastRet = -1; // 上一個通過 next 方法回傳的元素的下標
int expectedModCount = modCount;
// modCount 表示陣列當中資料改變的次數 modCount 是
// ArrayList 當中的類變數 expectedModCount 是 ArrayList
// 內部類 Itr 中的類變數 然后將這個變數保存到 expectedModCount當中
// 使用 expectedModCount 主要用于 fast-fail 機制這個我們后面會分析
我們現在來花點時間好好談一下modCount（英文全稱為：modifications count，修改次數）這個欄位，當ArrayList當中發生一次結構修改(Structural modifications)時，modCount就++，所謂結構修改就是那些讓ArrayList當中陣列的資料個數size發生變化的操作，比如說add、remove方法，因為這兩個方法一個是增加資料，一個是洗掉資料，都會導致容器當中資料個數發生變化，而set方法就不會是的modCount發生變化，因為沒有改變容器當中資料的個數，
Iterator的初始化方法：
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
}
在初始化方法當中，沒有任何操作也就印證了我們前面在分析欄位的時候說的 cursor的初始化的值為0，
Iterator重要方法
接下來分析迭代器當中比較重要的兩個方法next和hasNext，
public boolean hasNext() {
// 這個 size 是外部類 ArrayList 當中的 size 表示的是 ArrayList
// 當中資料元素的個數，cursor 的初始值為 0 每呼叫一個 next cursor
// 的值就+1，當等于 size 是容器當中的資料已經遍歷完成了 hasNext 就回傳 false 了
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
// 這個方法主要是用于檢測在資料迭代的程序當中 ArrayList 是否發生 `結構修改`
// 如果發生結構修改就拋出 ConcurrentModificationException 例外
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = https://www.cnblogs.com/Chang-LeHung/p/ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 更改 cursor 的值 并將其設定為下一個回傳元素的下標 這一點我們在
// 欄位分析的時候已經談到過了
cursor = i + 1;
// 回傳資料 運算式 lastRet = i 的回傳值為 i
// 這個運算式不僅將 lastRet 的值賦值為 i 同時回傳 i
// 因此可以回傳下標為 i 的資料
return (E) elementData[lastRet = i];
}
// 這個方法主要是用于檢測在資料迭代的程序當中 ArrayList 是否發生 `結構修改`
// 如果發生結構修改就拋出 ConcurrentModificationException 例外
final void checkForComodification() {
// 如果發生 `結構修改` 那么 modCount 的值會++ 那么就和 expectedModCount 不相等了
// expectedModCount 初始化的時候令其等于 expectedModCount
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
為什么要拋出ConcurrentModificationException例外呢，我們先想想是什么導致modCount發生變化，肯定迭代器在進行遍歷的同時，修改了modCount的值，通常這種現象的發生出現在并發的情況下，因此拋出ConcurrentModificationException例外，像這種通過迭代器遍歷程序進行檢查并且當發生不符合條件的情況下拋出例外的現象就稱作Fast-fail，
其實我們也可以在不使用并發的情況讓迭代器拋出這個例外，我們只需要在迭代器迭代的時候我們對ArrayList進行add和remove操作即可，比如像下面這樣就會拋出ConcurrentModificationException：
public void testArrayList() {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++)
list.add(i);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
list.add(55);
}
}
Iterator中的remove方法
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
// 進行合法性檢查，看是否需要拋出例外
checkForComodification();
try {
// 呼叫 ArrayList 的remove方法實作
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 因為 remove 會改變 modCount 的值，因此需要將 expectedModCount 重新賦值
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
ArrayList雜談
時間復雜度分析
- 因為
ArrayList是隨機存取的，因此我們通過下標查找資料的時間復雜度是O(1)， - 插入資料的時間復雜度是
O(n)，
擴容機制
還記的我們在ArrayList設計與實作，自己動手寫ArrayList當中自己實作ArrayList使用的擴容機制嗎？我們自己的擴容機制為擴容為原來長度的兩倍，而ArrayList當中的擴容機制為擴容為原來的1.5倍，
假設我們在使用ArrayList的時候沒有指定初始化的時候陣列的長度，也就是說初始長度為ArrayList的默認長度也就是10，那么當我們不停地往容器當中增加資料，擴容導致的陣列長度的變化如上圖所示，橫軸表示擴容次數，縱軸表示陣列長度，藍色的擴容為原陣列長度的1.5倍，另外一條是2倍，我們很清晰的發現擴容為原來的2倍在后期的陣列長度將會遠大于擴容1.5倍，這很可能會導致我們會浪費很大的陣列空間，比如說剛好加入最后一個資料的時候導致ArrayList進行擴容操作，這可能是ArrayList在設計時候的考量，
本篇文章我們仔細分析介紹了ArrayList的原始碼，希望大家有所識訓，我是LeHung，我們下期再見！！！
更多容器設計的內容在專案https://github.com/Chang-LeHung/CSCore!!!
關注公眾號：一無是處的研究僧，了解更多計算機知識，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498629.html
標籤：其他
上一篇：演算法競賽進階指南0x41并查集
下一篇：Leetcode 2 兩數相加