色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

騰訊常考的十道算法題

算法與數(shù)據(jù)結(jié)構(gòu) ? 來源:撿田螺的小男孩 ? 作者:算法與數(shù)據(jù)結(jié)構(gòu) ? 2022-03-28 10:25 ? 次閱讀

前言

大家好,我是撿田螺的小男孩。收集了騰訊常考的十道算法題(真題)。在金三銀四,希望對大家有幫助呀。

  1. 重排鏈表
  2. 最長遞增子序列
  3. 環(huán)形鏈表
  4. 反轉(zhuǎn)鏈表
  5. 最長回文子串
  6. 全排列
  7. LRU 緩存
  8. 合并K個升序鏈表
  9. 無重復(fù)字符的最長子串
  10. 刪除鏈表的倒數(shù)第 N 個結(jié)點

1. 重排鏈表

給定一個單鏈表 L 的頭節(jié)點 head ,單鏈表 L 表示為:

L0→L1→…→Ln-1→Ln

請將其重新排列后變?yōu)椋?/span>

L0→Ln→L1→Ln-1→L2→Ln-2→…

輸入:

head=[1,2,3,4]

輸出:

[1,4,2,3]

思路:

如果是數(shù)組就好了,哈哈,因為數(shù)組可以直接通過下標訪問,很容易就可以解答這道題了。但是這是鏈表。鏈表不支持下標訪問,我們沒辦法隨機訪問到鏈表任意位置的元素,怎么辦呢?

我們可以先遍歷一下,用數(shù)組把鏈表的元素按順序存儲起來呀,然后就可以把它當做數(shù)組這么訪問來用了對吧,最后重建下鏈表即可啦。

ArrayList的底層就是數(shù)組,我們先用它存儲鏈表就好,如下:

Listlist=newArrayList();
ListNodenode=head;
while(node!=null){
list.add(node);
node=node.next;
}

有了一個數(shù)組結(jié)構(gòu)的鏈表后,如何重建鏈表呢?回頭多看示例兩眼,很容易就發(fā)小規(guī)律啦:先排第1個,再排倒數(shù)第1個,接著排第2個,緊接著倒數(shù)第2個。顯然這個規(guī)律很明顯,代碼也比較好實現(xiàn):

inti=0;
intj=list.size()-1;
while(iif(i==j){
break;
}
list.get(j).next=list.get(i);
j--;
}
//大家畫個圖就很清晰知道為什么需要這行了,哈哈
list.get(i).next=null;

完整實現(xiàn)代碼如下:

classSolution{
publicvoidreorderList(ListNodehead){
if(head==null){
return;
}
Listlist=newArrayList();
ListNodenode=head;
while(node!=null){
list.add(node);
node=node.next;
}
inti=0,j=list.size()-1;
while(iif(i==j){
break;
}
list.get(j).next=list.get(i);
j--;
}
list.get(i).next=null;
}
}

2. 最長遞增子序列

給你一個整數(shù)數(shù)組 nums ,找到其中最長嚴格遞增子序列的長度。

實例1:

輸入:nums =[10,9,2,5,3,7,101,18]
輸出:4
解釋:最長遞增子序列是[2,3,7,101],因此長度為 4 。

實例2:

輸入:nums =[0,1,0,3,2,3]
輸出:4

思路:

這道題是求最值問題,可以使用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的解題整體思路就是:

  1. 窮舉分析
  2. 分析找規(guī)律,拆分子問題
  3. 確定邊界
  4. 確定最優(yōu)子結(jié)構(gòu)
  5. 寫出狀態(tài)轉(zhuǎn)移方程

2.1 窮舉分析

動態(tài)規(guī)劃的核心思想包括拆分子問題,記住過往,減少重復(fù)計算。所以我們在思考原問題:數(shù)組num[i]的最長遞增子序列長度時,可以思考下相關(guān)子問題,比如原問題是否跟子問題num[i-1]的最長遞增子序列長度有關(guān)呢?

自底向上的窮舉過程:

  • 當nums只有一個元素10時,最長遞增子序列是[10],長度是1.
  • 當nums需要加入一個元素9時,最長遞增子序列是[10]或者[9],長度是1。
  • 當nums再加入一個元素2時,最長遞增子序列是[10]或者[9]或者[2],長度是1。
  • 當nums再加入一個元素5時,最長遞增子序列是[2,5],長度是2。
  • 當nums再加入一個元素3時,最長遞增子序列是[2,5]或者[2,3],長度是2。
  • 當nums再加入一個元素7時,,最長遞增子序列是[2,5,7]或者[2,3,7],長度是3。
  • 當nums再加入一個元素101時,最長遞增子序列是[2,5,7,101]或者[2,3,7,101],長度是4。
  • 當nums再加入一個元素18時,最長遞增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],長度是4。
  • 當nums再加入一個元素7時,最長遞增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],長度是4.

2.2 分析找規(guī)律,拆分子問題

通過上面分析,我們可以發(fā)現(xiàn)一個規(guī)律:

如果新加入一個元素nums[i], 最長遞增子序列要么是以nums[i]結(jié)尾的遞增子序列,要么就是nums[i-1]的最長遞增子序列。看到這個,是不是很開心,nums[i]的最長遞增子序列已經(jīng)跟子問題nums[i-1]的最長遞增子序列有關(guān)聯(lián)了。

原問題數(shù)組nums[i]的最長遞增子序列 = 子問題數(shù)組nums[i-1]的最長遞增子序列/nums[i]結(jié)尾的最長遞增子序列

是不是感覺成功了一半呢?但是如何把nums[i]結(jié)尾的遞增子序列也轉(zhuǎn)化為對應(yīng)的子問題呢?要是nums[i]結(jié)尾的遞增子序列也跟nums[i-1]的最長遞增子序列有關(guān)就好了。又或者nums[i]結(jié)尾的最長遞增子序列,跟前面子問題num[j](0=結(jié)尾的最長遞增子序列有關(guān)就好了,帶著這個想法,我們又回頭看看窮舉的過程:

2e7ef6ec-ae3c-11ec-aa7f-dac502259ad0.png

nums[i]的最長遞增子序列,不就是從以數(shù)組num[i]每個元素結(jié)尾的最長子序列集合,取元素最多(也就是長度最長)那個嘛,所以原問題,我們轉(zhuǎn)化成求出以數(shù)組nums每個元素結(jié)尾的最長子序列集合,再取最大值嘛。哈哈,想到這,我們就可以用dp[i]表示以num[i]這個數(shù)結(jié)尾的最長遞增子序列的長度啦,然后再來看看其中的規(guī)律:

2e98d6ca-ae3c-11ec-aa7f-dac502259ad0.png

其實,nums[i]結(jié)尾的自增子序列,只要找到比nums[i]小的子序列,加上nums[i]就可以啦。顯然,可能形成多種新的子序列,我們選最長那個,就是dp[i]的值啦

  • nums[3]=5,以5結(jié)尾的最長子序列就是[2,5],因為從數(shù)組下標0到3遍歷,只找到了子序列[2]比5小,所以就是[2]+[5]啦,即dp[4]=2
  • nums[4]=3,以3結(jié)尾的最長子序列就是[2,3],因為從數(shù)組下標0到4遍歷,只找到了子序列[2]比3小,所以就是[2]+[3]啦,即dp[4]=2
  • nums[5]=7,以7結(jié)尾的最長子序列就是[2,5,7]和[2,3,7],因為從數(shù)組下標0到5遍歷,找到2,5和3都比7小,所以就有[2,7],[5,7],[3,7],[2,5,7]和[2,3,7]這些子序列,最長子序列就是[2,5,7]和[2,3,7],它倆不就是以5結(jié)尾和3結(jié)尾的最長遞增子序列+[7]來的嘛!所以,dp[5]=3 =dp[3]+1=dp[4]+1。

很顯然有這個規(guī)律:一個以nums[i]結(jié)尾的數(shù)組nums

  • 如果存在j屬于區(qū)間[0,i-1],并且num[i]>num[j]的話,則有:dp(i) =max(dp(j))+1。

2.3 確定邊界

當nums數(shù)組只有一個元素時,最長遞增子序列的長度dp(1)=1,當nums數(shù)組有兩個元素時,dp(2) =2或者1, 因此邊界就是dp(1)=1。

2.4 確定最優(yōu)子結(jié)構(gòu)

從2.2 窮舉分析找規(guī)律,我們可以得出,以下的最優(yōu)結(jié)構(gòu):

dp(i)=max(dp(j))+1,存在j屬于區(qū)間[0,i-1],并且num[i]>num[j]。

max(dp(j)) 就是最優(yōu)子結(jié)構(gòu)。

2.5 寫出狀態(tài)轉(zhuǎn)移方程

通過前面分析,我們就可以得出狀態(tài)轉(zhuǎn)移方程啦:

2ea9361e-ae3c-11ec-aa7f-dac502259ad0.png

所以數(shù)組nums[i]的最長遞增子序列就是:

最長遞增子序列=max(dp[i])

完整代碼實現(xiàn)如下

classSolution{
publicintlengthOfLIS(int[]nums){
if(nums.length==0){
return0;
}
int[]dp=newint[nums.length];
//初始化就是邊界情況
dp[0]=1;
intmaxans=1;
//自底向上遍歷
for(inti=1;ifor(intj=0;jif(nums[j]returnmaxans;
}
}

3. 環(huán)形鏈表

給定一個鏈表的頭節(jié)點head ,返回鏈表開始入環(huán)的第一個節(jié)點。如果鏈表無環(huán),則返回 null。

實例:

2ebe1e80-ae3c-11ec-aa7f-dac502259ad0.png
輸入:head =[3,2,0,-4], pos = 1
輸出:返回索引為 1 的鏈表節(jié)點
解釋:鏈表中有一個環(huán),其尾部連接到第二個節(jié)點。

如果判斷鏈表是否有環(huán),我們可以使用快慢指針,快指針是慢指針速度的兩倍,當兩個指針相遇時,即表示有環(huán)。

booleanhasCycle(ListNodehead){

ListNodeslow=head;
ListNodefast=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
returntrue;
}
}
returnfalse;
}

我們可以很容易就判斷有環(huán),但是如何返回入環(huán)的第一個節(jié)點呢?我們來畫個圖分析一波:

2ecc87b8-ae3c-11ec-aa7f-dac502259ad0.png

假設(shè)起點為A,入環(huán)點為B,快慢指針相遇點為C,慢指針走到相遇點為k步,B到C的距離為m。設(shè)環(huán)型周長為X。因為快指針速度是慢指針的2倍。則有:

K-m+X+m=2K=快指針走的舉例

所以周長X = K。相遇后,快指針到繼續(xù)往前走,走到入環(huán)點B,剛好距離是X-m = K-m。而起點到B節(jié)點,距離也是K-m。因此,快慢指針相遇后,慢指針回到起點,這時候快慢指針一樣的速度走,相遇時,就是入環(huán)點啦,是不是無巧不成書呀,哈哈哈。

完整代碼如下:

publicclassSolution{
publicListNodedetectCycle(ListNodehead){
if(head==null){
returnnull;
}
ListNodefast=head;
ListNodeslow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
//快慢指針相等表示有環(huán)
if(slow==fast){
//回到起點一起相同速度走
while(head!=fast){
head=head.next;
fast=fast.next;
}
returnhead;
}

}
returnnull;
}
}

4. 反轉(zhuǎn)鏈表

給你單鏈表的頭節(jié)點 head ,請你反轉(zhuǎn)鏈表,并返回反轉(zhuǎn)后的鏈表。

2eddbb14-ae3c-11ec-aa7f-dac502259ad0.png
輸入:head =[1,2,3,4,5]
輸出:[5,4,3,2,1]

完整代碼如下:

classSolution{
publicListNodereverseList(ListNodehead){

ListNodeprev=null;
ListNodenext=head;
ListNodecurr=head;

while(curr!=null){
next=curr.next;
curr.next=prev;
prev=curr;
curr=next;
}

returnprev;
}
}

之前圖解過這道題,大家可以看下哈:

看一遍就理解,圖解單鏈表反轉(zhuǎn)

5. 最長回文子串

給你一個字符串 s,找到 s 中最長的回文子串。

實例1:

輸入:s ="babad"
輸出:"bab"
解釋:"aba"同樣是符合題意的答案。

這道題可以使用中心擴展法實現(xiàn),從中間開始向兩邊擴散來判斷回文串。

for0<=?i?

但是回文串可能是長度可能是奇數(shù),也可能是偶數(shù),因此需要加多一步:

for0<=?i?

完整代碼如下:

classSolution{
publicStringlongestPalindrome(Strings){

if(s==null||s.length()<2){
?????????????returns;
}

Stringresult="";
for(inti=0;ir2.length()?r1:r2;
result=tempMax.length()>result.length()?tempMax:result;

}
returnresult;

}

privateStringsubLongestPalindrome(Strings,intl,intr){
while(l>=0&&rreturns.substring(l+1,r);
}
}

6.全排列

給定一個不含重復(fù)數(shù)字的數(shù)組 nums ,返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1:

輸入:nums =[1,2,3]
輸出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

輸入:nums =[0,1]
輸出:[[0,1],[1,0]]

這道題可以用回溯算法解決,完整代碼如下:

classSolution{
//全排列,即所有路徑集合
List>allPath=newLinkedList<>();

publicList>permute(int[]nums){
//當前路徑,入口路徑,path是空的
Listpath=newLinkedList<>();
//遞歸函數(shù)入口,可做選擇是nums數(shù)組
backTrace(nums,path);
returnallPath;
}

publicvoidbackTrace(int[]nums,Listpath){
//已走路徑path的數(shù)組長度等于nums的長度,表示走到葉子節(jié)點,所以加到全排列集合
if(nums.length==path.size()){
allPath.add(newLinkedList(path));
return;
}

for(inti=0;iif(path.contains(nums[i])){
continue;
}
//做選擇,加到當前路徑
path.add(nums[i]);
//遞歸,進入下一層的決策
backTrace(nums,path);
//取消選擇
path.remove(path.size()-1);
}
}
}

大家可以看下之前我寫的這篇回溯文章哈,有回溯算法的框架套用。

面試必備:回溯算法詳解

7. LRU 緩存

請你設(shè)計并實現(xiàn)一個滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結(jié)構(gòu)。

實現(xiàn) LRUCache 類:

  • LRUCache(int capacity) 以 正整數(shù) 作為容量capacity 初始化 LRU 緩存
  • int get(int key) 如果關(guān)鍵字 key 存在于緩存中,則返回關(guān)鍵字的值,否則返回 -1 。
  • void put(int key, int value)如果關(guān)鍵字 key 已經(jīng)存在,則變更其數(shù)據(jù)值 value ;如果不存在,則向緩存中插入該組 key-value 。如果插入操作導(dǎo)致關(guān)鍵字數(shù)量超過 capacity ,則應(yīng)該 逐出 最久未使用的關(guān)鍵字。

函數(shù) get 和 put 必須以O(1)的平均時間復(fù)雜度運行。

示例:

輸入
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
輸出
[null,null,null,1,null,-1,null,-1,3,4]

解釋
LRUCachelRUCache=newLRUCache(2);
lRUCache.put(1,1);//緩存是{1=1}
lRUCache.put(2,2);//緩存是{1=1,2=2}
lRUCache.get(1);//返回1
lRUCache.put(3,3);//該操作會使得關(guān)鍵字2作廢,緩存是{1=1,3=3}
lRUCache.get(2);//返回-1(未找到)
lRUCache.put(4,4);//該操作會使得關(guān)鍵字1作廢,緩存是{4=4,3=3}
lRUCache.get(1);//返回-1(未找到)
lRUCache.get(3);//返回3
lRUCache.get(4);//返回4

這道題,出現(xiàn)的頻率還是挺高的,很多小伙伴在面試時,都反饋自己遇到過原題

LRU,Least Recently Used,即最近使用過的數(shù)據(jù)是有用的,可以使用雙鏈表+Hashmap解答,雙鏈表用于存儲LRUCache的數(shù)據(jù),Hashmap實現(xiàn)O(1)的平均時間復(fù)雜度。

2ef0be4e-ae3c-11ec-aa7f-dac502259ad0.png
  • 每次從鏈表尾部添加元素,靠尾的元素就是最近使用過
  • 某個key可以通過哈希表快速定位到節(jié)點。

對于雙鏈表,需要做哪些事呢。

  • 首先是鏈表初始化,為了方便處理i,虛擬一個頭節(jié)點和尾結(jié)點。
  • 添加元素時,放到鏈表的尾部,表示該元素最近使用過
  • 刪除雙向鏈表的某個節(jié)點
  • 刪除并返回頭節(jié)點,表示刪除最久未使用的元素
  • 返回鏈表當前長度

LRU緩存有哪些方法

  • 構(gòu)造函數(shù)初始化方法
  • get和put方法
  • makeRecently 設(shè)置某個元素最近使用過的方法,哈希表已經(jīng)有該元素
  • addRecently 添加最近使用過的元素,同時更新map
  • deleteKey 刪除某個key對應(yīng)的元素,同時刪除map上的節(jié)點
  • removeLeastRecently 刪除最久未使用的元素

完整代碼如下:

classNode{

intkey,val;
Nodenext,prev;
publicNode(intkey,intval){
this.key=key;
this.val=val;
}
}

classDoubleList{
//虛擬出頭節(jié)點和尾結(jié)點
privateNodehead,tail;
privateintsize;

//初始化雙鏈表
publicDoubleList(){
//虛擬頭結(jié)點
head=newNode(0,0);
//虛擬頭結(jié)點
tail=newNode(0,0);
head.next=tail;
tail.prev=head;
size=0;
}

//要加到鏈表尾部,且越靠近鏈表尾部,越表示最近使用過
publicvoidaddLast(Nodex){
//比如當前鏈表為:head <-> 1 <-> tail,加入結(jié)點x = 2
x.prev=tail.prev;
//完成結(jié)點2指向兩端的箭頭head<->1<-?2?->tail;此時tail.pre=結(jié)點1還未斷開
x.next=tail;
//head<->1<->2->tail;
tail.prev.next=x;
//head<->1<->2<->tail;
tail.prev=x;
//更新鏈表長度
size++;
}

//刪除指定結(jié)點
publicvoidremove(Nodex){
x.prev.next=x.next;
x.next.prev=x.prev;
size--;
}

//刪除并返回頭結(jié)點
publicNoderemoveHead(){
if(head.next==tail){
returnnull;
}
Nodefirst=head.next;
//size在remove中更新了
remove(first);
//用作在哈希表中移除最久未使用的數(shù)據(jù)值
returnfirst;
}

//獲取鏈表長度
publicintgetSize(){
returnsize;
}
}

publicclassLRUCache{

privateMapmap;
privateDoubleListdoubleList;
privateintcap;

publicLRUCache(intcapacity){
this.map=newHashMap<>();
this.doubleList=newDoubleList();
this.cap=capacity;
}

publicintget(intkey){
if(map.containsKey(key)){
//先將key標記為最近使用,再返回value
makeRecently(key);
returnmap.get(key).val;
}else{
return-1;
}
}

publicvoidput(intkey,intvalue){
if(map.containsKey(key)){
deleteKey(key);//從原map中移除該key
addRecently(key,value);//更新最近使用
return;
}

intsize=doubleList.getSize();
if(size==cap){//說明需要移除最久未使用的元素了
removeLeastRecently();
}
addRecently(key,value);//添加新的元素進來
}


publicvoidmakeRecently(intkey){//將某個key標記為最近使用的元素(map中已存在的)
Nodex=map.get(key);
doubleList.remove(x);//先從雙鏈表刪除
doubleList.addLast(x);//再添加到鏈表末尾,因為尾部是最近使用過的元素
}

publicvoidaddRecently(intkey,intvalue){//添加最近使用過的元素
Nodex=newNode(key,value);
doubleList.addLast(x);
map.put(key,x);//更新map
}

publicvoiddeleteKey(intkey){
Nodex=map.get(key);
map.remove(key);
doubleList.remove(x);//在map中和cache中同時刪除
}

//刪除最久未使用的元素
publicvoidremoveLeastRecently(){
//最久未使用的一定在鏈表頭部
NodeoldNode=doubleList.removeHead();
intoldKey=oldNode.key;
map.remove(oldKey);
}
}



8. 合并K個升序鏈表

給你一個鏈表數(shù)組,每個鏈表都已經(jīng)按升序排列。請你將所有鏈表合并到一個升序鏈表中,返回合并后的鏈表。

示例 1:

輸入:lists =[[1,4,5],[1,3,4],[2,6]]
輸出:[1,1,2,3,4,4,5,6]
解釋:鏈表數(shù)組如下:
[
1->4->5,
1->3->4,
2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6

合并兩個有序鏈表,是比較簡單的,相信大家都會做。那么如何合并K個有序鏈表呢?其實道理是一樣的,我們可以借用優(yōu)先級隊列找出最小節(jié)點,完整代碼如下:

classSolution{


publicListNodemergeKLists(ListNode[]lists){

if(lists.length==0){
returnnull;
}
//虛擬節(jié)點
ListNodehead=newListNode(0);
ListNodetail=head;
//優(yōu)先隊列
PriorityQueuequeue=newPriorityQueue<>(lists.length,(a,b)->(a.val-b.val));

//將K個鏈表頭節(jié)點合并最小堆
for(ListNodenode:lists){
if(node!=null){
queue.add(node);
}
}

while(!queue.isEmpty()){
//獲取最小節(jié)點,放到結(jié)果鏈表中
ListNodenode=queue.poll();
tail.next=node;

if(node.next!=null){
queue.add(node.next);
}
//指針鏈表一直往前
tail=tail.next;
}
returnhead.next;
}
}

9. 無重復(fù)字符的最長子串

給定一個字符串 s ,請你找出其中不含有重復(fù)字符的 最長子串 的長度。

示例 1:

輸入:s="abcabcbb"
輸出:3
解釋:因為無重復(fù)字符的最長子串是"abc",所以其長度為 3。

示例 2:

輸入:s="bbbbb"
輸出:1
解釋:因為無重復(fù)字符的最長子串是"b",所以其長度為 1。

這道題可以使用滑動窗口來實現(xiàn)。滑動窗口就是維護一個窗口,不斷滑動,然后更新答案。

滑動窗口的大致邏輯框架,偽代碼如下:

intleft=0,right=0;
while(rightwhile(windowneedsshrink){
//縮小窗口
window.remove(s[left]);
left++;
}
}

解法流程如下:

  • 首先呢,就是獲取原字符串的長度。
  • 接著維護一個窗口(數(shù)組、哈希、隊列)
  • 窗口一步一步向右擴展
  • 窗口在向右擴展滑動過程,需要判斷左邊是否需要縮減
  • 最后比較更新答案

完整代碼如下:

intlengthOfLongestSubstring(Strings){
//獲取原字符串的長度
intlen=s.length();
//維護一個哈希集合的窗口
Setwindows=newHashSet<>();
intleft=0,right=0;
intres=0;

while(rightwhile(windows.contains(c)){
windows.remove(s.charAt(left));
left++;
}
windows.add(c);
//比較更新答案
res=Math.max(res,windows.size());
}
returnres;
}

之前寫過一篇滑動窗口解析,大家有興趣可以看下哈:

leetcode必備算法:聊聊滑動窗口

10.刪除鏈表的倒數(shù)第 N 個結(jié)點

給你一個鏈表,刪除鏈表的倒數(shù)第 n 個結(jié)點,并且返回鏈表的頭結(jié)點。

2f02740e-ae3c-11ec-aa7f-dac502259ad0.png

示例 :

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

這道題可以使用雙指針解決。既然我們要找到倒數(shù)第n個節(jié)點,我們可以使用兩個指針first 和 second同時對鏈表進行遍歷,并且first 比second超前n個節(jié)點。當first遍歷到鏈表的末尾時,second就恰好處于倒數(shù)第n個節(jié)點。

classSolution{
publicListNoderemoveNthFromEnd(ListNodehead,intn){
ListNodedummy=newListNode(0,head);
ListNodefirst=head;
ListNodesecond=dummy;
//first比second先走n個節(jié)點
for(inti=0;iwhile(first!=null){
first=first.next;
second=second.next;
}
//刪除節(jié)點
second.next=second.next.next;
ListNodeans=dummy.next;
returnans;
}
}

審核編輯 :李倩


聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學習之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 算法
    +關(guān)注

    關(guān)注

    23

    文章

    4608

    瀏覽量

    92844
  • 代碼
    +關(guān)注

    關(guān)注

    30

    文章

    4780

    瀏覽量

    68530
  • 數(shù)組
    +關(guān)注

    關(guān)注

    1

    文章

    417

    瀏覽量

    25939

原文標題:十道騰訊算法真題解析!

文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。

收藏 人收藏

    評論

    相關(guān)推薦

    嵌入式Linux內(nèi)核開發(fā)必須了解的三十道

    嵌入式系統(tǒng)Linux內(nèi)核開發(fā)工程師必須掌握的三十道 linux內(nèi)核工程師需要知道的30個問題,看看你能回答出多少個。
    發(fā)表于 04-22 08:22 ?2728次閱讀
    嵌入式Linux內(nèi)核開發(fā)必須了解的三<b class='flag-5'>十道</b><b class='flag-5'>題</b>

    單片機8031三:三、四、五。一10元

    單片機8031三:三、四、五。一10元,直接發(fā)我qq840921270 ,會給第一個采用的人直接發(fā)支付寶,決不食言,食言剁屌!求助大神,小弟謝過了
    發(fā)表于 04-16 17:02

    可以大體看出你C語言水平的十道

    可以大體看出你C語言水平的十道 各位,今天給大家搜集了10比較好的面試題,涉及了指針、運算、結(jié)構(gòu)體、函數(shù)、內(nèi)存,應(yīng)該來說比較全面了,有興趣的做一下檢測一下自己的水平吧! 1.strcpy
    發(fā)表于 04-03 16:00

    的寄存器有哪些?

    計算機由哪幾部分組成?的寄存器有哪些?
    發(fā)表于 10-08 06:04

    PCB生產(chǎn)工藝 | 第十道主流程之電測

    如圖,第十道主流程為電測。電測的目的:電測又叫電氣性能測試、功能測試或開短路測試等,主要是對PCB的網(wǎng)絡(luò)通過測試治具或測試針接觸網(wǎng)絡(luò)的測試點位進行開短路檢測,將壞板挑選出來。是PCB生產(chǎn)過程中的一
    發(fā)表于 03-30 18:19

    基于程序設(shè)計主觀智能閱卷算法的應(yīng)用研究

    在程序設(shè)計語言考試中,程序設(shè)計主觀智能評閱是一項具有實用價值的應(yīng)用。文中在分析主觀閱卷算法的基礎(chǔ)上,針對程序設(shè)計主觀的特征,提出了基于閱卷參考點和程序
    發(fā)表于 10-10 15:28 ?12次下載

    考研高頻詞匯

    考研高頻詞匯 1. abide by(=be faithful to ; obey)忠于;遵守。2. be absent from…. 缺席,不在3. 
    發(fā)表于 05-14 13:59 ?12次下載

    一考你!這三嵌入式Linux你會嗎?來做一下吧

    一: 解釋命令ls -a | more具體含義. 思考過后,再到下方尋找答案 二: GCC -g -o
    的頭像 發(fā)表于 04-03 11:22 ?5376次閱讀

    Linux面試3

    關(guān)鍵詞:linux、面試 第一:下面的網(wǎng)絡(luò)協(xié)議中,面向連接的的協(xié)議是( ) A 傳輸控制協(xié)議 B 用戶數(shù)據(jù)報協(xié)議 C 網(wǎng)際協(xié)議 D 網(wǎng)際控制報文協(xié)議 第二:. Linux文件權(quán)限一共10位長度
    發(fā)表于 09-23 11:03 ?486次閱讀

    40道經(jīng)典JAVA算法和解答

    本文檔的主要內(nèi)容詳細介紹的是40道經(jīng)典JAVA算法和解答。
    發(fā)表于 07-02 08:00 ?0次下載
    40道經(jīng)典JAVA<b class='flag-5'>算法</b><b class='flag-5'>題</b>和解答

    快來,我出個算法給你做做

    大家一個算法 責任編輯:xj 原文標題:大家一個算法 文章出處:【微信公眾號:
    的頭像 發(fā)表于 10-10 16:55 ?1398次閱讀

    套名校自控考研真電子版下載

    套名校自控考研真電子版下載
    發(fā)表于 03-24 10:15 ?0次下載
    <b class='flag-5'>十</b>套名校自控考研真<b class='flag-5'>題</b>電子版下載

    算法類型以及準備策略

    今天就和大家聊聊大公司的面試環(huán)節(jié)經(jīng)常涉及的算法類型以及準備策略。 問題難度首先大家比較關(guān)心的就是面試時候出現(xiàn)的算法的難度,從我的個人經(jīng)驗來看,除了有一次和同樣有acm獲獎經(jīng)歷的面試
    的頭像 發(fā)表于 09-02 10:50 ?1483次閱讀

    單調(diào)棧解題模板如何秒殺三算法

    單調(diào)棧實際上就是棧,只是利用了一些巧妙的邏輯,使得 **每次新元素入棧后,棧內(nèi)的元素都保持有序** (單調(diào)遞增或單調(diào)遞減)。 本文就通過幾道算法來看看單調(diào)棧模板的使用。
    的頭像 發(fā)表于 04-19 10:52 ?919次閱讀
    單調(diào)棧解題模板如何秒殺三<b class='flag-5'>道</b><b class='flag-5'>算法</b><b class='flag-5'>題</b>

    PCB生產(chǎn)工藝 | 第十道主流程之表面處理

    如圖,第十道主流程為電測。電測的目的:電測又叫電氣性能測試、功能測試或開短路測試等,主要是對PCB的網(wǎng)絡(luò)通過測試治具或測試針接觸網(wǎng)絡(luò)的測試點位進行開短路檢測,將壞板挑選出來。是PCB生產(chǎn)過程中的一
    的頭像 發(fā)表于 03-30 18:20 ?817次閱讀
    PCB生產(chǎn)工藝 | 第<b class='flag-5'>十道</b>主流程之表面處理
    主站蜘蛛池模板: 亚洲精品色婷婷在线蜜芽 | 曰本熟妇乱妇色A片在线| 成片免费观看视频在线网| 久久国产一区二区三区| 我的好妈妈8高清在线观看WWW| 99日影院在线播放| 久久99re热在线观看视频| 午夜亚洲WWW湿好大| 八妻子秋霞理在线播放| 理论片午午伦夜理片I| 亚洲欧美中文日韩v在线| 国产99对白在线播放| 免费国产久久啪在线| 亚洲男同tv| 国产精品一区二区四区| 热九九99香蕉精品品| 777黄色片| 久久理伦片琪琪电影院| 亚洲成年人影院| 国产成人免费在线| 欧美色妞AV重囗味视频| 4hu四虎免费影院www| 久久精品一本到东京热| 亚洲乱码日产精品BD在线下载| 国产成人久久AV免费看澳门| 秋霞鲁丝片Av无码| 99精品国产电影| 妈妈的朋友6未删减版完整在线| 亚洲日本乱码中文论理在线电影| 国产精品人成视频免费999| 色多多污污在线播放免费| 阿v天堂2017在无码| 暖暖 视频 免费 高清 在线观看| 中文无码第3页不卡av| 九色终合九色综合88| 亚洲精品在看在线观看| 国产亚洲精品成人a在线| 天天看高清影视在线18| 俄罗斯爱爱| 色偷偷爱偷偷要| 攵女yin乱合集高h|