用js做自適應(yīng)網(wǎng)站nba最新交易匯總實(shí)時(shí)更新
最好的,不一定是最合適的;最合適的,才是真正最好的。💓💓💓
目錄
?說(shuō)在前面
題目一:分割鏈表
題目二:環(huán)形鏈表的約瑟夫問(wèn)題
SUMUP結(jié)尾
?說(shuō)在前面
?dear朋友們大家好!💖💖💖數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)離不開(kāi)刷題,繼上次算法OJ練習(xí)1,我們繼續(xù)進(jìn)行鏈表經(jīng)典算法的練習(xí)。當(dāng)然除了了LeetCode,有些題也會(huì)在NowCoder上,大家可以在這兩個(gè)網(wǎng)站上進(jìn)行練習(xí)。
?👇👇👇
友友們!🎉🎉🎉點(diǎn)擊這里進(jìn)入力扣leetcode學(xué)習(xí)🎉🎉🎉
?以下是leetcode題庫(kù)界面:
?
?👇👇👇
🎉🎉🎉點(diǎn)擊這里進(jìn)入牛客網(wǎng)NowCoder刷題學(xué)習(xí)🎉🎉🎉
?以下是NowCoder題庫(kù)界面:
?
??
題目一:分割鏈表
題目鏈接:面試題 02.04. 分割鏈表 - 力扣(LeetCode)
題目描述:
?題目分析:
思路:創(chuàng)建大小鏈表,若pcur節(jié)點(diǎn)的值小于x則插入小鏈表,若pcur節(jié)點(diǎn)的值大于x則插入大鏈表,再將大小鏈表連接。
注意,實(shí)際上小鏈表的lesstail指向了原鏈表中數(shù)據(jù)為5的節(jié)點(diǎn),而大鏈表的greatertail指向了原鏈表中數(shù)據(jù)為2的節(jié)點(diǎn)。所以在連接大小鏈表時(shí),除了將小鏈表中的lesstail的next指針指向大鏈表中的第一個(gè)有效節(jié)點(diǎn)(而非頭節(jié)點(diǎn))greaterhead->next,還需要將大鏈表中的greatertail的next指針置空,否則將形成循環(huán)鏈表。
代碼如下:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* partition(struct ListNode* head, int x) {//單獨(dú)討論空鏈表的情況if(head==NULL)return NULL; //創(chuàng)建大小指針ListNode* lesshead=(ListNode*)malloc(sizeof(ListNode));ListNode* lesstail=lesshead;ListNode* greaterhead=(ListNode*)malloc(sizeof(ListNode));ListNode* greatertail=greaterhead;ListNode* pcur=head;//遍歷數(shù)組while(pcur){if(pcur->val<x)//放入小鏈表{lesstail->next=pcur;lesstail=pcur;}else//放入大鏈表{greatertail->next=pcur;greatertail=pcur;}pcur=pcur->next;}greatertail->next=NULL;//結(jié)尾置NULLlesstail->next=greaterhead->next;連接大小鏈表ListNode* ret=lesshead->next;//保存第一個(gè)有效節(jié)點(diǎn)//釋放動(dòng)態(tài)申請(qǐng)的空間free(lesshead);free(greaterhead);return ret;
}
?
題目二:環(huán)形鏈表的約瑟夫問(wèn)題
題目鏈接:環(huán)形鏈表的約瑟夫問(wèn)題_??皖}霸_牛客網(wǎng) (nowcoder.com)
背景:著名的約瑟夫問(wèn)題
據(jù)說(shuō)猶太著名歷史學(xué)家 Josephus 有過(guò)一下的故事:在羅馬人占領(lǐng)喬塔帕特后,39個(gè)猶太人與Joesphus 及他的朋友躲到一個(gè)洞中,39個(gè)猶太人決定寧死也不要被人抓到,于是決定了一個(gè)自殺方式,41個(gè)人排成一個(gè)圓圈,由第1個(gè)人開(kāi)始報(bào)數(shù),每報(bào)數(shù)到第3人該人就必須自殺,然后再由下一個(gè)重新報(bào)數(shù),知道所有人都自殺身亡為止。
然而 Josephus 和他的朋友并不想遵從,Josephus 要他的朋友先假裝遵從,他將朋友與自己安排在第16個(gè)與第31個(gè)位置,于是逃過(guò)了這場(chǎng)死亡游戲。
題目描述:
?題目分析:
思路:利用count計(jì)數(shù),count為m時(shí)刪除所對(duì)應(yīng)的節(jié)點(diǎn),直到剩下一個(gè)節(jié)點(diǎn)。
我們以約瑟夫事件原型為例,此時(shí)n=5,m=3,我們需要先創(chuàng)建這樣一個(gè)帶環(huán)鏈表,將它封裝為函數(shù)circle,而創(chuàng)建鏈表就需要申請(qǐng)節(jié)點(diǎn),將其封裝為函數(shù)ListBuyNode,同時(shí)需要在帶環(huán)鏈表中把每個(gè)節(jié)點(diǎn)的數(shù)據(jù)設(shè)置好,這個(gè)行為我們可以用for循環(huán)完成。?
創(chuàng)建好鏈表后,我們需要?jiǎng)?chuàng)建兩個(gè)指針:pcur用來(lái)遍歷鏈表,每每遍歷到下一個(gè)節(jié)點(diǎn)count++,如果遍歷的過(guò)程中count達(dá)到m,就刪除這個(gè)節(jié)點(diǎn),此時(shí)需要將pcur的前一個(gè)指針指向pcur的后一個(gè)指針,所以我們還需要指針prev來(lái)記錄pcur的前一個(gè)指針,以此往復(fù),直到只剩下一個(gè)節(jié)點(diǎn),此時(shí)pcur->next指向pcur它自己,所以循環(huán)條件就是pcur->next!=pcur。
代碼如下:
/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定,請(qǐng)勿修改,直接返回方法規(guī)定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/typedef struct ListNode ListNode;//創(chuàng)建節(jié)點(diǎn)ListNode* ListBuyNode(int x){ListNode* node=(ListNode*)malloc(sizeof(ListNode));if(node==NULL){perror("malloc");exit(1);}node->val=x;node->next=NULL;return node;}//創(chuàng)建帶環(huán)鏈表ListNode* circle(int n){ListNode* phead=ListBuyNode(1);ListNode* ptail=phead;for(int i=2;i<=n;i++){ptail->next=ListBuyNode(i);ptail=ptail->next;}ptail->next=phead;return ptail;}
int ysf(int n, int m)
{//創(chuàng)建關(guān)于n的帶環(huán)鏈表ListNode* prev=circle(n);ListNode* pcur=prev->next;int count=1;while(pcur!=pcur->next){if(count==m){//銷毀pcur節(jié)點(diǎn)prev->next=pcur->next;free(pcur);pcur=prev->next;count=1;}else{prev=pcur;pcur=pcur->next;count++;}}return pcur->val;
}
?約瑟夫問(wèn)題是循環(huán)鏈表的經(jīng)典應(yīng)用,大家重視起來(lái),務(wù)必熟練掌握。?
SUMUP結(jié)尾
數(shù)據(jù)結(jié)構(gòu)就像數(shù)學(xué)題,需要刷題才能對(duì)它有感覺(jué)。之后還會(huì)更新數(shù)據(jù)結(jié)構(gòu)相關(guān)的練習(xí)題、面試題,希望大家一起學(xué)習(xí),共同進(jìn)步~
如果大家覺(jué)得有幫助,麻煩大家點(diǎn)點(diǎn)贊,如果有錯(cuò)誤的地方也歡迎大家指出~