算法學習方法
- 堅持、刻意練習
- 練習缺陷、弱點地方
- 不舒服、枯燥是正常的
- LeetCode做題要考慮時間復雜度，盡量做到最優(yōu)解
- 經(jīng)常反饋，LeetCode每道題后面的solution和discuss都會有別人的解法，可以學習別人的優(yōu)秀方法。
常用的數(shù)據(jù)結構
- 數(shù)組
- 堆棧/隊列
- 優(yōu)先隊列
- 鏈表（單鏈表/雙鏈表）
- 哈希表
- 樹/二叉樹
- 二叉搜索樹
- 圖
時間及空間復雜度
主定理
數(shù)組和鏈表
數(shù)組是內存中一段連續(xù)的存儲區(qū)域 ，通過下標可以隨機訪問數(shù)組中的任意元素，所以查詢較快。而插入元素的話就需要先將插入位置后面的所有元素向后移動一位，然后再插入新元素，所以數(shù)組增刪慢。
鏈表在內存中不是連續(xù)的，每個元素除了自己的值之外還有一個指向下一個元素的指針。插入元素只需要移動指針的指向即可，但是查詢元素的話需要從頭開始移動指針，直到找到要查找的元素。
鏈表包括單鏈表和雙向鏈表。單鏈表,只有 next. 雙鏈表, 不僅有 next, 還有 previous.
數(shù)組隨機訪問某個元素的時間復雜度是O(1)。查找的話，如果無序數(shù)組就是o(n)，如果有序就可以用二分查找時間復雜度是 O(logn) 。增刪的時間復雜度是O(n) 。鏈表查詢的時間復雜度是O(n) ，增刪的時間復雜度是O(1)
1. 查找旋轉數(shù)組的最小數(shù)字
例如：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉。輸入一個遞增排序的數(shù)組的一個旋轉，輸出旋轉數(shù)組的最小元素。例如數(shù)組 {3，4，5，1，2} 為數(shù)組 {1，2，3，4，5} 的一個旋轉，該數(shù)組的最小值為 1
方法一：遍歷一遍數(shù)組，找到最小值后退出
public static int getTheMin(int nums[]) {
if (nums == null || nums.length == 0) {
throw new RuntimeException("input error!");
}
int result = nums[0];
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] < nums[i]) {
result = nums[i + 1];
break;
}
}
return result;
}
方法二：數(shù)組已經(jīng)是有序的，只是做了一個旋轉，所以我們可以考慮二分查找。
可以設定兩個下標 low 和 high，并設定 mid = (low + high)/2，我們自然就可以找到數(shù)組中間的元素 array[mid]，如果中間的元素位于前面的遞增數(shù)組，那么它應該大于或者等于 low 下標對應的元素，此時數(shù)組中最小的元素應該位于該元素的后面，我們可以把 low 下標指向該中間元素，這樣可以縮小查找的范圍。同樣，如果中間元素位于后面的遞增子數(shù)組，那么它應該小于或者等于 high 下標對應的元素。此時該數(shù)組中最小的元素應該位于該中間元素的前面。我們就可以把 high 下標更新到中位數(shù)的下標，移動之后的 high 下標對應的元素仍然在后面的遞增子數(shù)組中。不管是更新 low 還是 high，我們的查找范圍都會縮小為原來的一半，接下來我們再用更新的下標去重復新一輪的查找。直到最后兩個下標相鄰，即high - low = 1,也就是我們的循環(huán)結束條件。
public static int getTheMin(int nums[]) {
if (nums == null || nums.length == 0) {
throw new RuntimeException("input error!");
}
// 如果只有一個元素，直接返回
if (nums.length == 1)
return nums[0];
int result = nums[0];
int low = 0, high = nums.length - 1;
int mid;
// 確保 low 下標對應的值在左邊的遞增子數(shù)組，high 對應的值在右邊遞增子數(shù)組
while (nums[low] >= nums[high]) {
// 確保循環(huán)結束條件
if (high - low == 1) {
return nums[high];
}
// 取中間位置
mid = (low + high) / 2;
// 代表中間元素在左邊遞增子數(shù)組
if (nums[mid] >= nums[low]) {
low = mid;
} else {
high = mid;
}
}
return result;
}
2.調整數(shù)組順序使奇數(shù)位于偶數(shù)前面
例如：輸入一個整型數(shù)組，實現(xiàn)一個函數(shù)來調整該數(shù)組中的數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位于數(shù)組的后半部分，希望時間復雜度盡量小
方法一：從頭到尾掃描一遍數(shù)組，然后遇到奇數(shù)就移動到最前面
private static int[] orderArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 遇到奇數(shù)就放到最前面
if (Math.abs(arr[i]) % 2 == 1) {
int temp = arr[i];
// 先把 i 前面的都向后移動一個位置
for (int j = i; j > 0; j--) {
arr[j] = arr[j - 1];
}
arr[0] = temp;
}
}
return arr;
}
方法二：我們只需要維護兩個下標值，讓一個下標值從前往后遍歷，另外一個下標值從后往前遍歷，當發(fā)現(xiàn)第一個下標值對應到偶數(shù)，第二個下標值對應到奇數(shù)的時候，我們就直接對調兩個值。直到第一個下標到了第二個下標的后面的時候退出循環(huán)。
private static int[] orderArray(int[] arr) {
int odd = 0, even = arr.length - 1;
// 循環(huán)結束條件為 odd >= even
while (odd < even) {
// 第一個下標為偶數(shù)的時候停止
while (odd < even && Math.abs(arr[odd]) % 2 != 0) {
odd++;
}
// 第二個下標為奇數(shù)的時候停止
while (odd < even && Math.abs(arr[even]) % 2 == 0) {
even--;
}
// 找到后對調兩個值
int temp = arr[odd];
arr[odd] = arr[even];
arr[even] = temp;
}
return arr;
}
3.反轉一個單鏈表（LeetCode - 206）
例如：
input: 1 --> 2 --> 3 --> 4 output: 4 --> 3 --> 2 --> 1
方法一：迭代
在遍歷列表時，將當前節(jié)點的 next 指針改為指向前一個元素。由于節(jié)點沒有引用其上一個節(jié)點，因此必須事先存儲其前一個元素。在更改引用之前，還需要另一個指針來存儲下一個節(jié)點。最后返回新的頭引用。
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
- 時間復雜度：O(n)
- 空間復雜度：O(1)
方法二：遞歸
遞歸版本關鍵在于反向工作。假設列表的其余部分已經(jīng)被反轉，現(xiàn)在該如何反轉它前面的部分？
若從節(jié)點 k+1到 m 已經(jīng)被反轉，而我們正處于k。我們希望 k+1的下一個節(jié)點next指向k 。所以，
k.next.next = k。要注意的是第一個節(jié)點頭結點head的下一個必須指向 ? 。如果忽略了這一點，你的鏈表中可能會產(chǎn)生循環(huán)。
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
- 假設 n 是列表的長度，那么時間復雜度為 O(n)
- 空間復雜度：O(n) 由于使用遞歸，將會使用隱式棧空間。遞歸深度可能會達到 n 層。
4.交換鏈表相鄰元素（LeetCode - 24）
例如：對于給定鏈表中的元素，每相鄰的兩個元素互相加換。如果元素個數(shù)是奇數(shù)個，則最后一個元素就不用交換了。
input: 1 --> 2 --> 3 --> 4 output: 2 --> 1 --> 4 --> 3
input: 1 --> 2 --> 3 --> 4 --> 5 output: 2 --> 1 --> 4 --> 3 --> 5
遞歸解法：
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
非遞歸解法：
public ListNode swapPairs(ListNode head) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode temp = pre;
while(temp.next != null && temp.next.next != null) {
ListNode start = temp.next;
ListNode end = temp.next.next;
temp.next = end;
start.next = end.next;
end.next = start;
temp = start;
}
return pre.next;
}
5.判斷一個鏈表是否有環(huán)（LeetCode -141）
方法一：哈希表
思路:可以通過檢查一個結點此前是否被訪問過來判斷鏈表是否為環(huán)形鏈表。我們遍歷所有結點并在哈希表中存儲每個結點的引用（或內存地址）。如果當前結點為空結點 null（即已檢測到鏈表尾部的下一個結點），那么我們已經(jīng)遍歷完整個鏈表，并且該鏈表不是環(huán)形鏈表。如果當前結點的引用已經(jīng)存在于哈希表中，那么返回 true，表示該鏈表為環(huán)形鏈表。
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
- 時間復雜度為 O(n)
- 空間復雜度為 O(n)
方法二：龜兔賽跑法
思路：如果鏈表有環(huán)的話，那么和兩個運動員在環(huán)形跑道上賽跑是一個道理。如果兩人速度不同，那么他們最終會相遇。所以，我們可以使用具有 不同速度 的快、慢兩個指針遍歷鏈表，空間復雜度可以被降低至 O(1)。慢指針每次移動一步，而快指針每次移動兩步。如果列表中不存在環(huán)，最終快指針將會最先到達尾部，此時我們可以返回 false
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode quick = head.next;
while (slow != quick) {
if (quick == null || quick.next == null) {
return false;
}
slow = slow.next;
quick = quick.next.next;
}
return true;
}
- 時間復雜度為 O(n)
- 空間復雜度為 O(1)
