数据结构与算法(1)——数组与链表
數(shù)組
什么是數(shù)組？
數(shù)組簡(jiǎn)單來(lái)說(shuō)就是將所有的數(shù)據(jù)排成一排存放在系統(tǒng)分配的一個(gè)內(nèi)存塊上，通過(guò)使用特定元素的索引作為數(shù)組的下標(biāo)，可以在常數(shù)時(shí)間內(nèi)訪問(wèn)數(shù)組元素的這么一個(gè)結(jié)構(gòu)；
為什么能在常數(shù)時(shí)間內(nèi)訪問(wèn)數(shù)組元素？
為了訪問(wèn)一個(gè)數(shù)組元素，該元素的內(nèi)存地址需要計(jì)算其距離數(shù)組基地址的偏移量。需要用一個(gè)乘法計(jì)算偏移量，再加上基地址，就可以獲得某個(gè)元素的內(nèi)存地址。首先計(jì)算元素?cái)?shù)據(jù)類(lèi)型的存儲(chǔ)大小，然后將它乘以元素在數(shù)組中的索引，最后加上基地址，就可以計(jì)算出該索引位置元素的地址了；整個(gè)過(guò)程可以看到需要一次乘法和一次加法就完成了，而這兩個(gè)運(yùn)算的執(zhí)行時(shí)間都是常數(shù)時(shí)間，所以可以認(rèn)為數(shù)組訪問(wèn)操作能在常數(shù)時(shí)間內(nèi)完成；
數(shù)組的優(yōu)點(diǎn)
- 簡(jiǎn)單且易用；
- 訪問(wèn)元素快（常數(shù)時(shí)間）；
數(shù)組的缺點(diǎn)
- 大小固定：數(shù)組的大小是靜態(tài)的（在使用前必須制定數(shù)組的大小）；
- 分配一個(gè)連續(xù)空間塊：數(shù)組初始分配空間時(shí)，有時(shí)候無(wú)法分配能存儲(chǔ)整個(gè)數(shù)組的內(nèi)存空間（當(dāng)數(shù)組規(guī)模太大時(shí)）；
- 基于位置的插入操作實(shí)現(xiàn)復(fù)雜：如果要在數(shù)組中的給定位置插入元素，那么可能就會(huì)需要移動(dòng)存儲(chǔ)在數(shù)組中的其他元素，這樣才能騰出指定的位置來(lái)放插入的新元素；而如果在數(shù)組的開(kāi)始位置插入元素，那么這樣的移動(dòng)操作開(kāi)銷(xiāo)就會(huì)很大。
關(guān)于數(shù)組的一些問(wèn)題思考
1）在索引沒(méi)有語(yǔ)義的情況下如何表示沒(méi)有的元素？
我們創(chuàng)建的數(shù)組的索引可以有語(yǔ)義也可以沒(méi)有語(yǔ)義，比如我現(xiàn)在只是單純的想存放100，98，96這三個(gè)數(shù)字，那么它們保存在索引為0，1，2的這幾個(gè)地方或者其他地方都可以，無(wú)論它們之間的順序怎樣我都不關(guān)心，因?yàn)樗鼈兊乃饕菦](méi)有語(yǔ)義的我只是想把它們存起來(lái)而已；但是如果它們變成了學(xué)號(hào)為1，2，3這幾個(gè)同學(xué)對(duì)應(yīng)的成績(jī)，那么它們的索引就有了語(yǔ)義，索引0對(duì)應(yīng)了學(xué)號(hào)為1的同學(xué)的成績(jī)，索引1對(duì)應(yīng)了學(xué)號(hào)2的同學(xué)，索引2對(duì)應(yīng)了學(xué)號(hào)3的同學(xué)，因?yàn)閿?shù)組的最大的優(yōu)點(diǎn)是訪問(wèn)元素是在常數(shù)時(shí)間，所以我們使用數(shù)組最好就是在索引有語(yǔ)義的情況下；
好了，那么如果在索引沒(méi)有語(yǔ)義的情況下，我們?nèi)绾伪硎緵](méi)有的元素呢？例如上圖中，對(duì)于用戶(hù)而言，訪問(wèn)索引為3和4的數(shù)組元素是違法的，因?yàn)樗鼈兏揪筒淮嬖?#xff0c;我們?nèi)绾伪硎緵](méi)有的元素呢？
表示為0或者-1？
2）如何添加元素和刪除元素呢？
我們知道，數(shù)組的明顯缺點(diǎn)是在創(chuàng)建之前需要提前聲明好要使用的空間，那么當(dāng)我們空間滿(mǎn)了該如何處理呢？又該如何刪除元素呢？在Java中提供給我們的默認(rèn)數(shù)組是不支持這些功能的，我們需要開(kāi)發(fā)屬于自己的數(shù)組類(lèi)才行；
使用泛型封裝自己的數(shù)組類(lèi)
我們需要自己創(chuàng)建一個(gè)Array類(lèi)，并實(shí)現(xiàn)一些增刪改查的功能，大體的結(jié)構(gòu)如下：
public class Array<E>{private E[] data;private int size;/* 一些成員方法 */ }我們需要一個(gè)成員變量來(lái)保存我們的數(shù)據(jù)，這里是data，然后需要一個(gè)int類(lèi)型來(lái)存放我們的有效元素的個(gè)數(shù)，在這里我們沒(méi)有必要再多定義一個(gè)表示數(shù)組空間的變量，因?yàn)檫@里的空間大小就是data.length；
默認(rèn)的構(gòu)造函數(shù)
我們需要?jiǎng)?chuàng)建一些方法來(lái)初始化我們的數(shù)組，那肯定是需要傳一個(gè)capacity來(lái)表示數(shù)組的容量嘛：
// 構(gòu)造函數(shù)，傳入數(shù)組的容量capacity構(gòu)造Array public Array(int capacity) {data = (E[]) new Object[capacity];size = 0; }當(dāng)然我們也需要?jiǎng)?chuàng)建一個(gè)默認(rèn)的構(gòu)造函數(shù)來(lái)為不知道初始該定義多少的用戶(hù)一個(gè)默認(rèn)大小的數(shù)組：
// 無(wú)參數(shù)的構(gòu)造函數(shù)，默認(rèn)數(shù)組的容量capacity=10 public Array() {this(10); }這里演示的話給個(gè)10差不多了，實(shí)際可能會(huì)更復(fù)雜一些...
成員方法
就是增刪改查嘛，不過(guò)這里需要注意的是，為了實(shí)現(xiàn)我們自己的動(dòng)態(tài)數(shù)組，在增加和刪除中，我們對(duì)臨界值進(jìn)行了判斷，動(dòng)態(tài)的增加或者縮小數(shù)組的大小，而且提供了一些常用友好的方法給用戶(hù)；
// 獲取數(shù)組的容量 public int getCapacity() {return data.length; }// 獲取數(shù)組中的元素個(gè)數(shù) public int getSize() {return size; }// 返回?cái)?shù)組是否為空 public boolean isEmpty() {return size == 0; }// 在index索引的位置插入一個(gè)新元素e public void add(int index, E e) {if (index < 0 || index > size)throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");if (size == data.length)resize(2 * data.length);for (int i = size - 1; i >= index; i--)data[i + 1] = data[i];data[index] = e;size++; }// 向所有元素后添加一個(gè)新元素 public void addLast(E e) {add(size, e); }// 在所有元素前添加一個(gè)新元素 public void addFirst(E e) {add(0, e); }// 獲取index索引位置的元素 public E get(int index) {if (index < 0 || index >= size)throw new IllegalArgumentException("Get failed. Index is illegal.");return data[index]; }// 修改index索引位置的元素為e public void set(int index, E e) {if (index < 0 || index >= size)throw new IllegalArgumentException("Set failed. Index is illegal.");data[index] = e; }// 查找數(shù)組中是否有元素e public boolean contains(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e))return true;}return false; }// 查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1 public int find(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e))return i;}return -1; }// 從數(shù)組中刪除index位置的元素, 返回刪除的元素 public E remove(int index) {if (index < 0 || index >= size)throw new IllegalArgumentException("Remove failed. Index is illegal.");E ret = data[index];for (int i = index + 1; i < size; i++)data[i - 1] = data[i];size--;data[size] = null; // loitering objects != memory leakif (size == data.length / 4 && data.length / 2 != 0)resize(data.length / 2);return ret; }// 從數(shù)組中刪除第一個(gè)元素, 返回刪除的元素 public E removeFirst() {return remove(0); }// 從數(shù)組中刪除最后一個(gè)元素, 返回刪除的元素 public E removeLast() {return remove(size - 1); }// 從數(shù)組中刪除元素e public void removeElement(E e) {int index = find(e);if (index != -1)remove(index); }@Override public String toString() {StringBuilder res = new StringBuilder();res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));res.append('[');for (int i = 0; i < size; i++) {res.append(data[i]);if (i != size - 1)res.append(", ");}res.append(']');return res.toString(); }// 將數(shù)組空間的容量變成newCapacity大小 private void resize(int newCapacity) {E[] newData = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++)newData[i] = data[i];data = newData; }- 注意：為了更好的展示代碼而不太浪費(fèi)空間，所以這里使用//的風(fēng)格來(lái)注釋代碼；
- 特別注意：在remove方法中，縮小數(shù)組的判斷條件為size == data.length / 4 && data.length / 2 != 0，這是為了防止復(fù)雜度抖動(dòng)和安全性；
簡(jiǎn)單時(shí)間復(fù)雜度分析
添加操作
在添加操作中，我們可以明顯看到，addLast()方法是與n無(wú)關(guān)的，所以為O(1)復(fù)雜度；而addFirst()和add()方法都涉及到挪動(dòng)數(shù)組元素，所以都是O(n)復(fù)雜度，包括resize()方法；綜合起來(lái)添加操作的復(fù)雜度就是O(n)；
刪除操作
在刪除操作中，與添加操作同理，綜合來(lái)看刪除操作的復(fù)雜度就是O(n)；
修改操作
在修改操作中，如果我們知道了需要修改元素的索引，那么我們就可以在常數(shù)時(shí)間內(nèi)找到元素并進(jìn)行修改操作，所以很容易的知道這個(gè)操作時(shí)一個(gè)復(fù)雜度為O(1)的操作，所以修改操作的復(fù)雜度就是O(1)；但另外一種情況是我們不知道元素的索引，那么我們就需要先去查詢(xún)這個(gè)元素，我把這歸結(jié)到查詢(xún)操作中去；
查詢(xún)操作
在查詢(xún)操作中，如果我們已知索引，那么復(fù)雜度為O(1)；如果未知索引，我們需要遍歷整個(gè)數(shù)組，那么復(fù)雜度為O(n)級(jí)別；
總結(jié)
以上我們簡(jiǎn)單分析了我們自己創(chuàng)建的數(shù)組類(lèi)的復(fù)雜度：
- 增加：O(n)；
- 刪除：O(n)；
- 修改：已知索引 O(1)；未知索引 O(n)；
- 查詢(xún)：已知索引 O(1)；未知索引 O(n)；
均攤復(fù)雜度
如果細(xì)心的同學(xué)應(yīng)該可以注意到，在增加和刪除的復(fù)雜度分析中，如果我們都只是對(duì)最后一個(gè)元素進(jìn)行相應(yīng)的操作的話，那么對(duì)應(yīng)的O(n)的復(fù)雜度顯然是不合理的，我們之所以將他們的復(fù)雜度定義為O(n)，就是因?yàn)樵谖覀兺ǔ５膹?fù)雜度分析中我們需要考慮最壞的情況，也就是對(duì)應(yīng)的需要使用resize()方法擴(kuò)容的情況，但是這樣的情況并不是每一次都出現(xiàn)，所以我們需要更加合理的來(lái)分析我們的復(fù)雜度，這里提出的概念就是：均攤復(fù)雜度；
假設(shè)我們現(xiàn)在的capacity為5，并且每一次的添加操作都使用addLast()方法，那么我們?cè)谑褂昧宋宕蝍ddLast()方法之后就會(huì)觸發(fā)一次resize()方法，在前五次的addLast()方法中我們總共進(jìn)行了五次基本操作，也就是給數(shù)組的末尾添加上一個(gè)元素，在進(jìn)行第六次addLast()方法的時(shí)候，觸發(fā)resize()方法，就需要進(jìn)行一次元素的轉(zhuǎn)移，共5次操作（轉(zhuǎn)移五個(gè)元素嘛），然后再在末尾加上一個(gè)元素，也就是總共進(jìn)行了11次操作；
也就是說(shuō)：6次addLast()操作，觸發(fā)resize()方法，總共進(jìn)行了11次操作，平均下來(lái)，每次addLast()操作，進(jìn)行了2次基本操作（約等于）；那么依照上面的假設(shè)我們可以進(jìn)一步推廣為：假設(shè)capacity為n，n+1次addLast()操作，觸發(fā)resize()方法，總共進(jìn)行了2n+1次基本操作，平均來(lái)講，每次addLast()操作，進(jìn)行了2次基本操作，這樣也就意味著，均攤下來(lái)的addLast()方法的復(fù)雜度為O(1)，而不是之前分析的O(n)，這樣的均攤復(fù)雜度顯然比最壞復(fù)雜度來(lái)得更有意義，因?yàn)椴皇敲恳淮蔚牟僮鞫际亲顗牡那闆r！
同理，我們看removeLast()對(duì)應(yīng)的均攤復(fù)雜度也為O(1)；
復(fù)雜度震蕩
在我們的remove方法中，我們判斷縮小容量的條件為size == data.length / 4 && data.length / 2 != 0，這樣是為了防止復(fù)雜度震蕩和安全性（因?yàn)榭s小到一定的時(shí)候容量可能為1），這又是怎么一回事呢？我們考慮一下將條件改為size == data.length / 2的時(shí)候，出現(xiàn)的如下圖這樣的情況：
當(dāng)我們數(shù)組已經(jīng)滿(mǎn)元素的情況下，使用一次addLast方法，因?yàn)橛|發(fā)resize，數(shù)組容量擴(kuò)容為當(dāng)前的兩倍，所以此時(shí)復(fù)雜度為O(n)；這時(shí)候我們立即使用removeLast，因?yàn)榇藭r(shí)的容量等于n/2，所以會(huì)馬上產(chǎn)生縮小容量的操作，此時(shí)復(fù)雜度為O(n)；我們之前明明通過(guò)均攤復(fù)雜度分析出我們的兩個(gè)操作都為O(1)，而此時(shí)卻產(chǎn)生了震蕩，為了避免這樣的操作，我們需要懶操作一下，也就是在remove的時(shí)候不要立即縮容，而是等到size == capacity / 4的時(shí)候再縮小一半，這樣就有效的解決了復(fù)雜度震蕩的問(wèn)題；
Java中的ArrayList的擴(kuò)容
上面我們已經(jīng)實(shí)現(xiàn)了自己的數(shù)組類(lèi)，我們也順便看看Java中的ArrayList是怎么寫(xiě)的，其他的方法可以自己去看看，這里提出來(lái)一個(gè)grow()的方法，來(lái)看看ArrayList是怎么實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容的：
從上面的源碼我們可以看到ArrayList默認(rèn)增容是增加當(dāng)前容量的0.5倍（>> 1即乘以0.5）
鏈表
什么是鏈表
鏈表是一種用于存儲(chǔ)數(shù)據(jù)集合的數(shù)據(jù)結(jié)構(gòu)，它是最簡(jiǎn)單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，我們?cè)谏厦骐m然實(shí)現(xiàn)了動(dòng)態(tài)數(shù)組，但這僅僅是對(duì)于用戶(hù)而言，其實(shí)底層還是維護(hù)的一個(gè)靜態(tài)的數(shù)組，它之所以是動(dòng)態(tài)的是因?yàn)槲覀冊(cè)赼dd和remove的時(shí)候進(jìn)行了相應(yīng)判斷動(dòng)態(tài)擴(kuò)容或縮容而已，而鏈表則是真正意義上動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)；
鏈表的優(yōu)點(diǎn)
- 真正的動(dòng)態(tài)，不需要處理固定容量的問(wèn)題；
- 能夠在常數(shù)時(shí)間內(nèi)擴(kuò)展容量；
對(duì)比我們的數(shù)組，當(dāng)創(chuàng)建數(shù)組時(shí)，我們必須分配能存儲(chǔ)一定數(shù)量元素的內(nèi)存，如果向數(shù)組中添加更多的元素，那么必須創(chuàng)建一個(gè)新的數(shù)組，然后把原數(shù)組中的元素復(fù)制到新數(shù)組中去，這將花費(fèi)大量的時(shí)間；當(dāng)然也可以通過(guò)給數(shù)組預(yù)先設(shè)定一個(gè)足夠大的空間來(lái)防止上述時(shí)間的發(fā)生，但是這個(gè)方法可能會(huì)因?yàn)榉峙涑^(guò)用戶(hù)需要的空間而造成很大的內(nèi)存浪費(fèi)；而對(duì)于鏈表，初始時(shí)僅需要分配一個(gè)元素的存儲(chǔ)空間，并且添加新的元素也很容易，不需要做任何內(nèi)存復(fù)制和重新分配的操作；
鏈表的缺點(diǎn)
- 喪失了隨機(jī)訪問(wèn)的能力；
- 鏈表中的額外指針引用需要浪費(fèi)內(nèi)存；
鏈表有許多不足。鏈表的主要缺點(diǎn)在于訪問(wèn)單個(gè)元素的時(shí)間開(kāi)銷(xiāo)問(wèn)題；數(shù)組是隨時(shí)存取的，即存取數(shù)組中任一元素的時(shí)間開(kāi)銷(xiāo)為O(1)，而鏈表在最差情況下訪問(wèn)一個(gè)元素的開(kāi)銷(xiāo)為O(n)；數(shù)組在存取時(shí)間方面的另一個(gè)優(yōu)點(diǎn)是內(nèi)存的空間局部性，由于數(shù)組定義為連續(xù)的內(nèi)存塊，所以任何數(shù)組元素與其鄰居是物理相鄰的，這極大得益于現(xiàn)代CPU的緩存模式；
鏈表和數(shù)組的簡(jiǎn)單對(duì)比
- 數(shù)組最好用于索引有語(yǔ)意的情況，最大的優(yōu)點(diǎn)：支持快速查詢(xún)；
- 鏈表不適用于索引有語(yǔ)意的情況，最大的優(yōu)點(diǎn)：動(dòng)態(tài)；
實(shí)現(xiàn)自己的鏈表類(lèi)
public class LinkedList<E> {private class Node {public E e;public Node next;public Node(E e, Node next) {this.e = e;this.next = next;}public Node(E e) {this(e, null);}public Node() {this(null, null);}@Overridepublic String toString() {return e.toString();}}private Node dummyHead;private int size;public LinkedList() {dummyHead = new Node();size = 0;}// 獲取鏈表中的元素個(gè)數(shù)public int getSize() {return size;}// 返回鏈表是否為空public boolean isEmpty() {return size == 0;}// 在鏈表的index(0-based)位置添加新的元素e// 在鏈表中不是一個(gè)常用的操作，練習(xí)用：）public void add(int index, E e) {if (index < 0 || index > size)throw new IllegalArgumentException("Add failed. Illegal index.");Node prev = dummyHead;for (int i = 0; i < index; i++)prev = prev.next;prev.next = new Node(e, prev.next);size++;}// 在鏈表頭添加新的元素epublic void addFirst(E e) {add(0, e);}// 在鏈表末尾添加新的元素epublic void addLast(E e) {add(size, e);}// 獲得鏈表的第index(0-based)個(gè)位置的元素// 在鏈表中不是一個(gè)常用的操作，練習(xí)用：）public E get(int index) {if (index < 0 || index >= size)throw new IllegalArgumentException("Get failed. Illegal index.");Node cur = dummyHead.next;for (int i = 0; i < index; i++)cur = cur.next;return cur.e;}// 獲得鏈表的第一個(gè)元素public E getFirst() {return get(0);}// 獲得鏈表的最后一個(gè)元素public E getLast() {return get(size - 1);}// 修改鏈表的第index(0-based)個(gè)位置的元素為e// 在鏈表中不是一個(gè)常用的操作，練習(xí)用：）public void set(int index, E e) {if (index < 0 || index >= size)throw new IllegalArgumentException("Update failed. Illegal index.");Node cur = dummyHead.next;for (int i = 0; i < index; i++)cur = cur.next;cur.e = e;}// 查找鏈表中是否有元素epublic boolean contains(E e) {Node cur = dummyHead.next;while (cur != null) {if (cur.e.equals(e))return true;cur = cur.next;}return false;}// 從鏈表中刪除index(0-based)位置的元素, 返回刪除的元素// 在鏈表中不是一個(gè)常用的操作，練習(xí)用：）public E remove(int index) {if (index < 0 || index >= size)throw new IllegalArgumentException("Remove failed. Index is illegal.");// E ret = findNode(index).e; // 兩次遍歷Node prev = dummyHead;for (int i = 0; i < index; i++)prev = prev.next;Node retNode = prev.next;prev.next = retNode.next;retNode.next = null;size--;return retNode.e;}// 從鏈表中刪除第一個(gè)元素, 返回刪除的元素public E removeFirst() {return remove(0);}// 從鏈表中刪除最后一個(gè)元素, 返回刪除的元素public E removeLast() {return remove(size - 1);}// 從鏈表中刪除元素epublic void removeElement(E e) {Node prev = dummyHead;while (prev.next != null) {if (prev.next.e.equals(e))break;prev = prev.next;}if (prev.next != null) {Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;}}@Overridepublic String toString() {StringBuilder res = new StringBuilder();Node cur = dummyHead.next;while (cur != null) {res.append(cur + "->");cur = cur.next;}res.append("NULL");return res.toString();} }鏈表虛擬頭結(jié)點(diǎn)的作用
- 為了屏蔽掉鏈表頭結(jié)點(diǎn)的特殊性；
因?yàn)轭^結(jié)點(diǎn)是沒(méi)有前序結(jié)點(diǎn)的，所以我們不管是刪除還是增加操作都要對(duì)頭結(jié)點(diǎn)進(jìn)行單獨(dú)的判斷，為了我們編寫(xiě)邏輯的方便，引入了一個(gè)虛擬頭結(jié)點(diǎn)的概念；
簡(jiǎn)單復(fù)雜度分析
我們從鏈表的操作中可以很容易的看出，對(duì)于增刪改查這幾個(gè)操作的復(fù)雜度都是O(n)的，但是如果我們只是對(duì)鏈表頭進(jìn)行增/刪/查的操作的話，那么它的復(fù)雜度就是O(1)的，這里也可以看出來(lái)我們的鏈表適合干的事情了..
LeetCode相關(guān)題目參考
1.兩數(shù)之和
參考答案：
class Solution {public int[] twoSum(int[] numbers, int target) {int [] res = new int[2];if(numbers==null||numbers.length<2)return res;HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();for(int i = 0; i < numbers.length; i++){if(!map.containsKey(target-numbers[i])){map.put(numbers[i],i);}else{res[0]= map.get(target-numbers[i]);res[1]= i;break;}}return res;} }2.兩數(shù)相加
參考答案：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummyHead = new ListNode(0);ListNode p = l1, q = l2, curr = dummyHead;int carry = 0;while (p != null || q != null) {int x = (p != null) ? p.val : 0;int y = (q != null) ? q.val : 0;int sum = carry + x + y;carry = sum / 10;curr.next = new ListNode(sum % 10);curr = curr.next;if (p != null) p = p.next;if (q != null) q = q.next;}if (carry > 0) {curr.next = new ListNode(carry);}return dummyHead.next; }19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)（劍指Offer面試題22）
我的答案：（13ms）
public ListNode removeNthFromEnd(ListNode head, int n) {// 正確性判斷if (null == head || null == head.next) {return null;}int num = 0;// 定義一個(gè)虛擬頭結(jié)點(diǎn)方便遍歷鏈表ListNode dummyHead = new ListNode(-1);dummyHead.next = head;ListNode prev = dummyHead;// 一次遍歷找到鏈表的總數(shù)while (null != prev.next) {num++;prev = prev.next;}// 二次遍歷刪除對(duì)應(yīng)的節(jié)點(diǎn)prev = dummyHead;for (int i = 0; i < num - n; i++) {prev = prev.next;}// end for:找到了刪除節(jié)點(diǎn)的前序節(jié)點(diǎn)ListNode delNode = prev.next;prev.next = prev.next.next;delNode.next = null;// 返回頭結(jié)點(diǎn)return dummyHead.next; }我的答案2：（16ms）
public ListNode removeNthFromEnd(ListNode head, int n) {// 正確性判斷if (null == head || null == head.next) {return null;}HashMap<Integer, ListNode> map = new HashMap<>();// 定義一個(gè)虛擬頭結(jié)點(diǎn)方便遍歷鏈表ListNode dummyHead = new ListNode(-1);dummyHead.next = head;ListNode prev = dummyHead;map.put(0, dummyHead);// 一次遍歷，將序號(hào)與ListNode對(duì)應(yīng)存入map中for (int i = 1; null != prev.next; i++, prev = prev.next) {map.put(i, prev.next);}// 刪除對(duì)應(yīng)的節(jié)點(diǎn)int delNodeNum = map.size() - n;ListNode delNode = map.get(delNodeNum);prev = map.get(delNodeNum - 1);prev.next = prev.next.next;delNode.next = null;// help GC// 返回頭結(jié)點(diǎn)return dummyHead.next; }參考答案：（26ms）
public ListNode removeNthFromEnd(ListNode head, int n) {// 正確性判斷if (null == head || null == head.next) {return null;}// 定義虛擬頭結(jié)點(diǎn)方便遍歷ListNode dummyHead = new ListNode(-1);dummyHead.next = head;// 定義快慢兩個(gè)節(jié)點(diǎn)ListNode fast = dummyHead;ListNode slow = dummyHead;// 讓fast先跑到第n個(gè)位置for (int i = 0; i <= n; i++) {fast = fast.next;}// 再讓兩個(gè)一起移動(dòng)，當(dāng)fast為尾節(jié)點(diǎn)時(shí)slow的位置即刪除元素的位置while (null != fast) {fast = fast.next;slow = slow.next;}ListNode delNode = slow.next;slow.next = slow.next.next;delNode.next = null;// help GC.return dummyHead.next; }21.合并兩個(gè)有序鏈表（劍指Offer面試題25）
我的答案：（13ms）
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 正確性判斷if (null == l1) {return l2;}if (null == l2) {return l1;}// 定義一個(gè)虛擬頭結(jié)點(diǎn)方便遍歷ListNode dummyHead = new ListNode(-1);dummyHead.next = l1;ListNode pre = dummyHead;// 遍歷l1鏈表int len1 = 0;while (null != pre.next) {len1++;pre = pre.next;}int[] nums1 = new int[len1];// 保存l1鏈表的數(shù)據(jù)pre = dummyHead;for (int i = 0; i < len1; i++) {nums1[i] = pre.next.val;pre = pre.next;}// 遍歷l2鏈表int len2 = 0;dummyHead.next = l2;pre = dummyHead;while (null != pre.next) {len2++;pre = pre.next;}int[] nums2 = new int[len2];// 保存l2鏈表的數(shù)據(jù)pre = dummyHead;for (int i = 0; i < len2; i++) {nums2[i] = pre.next.val;pre = pre.next;}int[] nums = new int[len1 + len2];// 將兩個(gè)鏈表的數(shù)據(jù)整合并排序System.arraycopy(nums1, 0, nums, 0, len1);System.arraycopy(nums2, 0, nums, len1, len2);Arrays.sort(nums);// 拼接一個(gè)鏈表ListNode dummy = new ListNode(-1);pre = dummy;for (int i = 0; i < nums.length; i++) {ListNode node = new ListNode(nums[i]);pre.next = node;pre = pre.next;}return dummy.next; }參考答案：（15ms）
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}ListNode head = null;if (l1.val < l2.val) {head = l1;head.next = mergeTwoLists(l1.next, l2);} else {head = l2;head.next = mergeTwoLists(l1, l2.next);}return head; }74.搜索二維矩陣（劍指Offer面試題4）
參考答案：（8ms）
public boolean searchMatrix(int[][] matrix, int target) {// 正確性判斷if (null == matrix || 0 == matrix.length) {return false;}if (null == matrix[0] || 0 == matrix[0].length) {return false;}int row = matrix.length;int col = matrix[0].length;int start = 0, end = row * col - 1;while (start <= end) {int mid = start + (end - start) / 2;int number = matrix[mid / col][mid % col];if (number == target) {return true;} else if (number > target) {end = mid - 1;} else {start = mid + 1;}}return false; }141.環(huán)形鏈表
我的答案：（14ms）
public boolean hasCycle(ListNode head) {// 正確條件判斷if (null == head || null == head.next) {return false;}// 引入虛擬頭結(jié)點(diǎn)ListNode dummyHead = new ListNode(-1);dummyHead.next = head;HashMap<ListNode, Integer> map = new HashMap<>();ListNode prev = dummyHead;// 遍歷鏈表while (null != prev.next) {if (map.containsKey(prev.next)) {return true;} else {map.put(prev.next, prev.next.val);prev = prev.next;}}// 如果遍歷到了鏈表尾巴都沒(méi)找到則返回falsereturn false; }參考答案：（3ms）
public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){// move 2 stepsfast = fast.next.next;// move 1 stepslow = slow.next;if(fast == slow)return true;}return false; }147.對(duì)鏈表進(jìn)行插入排序
參考答案：（38ms）
public ListNode insertionSortList(ListNode head) {// 正確性判斷if (null == head || null == head.next) {return head;}// 定義一個(gè)新的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的作用是一個(gè)一個(gè)把head開(kāi)頭的鏈表插入到dummy開(kāi)頭的鏈表里L(fēng)istNode dummy = new ListNode(-1);// 類(lèi)似于冒泡排序法的遍歷整個(gè)鏈表while (null != head) {ListNode pre = dummy;while (null != pre.next && pre.next.val < head.val) {pre = pre.next;}ListNode temp = head.next;head.next = pre.next;pre.next = head;head = temp;}return dummy.next; }148.排序鏈表
我的答案：（829ms）
public ListNode sortList(ListNode head) {// 正確性判斷if (null == head || null == head.next) {return head;}// 引入虛擬頭結(jié)點(diǎn)方便遍歷ListNode dummyHead = new ListNode(-1);dummyHead.next = head;List<Integer> vals = new ArrayList<>();ListNode prev = dummyHead;// 遍歷一遍數(shù)組，將數(shù)據(jù)存入排好序存入vals集合中while (null != prev.next) {// 每一次都將val值插入到正確的地方int index = 0;for (int i = 0; i < vals.size(); i++) {if (prev.next.val >= vals.get(i)) {index = i + 1;}}vals.add(index, prev.next.val);prev = prev.next;}// 連接鏈表prev = dummyHead;for (int i = 0; i < vals.size(); i++) {ListNode node = new ListNode(vals.get(i));prev.next = node;prev = prev.next;}return dummyHead.next; }參考答案：（4ms）
public ListNode sortList(ListNode head) {// 正確性判斷if (null == head || null == head.next) {return head;}// 第一次遍歷：找到鏈表長(zhǎng)度int len = 0;ListNode cur = head;while (null != cur) {len++;cur = cur.next;}// 第二次遍歷：保存鏈表的值int[] nums = new int[len];cur = head;for (int i = 0; i < len; i++) {nums[i] = cur.val;cur = cur.next;}// 第三次遍歷：改變鏈表的值A(chǔ)rrays.sort(nums);cur = head;for (int i = 0; i < len; i++) {cur.val = nums[i];cur = cur.next;}return head; }這里想吐槽一下：因?yàn)樯厦娴乃惴ū闅v了三次鏈表，我想著使用ArrayList來(lái)少一次遍歷結(jié)果發(fā)現(xiàn)運(yùn)算速度達(dá)到了20ms左右..時(shí)間好像都花在了ArrayList轉(zhuǎn)數(shù)組這個(gè)操作上了...這或許就是傳說(shuō)中的負(fù)優(yōu)化吧...
203.刪除鏈表中的節(jié)點(diǎn)（劍指Offer面試題18）
參考答案：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode removeElements(ListNode head, int val) {// 定義一個(gè)虛擬頭結(jié)點(diǎn)ListNode dummyHead = new ListNode(-1);dummyHead.next = head;ListNode prev = dummyHead;while (prev.next != null) {if (prev.next.val == val) {prev.next = prev.next.next;} else {prev = prev.next;}}return dummyHead.next;} }206.反轉(zhuǎn)鏈表（劍指Offer面試題6、面試題24）
我的答案：（7ms）
public ListNode reverseList(ListNode head) {// 正確性判斷if (null == head || null == head.next) {return head;}// 定義一個(gè)虛擬頭結(jié)點(diǎn)ListNode dummyHead = new ListNode(-1);dummyHead.next = head;HashMap<Integer, ListNode> map = new HashMap<>();ListNode prev = dummyHead;// 存儲(chǔ)節(jié)點(diǎn)順序信息for (int i = 0; null != prev.next; i++) {map.put(i, prev.next);prev = prev.next;}int listSize = map.size();// 反轉(zhuǎn)鏈表for (int i = listSize - 1; i > 0; i--) {map.get(i).next = map.get(i - 1);}map.get(0).next = null;// 返回頭結(jié)點(diǎn)return map.get(listSize - 1); }參考答案：（0ms）
public ListNode reverseList(ListNode head) {ListNode pre = null;while (null != head) {ListNode temp = head;head = head.next;temp.next = pre;pre = temp;}return pre; }442.數(shù)組中重復(fù)的數(shù)據(jù)（劍指Offer面試題3）
我的答案：（56ms）
public List<Integer> findDuplicates(int[] nums) {List<Integer> result = new ArrayList<>();// 正確性判斷if (null == nums || 0 == nums.length) {return result;}// 創(chuàng)建一個(gè)HashMap，K值存位置，V值存數(shù)據(jù)HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {// 如果存在重復(fù)的V值那么則有重復(fù)的元素存在if (map.containsKey(nums[i])) {result.add(nums[i]);}map.put(nums[i], i);}return result; }參考答案：（14ms）
public List<Integer> findDuplicates(int[] nums) {List<Integer> res = new ArrayList<>();if (nums == null || nums.length == 0) return res;for (int i = 0; i < nums.length; i++) {int index = Math.abs(nums[i]) - 1;if (nums[index] > 0) nums[index] *= -1;else {res.add(index + 1);}}return res; }上面這個(gè)方法我DEBUG了一會(huì)兒終于搞懂了，如果有兩個(gè)重復(fù)的數(shù)字，那么nums[index]位置的數(shù)字一定是一個(gè)復(fù)數(shù)，但是如果這個(gè)index值超過(guò)了nums.length，就會(huì)報(bào)錯(cuò)啊..這個(gè)只能算一個(gè)巧解吧...
簡(jiǎn)單總結(jié)
刷題還是挺有成就感的，像這樣復(fù)習(xí)一遍下來(lái)感覺(jué)自己還是挺有收獲的，特別是在算法方面有了一些神奇的體驗(yàn)，然后呢?cái)?shù)據(jù)結(jié)構(gòu)這方面也通過(guò)刷題有了不一樣的理解和見(jiàn)解，就希望自己能抓緊點(diǎn)兒時(shí)間吧，加油；
歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處！
簡(jiǎn)書(shū)ID：@我沒(méi)有三顆心臟
github：wmyskxz
總結(jié)
以上是生活随笔為你收集整理的数据结构与算法(1)——数组与链表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 初学Java Web（2）——搭建Jav
- 下一篇： 数据结构与算法(2)——栈和队列