acm金牌有多難，ACM金牌選手算法講解《線性表》

2023-12-09 阅读 28 评论 0

摘要：導讀:????????哈嘍，大家好，我是編程熊，雙非逆襲選手，字節跳動、曠視科技前員工，ACM亞洲區域賽金牌，保研985研究生，分享算法與數據結構、計算機學習經驗，幫助大家進大廠~acm金牌有多難，關注下方公眾號，學習

導讀:

????????哈嘍，大家好，我是編程熊，雙非逆襲選手，字節跳動、曠視科技前員工，ACM亞洲區域賽金牌，保研985研究生，分享算法與數據結構、計算機學習經驗，幫助大家進大廠~

acm金牌有多難，

關注下方公眾號，學習硬核知識

線性表

LeetCode刷題過程中，常常用到的線性表主要包括以下四個重要的數據結構: 數組、鏈表、棧、隊列。

acm算法推薦入門書。下面將分別講解數組、鏈表、棧和隊列。

線性表概述

線性: 這里的線性是邏輯上的連續，而非物理存儲的連續。

存儲的數據: 線性表是一個有n個相同類型數據的有序序列。

數組array

介紹

線性表的逆置算法數據結構、數組是物理存儲連續的線性表，其常見的形式為 a[0]、a[1] ... a[n-1]，a[i-1] 是 a[i] 的前驅，a[i+1] 是 a[i] 的后繼。

基本操作

插入

插入元素，要將插入位置后的元素全部向后移動一位。

下圖以數組長度為6，數據為0、1、2、3、4、5，在位置3插入一個元素X舉例。

刪除

acm算法是什么意思，刪除元素，要講刪除位置后的元素全部向前移動一位。

下圖以數組長度為6，數據為0、1、2、3、4、5，刪除位置3上的元素X舉例。

反轉

翻轉數組，本質是將數組存儲的數據進行反轉。

下圖以數組長度為6，數據為0、1、2、3、4、5，反轉整個數組舉例。

例題

LeetCode 27. 移除元素

題意

刪除數組中所有等于 val 的元素，返回移除后數組的新長度。要求不使用額外的空間。

示例

輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]

題解

數組的刪除操作，但如何不使用額外的空間呢？因為刪除val后的數組的長度小于等于原數組的長度，因此可以一邊將不等于val的數組放入原數組中，同時判斷原數組的數是否等于val。

代碼

class?Solution?{public?int?removeElement(int[]?nums,?int?val)?{//?left?存當前nums數組中不等于val的數字數量int?left?=?0;?for?(int?right?=?0;?right?<?nums.length;?right++)?{if?(nums[right]?!=?val)?{nums[left]?=?nums[right];left++;}}return?left;}
}

習題推薦

LeetCode 35. 搜索插入位置

鏈表

介紹

鏈表的出現是為了解決數組插入、刪除帶來的線性開銷。

區別于數組，鏈表中的元素可以不連續存儲，每一個元素包含該 元素的數據 和 指向鏈表下一個節點的指針。

基本操作

插入

插入元素，要將插入元素前一個位置的指針指向插入元素本身，將插入元素的指針指向前一個位置。

刪除

刪除元素，要將刪除元素前一個元素的指針指向刪除元素后一個元素，代碼實現上需要將刪除元素指針指向的位置記錄下來。

下圖是以長度為5的鏈表，刪除位置3上的元素為例子。

翻轉

翻轉鏈表，可以一邊遍歷同時用一個臨時變量記錄當前元素的下一個元素的指針所指向的位置，然后再將當前元素的下一個元素的指針指向自己。

下圖是以長度為5的鏈表，翻轉鏈表為例子。

例題

1. LeetCode 206. 反轉鏈表

題意

給單鏈表的頭節點 head ，請反轉鏈表，并返回反轉后的鏈表。

示例

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

題解

按上述鏈表翻轉操作思路實現代碼。

代碼

public?ListNode?reverseList(ListNode?head)?{//?pre?存的是當前節點的上一個節點ListNode?prev?=?null;//?curr?存的是當前鏈表遍歷到節點ListNode?curr?=?head;while?(curr?!=?null)?{//?next?存的是當前節點下一個節點ListNode?next?=?curr.next;curr.next?=?prev;prev?=?curr;curr?=?next;}return?prev;
}

習題推薦

LeetCode237. 刪除鏈表中的節點
LeetCode 21. 合并兩個有序鏈表
LeetCode 160. 相交鏈表

棧和隊列

棧

棧被限定必須在棧頂進行插入和刪除操作，因此其特點為是后進先出。

下圖是棧的插入(入棧)、刪除(出棧)示意圖。

隊列

隊列被限定在隊頭進行刪除操作，隊尾進行插入操作，因此其特點為先進先出。

下圖是隊列的插入(入隊)、刪除(出隊)示意圖。

基本操作

棧和隊列的插入和刪除操作上圖已解釋。

例題

LeetCode ?155. 最小棧

題意設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的棧。

push(x) —— 將元素 x 推入棧中。
pop() —— 刪除棧頂的元素。
top() —— 獲取棧頂元素。
getMin() —— 檢索棧中的最小元素。

示例

輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]輸出：
[null,null,null,null,-3,null,0,-2]解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

題解

建一個輔助棧，輔助棧的棧頂表示原棧所有數字最小值，下面分別討論題目要求的四種操作，如何實現。

push(x): 若插入的數字小于等于輔助棧的棧頂元素，則這個數字在原棧是最小值(之一)，我們將其插入輔助棧中。
pop(): 若原棧刪除的數字等于輔助棧的棧頂元素，則這個數字在原棧是最小值(之一)，我們同時原棧和輔助棧的棧頂元素；反之，只刪除原棧棧頂元素。
top(): 返回原棧的棧頂元素。
getMin(): 返回輔助棧的棧頂元素。

代碼

class?MinStack?{public?Stack<Integer>?s,?min_s;public?MinStack()?{s?=?new?Stack<>();min_s=?new?Stack<>();}public?void?push(int?x)?{s.push(x);if(min_s.isEmpty()?||?x?<=?min_s.peek())min_s.push(x);}public?void?pop()?{if(s.pop().equals(min_s.peek()))min_s.pop();}public?int?top()?{return?s.peek();}public?int?getMin()?{return?min_s.peek();}
}