導讀:
????????哈嘍,大家好,我是編程熊,雙非逆襲選手,字節跳動、曠視科技前員工,ACM亞洲區域賽金牌,保研985研究生,分享算法與數據結構、計算機學習經驗,幫助大家進大廠~
acm金牌有多難,
關注下方公眾號,學習硬核知識
LeetCode刷題過程中,常常用到的線性表主要包括以下四個重要的數據結構: 數組、鏈表、棧、隊列。
acm算法推薦入門書。下面將分別講解數組、鏈表、棧和隊列。
線性: 這里的線性是邏輯上的連續,而非物理存儲的連續。
存儲的數據: 線性表是一個有n
個相同類型數據的有序序列。
線性表的逆置算法數據結構、數組是物理存儲連續的線性表,其常見的形式為 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
,反轉整個數組舉例。
題意
刪除數組中所有等于 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的鏈表,翻轉鏈表為例子。
題意
給單鏈表的頭節點 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. 相交鏈表
棧被限定必須在棧頂進行插入和刪除操作,因此其特點為是后進先出。
下圖是棧的插入(入棧)、刪除(出棧)示意圖。
隊列被限定在隊頭進行刪除操作,隊尾進行插入操作,因此其特點為先進先出。
下圖是隊列的插入(入隊)、刪除(出隊)示意圖。
棧和隊列的插入和刪除操作上圖已解釋。
題意設計一個支持 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();}
}
LeetCode 20. 有效的括號
---END---
你好,我是編程熊,本科畢業于雙非學校,校招時拿下字節跳動SP、曠視科技SP,也拿過ACM亞洲區域賽金牌,最終神奇保研985的研究生。
希望分享的知識和人生經驗可以幫助到你。
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态