暑期算法訓練.11

目錄

47. 力扣203 移除鏈表元素

47.1 題目解析：

?編輯?

47.2 算法思路：

47.3 代碼演示：

?編輯?

48. 力扣2.兩數相加

48.1 題目解析：

?編輯?

48.2 算法思路;

48.3 代碼演示：

48.4 總結反思：

49. 力扣24 兩兩交換鏈表中的節點

49.1 題目解析：

49.2 算法思路：

49.3 代碼演示：

?編輯

49.4 總結反思

50. 力扣 143 重排鏈表

50.1 題目解析：

50.2 算法思路：

?

50.3 代碼演示：

?編輯

50.4 總結反思

51 力扣 25 k個1組翻轉鏈表

51.1題目解析：

51.2?算法思路：

?編輯?

?

51.3?代碼演示：

??編輯

51.4 總結反思

今天咱們講鏈表，以及鏈表常用操作總結：

就是咱們接下來的題目，基本上都會用到這幾種方法：

1.畫圖！！！（這個畫圖特別重要），因為畫圖直觀加形象加便于我們理解

2.咱們在做題的時候，可以引入虛擬節點：

【1】虛擬頭結點可以簡化邊界的處理。

【2】可以統一操作，不需要再單獨的對頭節點進行特殊操作。為什么這么說呢？是因為

那么接下來咱們通過一道題目來進行實際的探查：

47. 力扣203 移除鏈表元素

47.1 題目解析：

?

題目很簡單。就是刪除值為val的某個節點

47.2 算法思路：

就是遍歷整個鏈表，找到值為val的那個元素，然后再跳過這個元素即可。

47.3 代碼演示：

?

//不帶虛擬頭結點
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 需要單獨處理頭節點,確保頭結點不為空，并且里面的數值也不可以是空，頭結點是個有效的頭結點while (head != nullptr && head->val == val) {head = head->next;}// 再處理其他節點ListNode* cur = head;while (cur != nullptr && cur->next != nullptr) {if (cur->next->val == val) {cur->next = cur->next->next;}else {cur = cur->next;}}return head;}
};

這個是不帶虛擬頭結點的版本，可以看出來，咱們需要單獨的處理一下頭結點，然后再是處理其他的節點。并且，如果這樣的話，步驟就比較繁瑣，而且不容易統一處理方式

//帶虛擬頭結點的版本
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy = new ListNode(0); // 虛擬頭節點指向headdummy->next = head;ListNode* cur = dummy;while (cur->next != nullptr) {if (cur->next->val == val) {cur->next = cur->next->next; // 統一刪除邏輯，直接跳過這個節點即可，也是單向鏈表通常的刪除邏輯}else {cur = cur->next;}}return dummy->next; // 新頭節點}
};

這個是帶虛擬頭結點的版本，是不是很爽，基本可以統一處理節點了（包括頭節點）。

所以，虛擬頭節點的好處就是：

1. 避免頭節點的特殊處理

  • 問題：在鏈表操作中，如果直接操作頭節點（如刪除、反轉、插入等），通常需要額外判斷：

    • 如果刪除頭節點，需要重新指定?head。

    • 如果插入新節點到頭部，需要更新?head。

  • 虛擬頭結點的作用：

    • 提供一個統一的“前驅節點”，使得頭節點和其他節點的操作邏輯一致。

    • 無論原頭節點如何變化，dummy->next?始終指向新頭節點。

2. 簡化代碼邏輯

  • 沒有虛擬頭結點：需要單獨處理頭節點，代碼分支增多。

  • 有虛擬頭結點：所有節點（包括原頭節點）都有前驅節點，可以用統一邏輯處理。

?

在C++中，虛擬頭節點一般這樣創建：

ListNode* dummy = new ListNode(0); // 值任意，一般用0
dummy->next = head; // 指向原頭節點
// ... 操作鏈表
return dummy->next; // 返回新頭節點

3.不要吝嗇空間，該創建的時候就得創建，這樣可以省去不少的麻煩：

想必大家多多少少都做過這種題目吧，就是斷開兩個節點之間的鏈接，讓第三個節點鏈接上去。那么此時，咱們如果不定義一個next節點變量，直接就有兩個變量（prev，cur）去連接的話，此時就得注意一下順序了。只能按照咱們圖中所指的順序來進行鏈接。

prev->next->prev=cur;
cur->next=prev->next;
prev->next=cur;
cur->prev=prev;

如果前兩行與后兩行顛倒了，先執行后兩行，那么這樣的話，會發現找不到后面那個節點了，也會導致cur->next=cur，自己指向自己，死循環。所以，這個時候就體現了，再定義一個新變量的必要性。再定義一個新變量，就不需要再擔心執行的順序了，管你先執行那個，都可以。

4.快慢指針

一般用于鏈表中環的判斷，找到鏈表中環的入口，找到鏈表中倒數第n個節點。

而咱們鏈表的常用操作就是1.創建一個新的節點，2.尾插 3.頭插（這個頭插法在逆序鏈表中還是比較常用的）

這個是尾插，還是比較簡單的。

這個是頭插。相對于尾插來說，還是復雜一點的。

48. 力扣2.兩數相加

48.1 題目解析：

?

這個題目有個關鍵的地方就是逆序操作，咱們可以直接從頭開始加（因為這個是逆序存儲的），即2,4,3 逆序存儲為 3,4,2。5，6，4 逆序存儲為4,6,5 。那么3，4，2與4，6，5相加，由于是從最低位開始加，那么逆序之后，對應的就從鏈表的頭開始相加，非常的方便。

48.2 算法思路;

直接模擬兩數相加即可

?

以上就是這個題目的所有的算法思路。

48.3 代碼演示：

struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}};
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1 = l1; ListNode* cur2 = l2;ListNode* newnode = new ListNode(0);//創建一個虛擬頭結點，記錄最終結果int t = 0;ListNode* prev = newnode;while (cur1 || cur2 || t){if (cur1){t += cur1->val;cur1 = cur1->next;}if (cur2){t += cur2->val;cur2 = cur2->next;}prev->next = new ListNode(t % 10);//新建一個節點才能去存儲數字，因為此時newnode后面并沒有節點。prev = prev->next;t /= 10;}ListNode* next = newnode->next;delete newnode;return next;}
};

48.4 總結反思：

這道題目充分的利用了上面的知識，所以還得具備充分的知識儲備才可以。

49. 力扣24 兩兩交換鏈表中的節點

49.1 題目解析：

本題交換節點需要注意的是，不可以只交換節點里面的數值，必須得連著節點一起交換才可以。

49.2 算法思路：

OK，算法思路就是上面我寫的這些，大家好好的參悟一下

49.3 代碼演示：

class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;//若是鏈表為空，或者是鏈表只有一個元素，直接返回。注意，這里判斷的標準時head，因為head才是真正的頭結點，而不是newHead。判斷這個的目的是為了預防下面的cur->next（cur為空，cur就是頭結點，鏈表為空）與next->next（鏈表只有一個元素，此時next為空），空指針解引用ListNode* newHead = new ListNode(0);newHead->next = head;//head才是真正的頭結點ListNode* prev = newHead;ListNode* cur = prev->next; ListNode* next = cur->next; ListNode* nnext = next->next;while (cur && next){//更新節點prev->next = next;next->next = cur;cur->next = nnext;//交換指針prev = cur;cur = nnext;if (cur) next = cur->next;if (next) nnext = next->next;}ListNode* kk = newHead->next;delete newHead;return kk;}
};

49.4 總結反思

其實這道題目也是用到了上面咱們所說的這些算法，大家還是得好好的參悟一下

50. 力扣 143 重排鏈表

50.1 題目解析：

這個題目其實是讓你按照一定得順序重新排一下鏈表

?

那么其實題目就是這樣的，所以咱們可以分為三個步驟

1.找到鏈表的中間節點

使用快慢指針（一定要畫圖，考慮使用slow得落點在哪里）

2.把后面的部分逆序

使用雙指針（或者三指針），或者頭插法（推薦）完成逆序

3.合并兩個有序鏈表，（雙指針），按照一定得順序合并

50.2 算法思路：

?關于slow的落點，咱們直接砍掉slow后面的部分給逆序即可。不過需要引入虛擬頭結點。一開始得先頭插進第二個鏈表：

?

?

?

?

50.3 代碼演示：

class Solution {
public:void reorderList(ListNode* head) {if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;//先找到中間節點ListNode* slow = head; ListNode* fast = head;while (fast && fast->next)//注意循環條件是這個，不是slow<fast{slow = slow->next;fast = fast->next->next;}//之后使用頭插法對slow后面的部分進行逆序ListNode* head2 = new ListNode(0);ListNode* cur = slow->next;slow->next = nullptr;while (cur){ListNode* next = cur->next;//再定義一個變量存儲這個cur，就是為了防止順序問題cur->next = head2->next;head2->next = cur;cur = next;}//之后進行合并鏈表ListNode* kk = new ListNode(0);ListNode* prev = kk;ListNode* cur1 = head;ListNode* cur2 = head2->next;while (cur1){//先合并第一個鏈表prev->next = cur1;cur1 = cur1->next;prev = prev->next;//再合并第二個鏈表if (cur2){prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}delete head2;delete kk;}
};

這樣的代碼量，放在整個鏈表對應的題目里面，算是比較多的了

50.4 總結反思

重點的東西還是開篇所講的那些東西，還是希望大家要好好的研讀，最好記住。

51 力扣 25 k個1組翻轉鏈表

51.1題目解析：

其實這一題就考了一個模擬，并且也用到了逆序

51.2?算法思路：

?

?

?

51.3?代碼演示：

?

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {//求出需要逆序多少組int n = 0;ListNode* cur = head;while (cur){cur = cur->next;n++;}n /= k;//重復n次，將長度為k的鏈表逆序即可ListNode* newHead = new ListNode(0);ListNode* prev = newHead;ListNode* cur1 = head;for (int i = 0; i < n; i++){ListNode* tmp = cur1;//把一開始的cur1的位置給存起來，由于是逆序存儲，所以說后面的tmp的位置，就是下一組逆序頭插的位置for (int j = 0; j < k; j++)//不可寫成whilw(k--)/*k 被修改后沒有恢復：內層 while (k--) 會直接修改 k 的值，導致后續循環（如果有）的 k 不正確。例如：第一次循環 k = 3，執行完 while (k--) 后 k = -1。如果還有第二次循環，k 已經變成 - 1，導致內層循環不執行，邏輯錯誤。n 被修改后不影響邏輯，但 k 被修改會導致后續組的反轉次數錯誤。*/{ListNode* next = cur1->next;cur1->next = prev->next;prev->next = cur1;cur1 = next;}prev = tmp;}//剩下的直接接在后面即可prev->next = cur1;ListNode* cur2 = newHead->next;delete newHead;return cur2;}
};

這個地方，作者一開始寫的時候，出現了一個失誤，給大家看一下：

這個是錯誤的：
while(n--)  // 直接修改n的值
{ListNode* tmp = cur1;while(k--)  // 直接修改k的值{// 反轉邏輯}prev = tmp;
}

問題：

  1. k?被修改后沒有恢復：內層?while(k--)?會直接修改?k?的值，導致后續循環（如果有）的?k?不正確。例如：

    • 第一次循環?k=3，執行完?while(k--)?后?k=-1。

    • 如果還有第二次循環，k?已經變成?-1，導致內層循環不執行，邏輯錯誤。

  2. n?被修改后不影響邏輯，但?k?被修改會導致后續組的反轉次數錯誤。

這個是正確的：
for(int i=0; i<n; i++)  // 不修改n
{ListNode* tmp = cur1;for(int j=0; j<k; j++)  // 不修改k{// 反轉邏輯}prev = tmp;
}

改進點：

  1. 使用?for?循環代替?while?循環：

    • for(int j=0; j<k; j++)?不會修改?k?的值，確保每次反轉都是?k?個節點。

    • for(int i=0; i<n; i++)?也不會修改?n，但即使修改?n?也不會影響邏輯。

  2. 避免了?k?被錯誤修改：

    • 由于?k?保持不變，每次都能正確反轉?k?個節點。

?

51.4 總結反思

今天的知識基本都用到了我在開篇所講的那些知識

本篇完.................?

?

?

?

?

?

?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/91344.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/91344.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/91344.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

nl2sql grpo強化學習訓練，加大數據量和輪數后，準確率沒提升，反而下降了，如何調整

nl2sql grpo強化學習訓練，加大數據量和輪數后，準確率沒提升，反而下降了，如何調整

在NL2SQL任務中使用GRPO強化學習訓練時&#xff0c;增加數據量和訓練輪數后準確率下降&#xff0c;通常是由過擬合、訓練不穩定、獎勵函數設計不合理、數據質量問題或探索-利用失衡等原因導致的。以下是具體的診斷思路和調整策略&#xff0c;幫助定位問題并優化性能&#xff1a…
閱讀更多...
PHP/Java/Python實現：如何有效防止惡意文件上傳

PHP/Java/Python實現：如何有效防止惡意文件上傳

文章目錄 木馬病毒防范：文件上傳如何徹底防止偽造文件類型 引言 一、文件類型偽造的原理與危害 1.1 常見偽造手段 1.2 潛在危害 二、防御體系設計 2.1 防御架構 三、核心防御技術實現 3.1 服務端驗證實現 3.1.1 文件內容檢測（Python示例） 3.1.2 擴展名與內容雙重驗證（Java示…
閱讀更多...
SpringBoot系列之基于Redis的分布式限流器

SpringBoot系列之基于Redis的分布式限流器

SpringBoot系列之基于Redis的分布式限流器 SpringBoot 系列之基于 Redis 的分布式限流器 圖文并茂，代碼即拷即用，支持 4 種算法（固定窗口 / 滑動窗口 / 令牌桶 / 漏桶） 一、為什么要用分布式限流？ 單機 Guava-RateLimiter 在集群下會 各玩各的，流量漂移，無法全局控量。…
閱讀更多...
面試遇到的問題2

面試遇到的問題2

Redisson的看門狗相關問題 首先要明確一點&#xff0c;看門狗機制的使用方式是&#xff1a;在加鎖的時候不加任何參數&#xff0c;也就是&#xff1a; RLock lock redisson.getLock("myLock"); try {lock.lock(); // 阻塞式加鎖// 業務邏輯... } finally {lock.unl…
閱讀更多...
Linux—進程概念與理解

Linux—進程概念與理解

目錄 1.馮諾依曼體系結構 小結&#xff1a; 2.操作系統 概念&#xff1a; 結構示意圖&#xff1a; 理解操作系統&#xff1a; 用戶使用底層硬件層次圖&#xff1a;?編輯 3.進程 概念 結構示意圖 task_ struct內容分類 典型用法示例 觀察進程: 了解 PID PPID 查…
閱讀更多...
LeetCode 面試經典 150_數組/字符串_買賣股票的最佳時機（7_121_C++_簡單）(貪心)

LeetCode 面試經典 150_數組/字符串_買賣股票的最佳時機（7_121_C++_簡單）(貪心)

LeetCode 面試經典 150_數組/字符串_買賣股票的最佳時機&#xff08;7_121_C_簡單&#xff09;題目描述&#xff1a;輸入輸出樣例&#xff1a;題解&#xff1a;解題思路&#xff1a;思路一&#xff08;貪心算法&#xff09;&#xff1a;代碼實現代碼實現&#xff08;思路一&…
閱讀更多...
Ubuntu 18.04 repo sync報錯：line 0: Bad configuration option: setenv

Ubuntu 18.04 repo sync報錯：line 0: Bad configuration option: setenv

repo sync時報 line 0: Bad configuration option: setenv因為 Ubuntu 18.04 默認的 openssh-client 是 7.6p1&#xff0c;還不支持 setenv&#xff0c;但是.repo/repo/ssh.py 腳本中明確地傳入了 SetEnv 參數給 ssh&#xff0c;而你的 OpenSSH 7.6 不支持這個參數。需要按如下…
閱讀更多...
bug記錄-stylelint

bug記錄-stylelint

BUG1不支持Vue文件內聯style樣式解決&#xff1a; "no-invalid-position-declaration": null
閱讀更多...
前端開發(HTML,CSS,VUE,JS)從入門到精通！第一天(HTML5)

前端開發(HTML,CSS,VUE,JS)從入門到精通！第一天(HTML5)

一、HTML5 簡介1&#xff0e;HTML全稱是 Hyber Text Markup Language&#xff0c;超文本標記語言&#xff0c;它是互聯網上應用最廣泛的標記語言&#xff0c;簡單說&#xff0c;HTML 頁面就等于“普通文本HTML標記&#xff08;HTML標簽&#xff09;“。2&#xff0e;HTML 總共經…
閱讀更多...
智慧收銀系統開發進銷存：便利店、水果店、建材與家居行業的—仙盟創夢IDE

智慧收銀系統開發進銷存：便利店、水果店、建材與家居行業的—仙盟創夢IDE

在數字化轉型的浪潮中&#xff0c;收銀系統已不再局限于簡單的收款功能&#xff0c;而是成為企業進銷存管理的核心樞紐。從便利店的快消品管理到建材家居行業的大宗商品調度&#xff0c;現代收銀系統通過智能化技術重塑了傳統商業模式。本文將深入探討收銀系統在不同行業進銷存…
閱讀更多...
三維掃描相機：工業自動化的智慧之眼——遷移科技賦能智能制造新紀元

三維掃描相機：工業自動化的智慧之眼——遷移科技賦能智能制造新紀元

在當今工業4.0時代&#xff0c;自動化技術正重塑生產流程&#xff0c;而核心工具如三維掃描相機已成為關鍵驅動力。作為工業自動化領域的“智慧之眼”&#xff0c;三維掃描相機通過高精度三維重建能力&#xff0c;解決了傳統制造中的效率瓶頸和精度痛點。遷移科技&#xff0c;自…
閱讀更多...
Jmeter的元件使用介紹：（九）監聽器詳解

Jmeter的元件使用介紹：（九）監聽器詳解

監聽器主要是用來監聽腳本執行的取樣器結果。Jmeter的默認監聽器有&#xff1a;查看結果樹、聚合報告、匯總報告、用表格查看結果&#xff0c;斷言結果、圖形結果、Beanshell監聽器、JSR223監聽器、比較斷言可視化器、后端監聽器、郵件觀察器&#xff0c;本文介紹最常用的監聽器…
閱讀更多...
聯通元景萬悟 開源，搶先體驗！！！

聯通元景萬悟 開源，搶先體驗！！！

簡介&#xff1a; 元景萬悟智能體平臺是一款面向企業級場景的一站式、商用license友好的智能體開發平臺&#xff0c;是業界第一款go語言&#xff08;后端&#xff09;開發的智能體開發平臺&#xff08;7月19日&#xff09;&#xff0c;coze studio開源是7月26日&#xff0c;同時…
閱讀更多...
Git之本地倉庫管理

Git之本地倉庫管理

一.什么是Git在學習工作中&#xff0c;我們經常會遇到改文檔的場景。一個文檔可能會被我們修改多次&#xff0c;而最終真正使用的可能是最先的幾版。而如果我們直接在原文檔上修改&#xff0c;就會導致無法找到最先的幾次。這也就導致我們要對我們所有的版本進行維護&#xff0…
閱讀更多...
Go再進階：結構體、接口與面向對象編程

Go再進階：結構體、接口與面向對象編程

&#x1f680; Go再進階&#xff1a;結構體、接口與面向對象編程 大家好&#xff01;在前兩篇文章中&#xff0c;我們深入學習了Go語言的流程控制語句以及數組和切片的使用并且還對Go 語言的核心知識點進行了補充講解&#xff0c;這些知識讓我們能夠編寫出更為復雜和靈活的程序…
閱讀更多...
Python入門第六課：現代開發與前沿技術

Python入門第六課：現代開發與前沿技術

異步編程（asyncio） 1. 協程基礎 import asyncio import time# 定義協程函數 async def say_after(delay, message):await asyncio.sleep(delay)print(message)# 主協程 async def main():print(f"開始時間: {time.strftime(%X)}")# 順序執行await say_after(2, 你…
閱讀更多...
STM32移植LVGL9.2.1教程

STM32移植LVGL9.2.1教程

一、環境說明 &#xff08;1&#xff09;開發板&#xff1a;STM32F401RCT6核心板&#xff08;網上很多&#xff0c;價格只有幾塊錢&#xff09; &#xff08;2&#xff09;屏幕&#xff1a;2.8寸spi屏gt911觸摸 轉接板&#xff08;某寶有賣&#xff0c;沒有推廣自行搜索&…
閱讀更多...
python學智能算法（二十九）|SVM-拉格朗日函數求解中-KKT條件理解

python學智能算法（二十九）|SVM-拉格朗日函數求解中-KKT條件理解

【1】引言 前序學習階段中&#xff0c;我們掌握了最佳分割超平面對應的構造拉格朗日函數極值為&#xff1a; L(w,b,α)∑i1mαi?12∑i,j1mαiαjyiyjxiTxjL(w,b,\alpha)\sum_{i1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i,j1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}L(w,…
閱讀更多...
大模型應用開發1-認識大模型

大模型應用開發1-認識大模型

1.基礎概念 1.1 AI的概念&#xff1a; AI&#xff0c;??智能&#xff08;Artificial Intelligence&#xff09;&#xff0c;使機器能夠像?類?樣思考、學習和解決問題的技術。AI發展?今?概可以分為三個階段&#xff1a;其中&#xff0c;深度學習領域的自然語言處理&#…
閱讀更多...
Linux 遠程連接解析：SSH 協議理論與應用

Linux 遠程連接解析：SSH 協議理論與應用

Linux 遠程連接解析&#xff1a;SSH 協議理論與應用在網絡互聯的時代&#xff0c;遠程管理服務器已成為常態。SSH&#xff08;Secure Shell&#xff09;作為一種安全的網絡協議&#xff0c;憑借其加密機制和靈活的功能&#xff0c;成為 Linux 系統遠程操作的事實標準。本文將從…
閱讀更多...
最新文章

Copyright @ 2022~2023