41. 缺失的第一個(gè)正數(shù)

這個(gè)題目的通過率很低，是一道難題，類似于腦筋急轉(zhuǎn)彎，確實(shí)不好想。實(shí)際上，對(duì)于一個(gè)長(zhǎng)度為 N 的數(shù)組，其中沒有出現(xiàn)的最小正整數(shù)只能在 [1,N+1] 中。

這個(gè)結(jié)論并不好想，舉個(gè)例子：nums = [3,4,-1,1]，長(zhǎng)度為 4，未出現(xiàn)的最小正數(shù)是 2；極端一點(diǎn)，nums = [1,2,3,4]，未出現(xiàn)的最小正數(shù)是 5。因此算法的第一步就是預(yù)處理，將這個(gè)范圍之外的數(shù)全部標(biāo)記掉：

		for (int& num : nums) {if (num <= 0 || num > n) {num = n + 1;}}

對(duì)于 nums = [3,4,-1,1]，操作之后，nums = [3,4,5,1]。

第二步，需要將符合條件的數(shù)，放到它標(biāo)記到應(yīng)該呆的位置上，標(biāo)記方法是取反，比如 1，就放到第一個(gè)位置 0，將每一個(gè)數(shù)操作一遍：

		for (int i = 0; i < n; ++i) {int pos = abs(nums[i]) - 1; // 計(jì)算原始數(shù)字對(duì)應(yīng)的索引if (pos < n && nums[pos] > 0) { // 只有在正常范圍內(nèi)的數(shù)才進(jìn)行放置nums[pos] =-nums[pos]; // 通過取負(fù)值來標(biāo)記這個(gè)位置的數(shù)字已經(jīng)存在}}

對(duì)于 nums = [3,4,5,1]，操作之后，nums = [3,4,-5,1]、nums = [3,4,-5,-1]、nums = [3,4,-5,-1]（不變）、nums = [-3,4,-5,-1]。經(jīng)過這輪操作之后，會(huì)發(fā)現(xiàn)，第二個(gè)數(shù)沒有被標(biāo)記，因此數(shù)組中沒有 2，因此將 2 返回：

		for (int i = 0; i < n; ++i) {if (nums[i] > 0) {return i + 1; // 返回缺失的第一個(gè)正數(shù)}}return n + 1; // 如果1到n都存在，那么返回n+1

73. 矩陣置零

這道題目的思路是，首先判斷第一行或者第一列是否有 0 元素：

		bool firstRowZero = false;bool firstColZero = false;for (int i = 0; i < m; i++) {if (matrix[i][0] == 0) {firstColZero = true;break;}}for (int j = 0; j < n; j++) {if (matrix[0][j] == 0) {firstRowZero = true;break;}}

然后根據(jù)非第一列非第一行得元素是否為零，標(biāo)記第一列或者第一行：

 		for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][j] == 0) {matrix[i][0] = 0;matrix[0][j] = 0;}}}

當(dāng)?shù)谝恍谢蛘叩谝涣斜粯?biāo)記了，就可以根據(jù)這個(gè)信息來標(biāo)記其它元素了：

		for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}}

最后根據(jù)flags 置第一行第一列元素為 0：

		if (firstColZero) {for (int i = 0; i < m; i++) {matrix[i][0] = 0;}}if (firstRowZero) {for (int j = 0; j < n; j++) {matrix[0][j] = 0;}}

48. 旋轉(zhuǎn)圖像

這個(gè)題目的思路是先轉(zhuǎn)置，然后反轉(zhuǎn)每一行：

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 轉(zhuǎn)置矩陣for (int i = 0; i < n; ++i) {for (int j = i; j < n; ++j) {swap(matrix[i][j], matrix[j][i]);}}// 反轉(zhuǎn)每一行for (int i = 0; i < n; ++i) {reverse(matrix[i].begin(), matrix[i].end());}}
};

240. 搜索二維矩陣 II

我以為這道題要從左上角開始搜索，后來才發(fā)現(xiàn)必須通過右上或者坐下，因?yàn)檫@兩個(gè)方向中，元素單調(diào)性是相反的，單調(diào)性如果相同，是沒辦法排除的：

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty() || matrix[0].empty())return false;int m = matrix.size();int n = matrix[0].size();int i = 0, j = n - 1;while (i < m && j >= 0) {if (matrix[i][j] == target) {return true;} else if (matrix[i][j] > target) {j--; } else {i++; }}return false; }
};

160. 相交鏈表

這道題目簡(jiǎn)單，直接雙指針，因?yàn)?A+B = B+A，它們這樣運(yùn)行一圈后，必然會(huì)相交：

class Solution {
public:ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {if (headA == NULL || headB == NULL)return NULL;ListNode* pA = headA;ListNode* pB = headB;while (pA != pB) {// 如果達(dá)到末尾，則轉(zhuǎn)向另一鏈表的頭部pA = pA == NULL ? headB : pA->next;pB = pB == NULL ? headA : pB->next;}// 若相遇，則 pA 或 pB 為交點(diǎn)，或兩者均為 NULL，未相交return pA;}
};

206. 反轉(zhuǎn)鏈表

這個(gè)題目用兩種解法，遞歸和迭代：

class Solution {
public:ListNode* reverseList(ListNode* head) {// 遞歸// if(head ==  nullptr || head->next == nullptr)// return head;// ListNode *newNode = reverseList(head->next);// head->next->next = head;// head->next = nullptr;// return newNode;// 迭代ListNode* prev = nullptr; // 前一個(gè)結(jié)點(diǎn)ListNode* curr = head;    // 遍歷ListNode* next = nullptr; // 存儲(chǔ)下一個(gè)結(jié)點(diǎn)while (curr != nullptr) {next = curr->next; // 存儲(chǔ)下一個(gè)結(jié)點(diǎn)curr->next = prev; // 反轉(zhuǎn)當(dāng)前prev = curr;       // 移動(dòng)curr = next;       // 移動(dòng)}return prev;}
};

234. 回文鏈表

這個(gè)題目能用到上面的解法，先用快慢指針找到中點(diǎn)，然后反轉(zhuǎn)后面的鏈表，然后雙指針從兩邊向中心靠近且比較：

class Solution {
public:bool isPalindrome(ListNode* head) {if (head == nullptr || head->next == nullptr)return true;ListNode *slow = head, *fast = head, *prev = nullptr, *next = nullptr;while (fast != nullptr && fast->next != nullptr) {fast = fast->next->next;slow = slow->next;}while (slow != nullptr) {next = slow->next;slow->next = prev;prev = slow;slow = next;}ListNode* left = head;ListNode* right = prev;while (right != nullptr) {if (left->val != right->val)return false;left = left->next;right = right->next;}return true;}
};

141. 環(huán)形鏈表

快慢指針：

	bool hasCycle(ListNode* head) {ListNode *fast = head, *slow = head;while (fast != nullptr && slow != nullptr) {fast = fast->next;if (fast == nullptr)return false;fast = fast->next;slow = slow->next;if (slow == fast)return true;}return false;}

142. 環(huán)形鏈表 II

這個(gè)用哈希表簡(jiǎn)直是降維打擊：

	ListNode *detectCycle(ListNode *head) {unordered_set<ListNode *> visited;while (head != nullptr) {if (visited.count(head)) {return head;}visited.insert(head);head = head->next;}return nullptr;}

21. 合并兩個(gè)有序鏈表

使用一個(gè)偽頭結(jié)點(diǎn)，然后將所有的結(jié)點(diǎn)掛在這個(gè)結(jié)點(diǎn)上：

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode dummy(0); ListNode* tail = &dummy; // 使用一個(gè)尾指針，始終指向新鏈表的最后一個(gè)節(jié)點(diǎn)while (list1 && list2) {if (list1->val < list2->val) {tail->next = list1;  // 接上 list1 的當(dāng)前節(jié)點(diǎn)list1 = list1->next; // 移動(dòng) list1 指針} else {tail->next = list2;  // 接上 list2 的當(dāng)前節(jié)點(diǎn)list2 = list2->next; // 移動(dòng) list2 指針}tail = tail->next; // 移動(dòng)尾指針到新鏈表的末尾}tail->next = list1 ? list1 : list2;return dummy.next; }
};

總結(jié)

41. 缺失的第一個(gè)正數(shù)

• 利用索引作為哈希鍵通過元素取反來標(biāo)記存在的數(shù)字，有效利用數(shù)組自身空間來存儲(chǔ)信息。
• 確保處理后的數(shù)組中，每個(gè)數(shù)字都在其應(yīng)有的位置上，沒有則是缺失的最小正數(shù)。

73. 矩陣置零

• 使用矩陣的第一行和第一列作為標(biāo)記數(shù)組，記錄哪些行列需要被置零。
• 分步處理，先標(biāo)記，后置零，注意操作的順序和邏輯清晰。

48. 旋轉(zhuǎn)圖像

• 先轉(zhuǎn)置矩陣，然后反轉(zhuǎn)每一行，是一種簡(jiǎn)潔的在原地操作矩陣的方法，符合題目要求的空間復(fù)雜度。

240. 搜索二維矩陣 II

• 從右上角（或左下角）開始搜索，利用行和列的單調(diào)性來排除行或列，這種策略提高了搜索效率。

160. 相交鏈表

• 雙指針法，一個(gè)從鏈表A出發(fā)到鏈表B，另一個(gè)從鏈表B出發(fā)到鏈表A，兩者會(huì)在交點(diǎn)相遇。
• 由于路徑長(zhǎng)度相同（A+B=B+A），所以兩指針會(huì)同時(shí)到達(dá)交點(diǎn)。

206. 反轉(zhuǎn)鏈表

• 迭代和遞歸兩種方式，迭代方式通過交換指針方向在原地反轉(zhuǎn)鏈表，而遞歸則是通過遞歸棧來實(shí)現(xiàn)。

234. 回文鏈表

• 快慢指針找到中點(diǎn)，反轉(zhuǎn)后半部分，然后前后兩部分進(jìn)行比對(duì)。
• 這種方法充分利用了鏈表的特性，減少了空間復(fù)雜度。

141. 環(huán)形鏈表

• 快慢指針法檢測(cè)環(huán)，快指針每次走兩步，慢指針每次走一步，如果相遇則說明有環(huán)。

142. 環(huán)形鏈表 II

• 使用哈希表記錄訪問過的節(jié)點(diǎn)，第一個(gè)重復(fù)訪問的節(jié)點(diǎn)即為環(huán)的入口。
• 或者使用快慢指針確定環(huán)的存在后，用兩個(gè)指針從頭和相遇點(diǎn)出發(fā)，第二次相遇點(diǎn)即為環(huán)的入口。

21. 合并兩個(gè)有序鏈表

• 使用一個(gè)偽頭節(jié)點(diǎn)簡(jiǎn)化邊界情況的處理，通過比較兩鏈表頭部節(jié)點(diǎn)的值，依次選擇較小的節(jié)點(diǎn)拼接到新鏈表上。