美女直接做的網(wǎng)站有哪些汕頭網(wǎng)站建設(shè)方案推廣
文章目錄
- 參考資料
- 一 數(shù)組
- 1.1 二分查找
- 1.2 移除元素
- 1.3 長(zhǎng)度最小的子數(shù)組
- 1.4 螺旋矩陣
- 1.5 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
- 二 鏈表
- 2.1 移除鏈表元素
- 2.2 設(shè)計(jì)鏈表
- 2.3 反轉(zhuǎn)鏈表
- 2.4 兩兩交換鏈表中的節(jié)點(diǎn)
- 2.5 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
- 2.6 鏈表相交
- 2.7 環(huán)形鏈表II
- 三 哈希表
- 3.1 有效的字母異位詞
- 3.2 兩個(gè)數(shù)組的交集
參考資料
代碼隨想錄 https://programmercarl.com/
LeetCode https://leetcode.cn/
一 數(shù)組
1.1 二分查找
- 前提
有序數(shù)組,元素唯一(有重復(fù)元素,使用二分查找法返回的元素下標(biāo)可能不是唯一) - 思想
- 定義 target 是在一個(gè)在左閉右閉的區(qū)間里,也就是[left, right]
- while (left <= right) 要使用 <= ,因?yàn)閘eft == right是有意義的,所以使用 <=
- if (nums[middle] > target) right 要賦值為 middle - 1,因?yàn)楫?dāng)前這個(gè)nums[middle]一定不是target,那么接下來(lái)要查找的左區(qū)間結(jié)束下標(biāo)位置就是 middle - 1
- 若要通過二分查找確定插入位置,則最后需判斷nums[mid] > target,若是則mid為結(jié)果,若不是則mid + 1為結(jié)果
- 代碼
// https://leetcode.cn/problems/binary-search/description/ class Solution {public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left)/2;if (nums[mid] == target) {return mid;} if (nums[mid] < target) {left = mid + 1;}if (nums[mid] > target) {right = mid - 1;}}return -1;} };
1.2 移除元素
- 前提
O(1)空間,不要求保留原順序 - 思想
將要?jiǎng)h除的元素用數(shù)組最后面的元素進(jìn)行替換 - 代碼
// https://leetcode.cn/problems/remove-element/description/ class Solution {public:int removeElement(vector<int>& nums, int val) {int left = 0, right = nums.size() - 1;while (left <= right) {if (nums[left] == val) {nums[left] = nums[right];right --;} else {left ++;}}// [0, right]為需要保留的元素,長(zhǎng)度位right + 1return right + 1;} };
1.3 長(zhǎng)度最小的子數(shù)組
- 前提
O(1)空間,子數(shù)組連續(xù) - 思想
定義區(qū)間[left, right),當(dāng)區(qū)間和sum < target時(shí)移動(dòng)right,相反則記錄當(dāng)前區(qū)間長(zhǎng)度right - left并移動(dòng)left,直到right > 數(shù)組總長(zhǎng)度時(shí)結(jié)束循環(huán) - 代碼
// https://leetcode.cn/problems/minimum-size-subarray-sum/description/ class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0, right = 0; // [left, right)int sum = 0, ans = 0;while (right <= nums.size()) {if (sum < target) {// 此時(shí)right指針已達(dá)到末尾,且子數(shù)組和小于target// 結(jié)束循環(huán)if (right == nums.size()) {break;}sum += nums[right];right ++;} else {int len = right - left;if (ans == 0) {ans = len;} else {ans = ans > len ? len : ans;}sum -= nums[left];left ++;}}return ans;} };
1.4 螺旋矩陣
- 思想
關(guān)鍵在于方向的轉(zhuǎn)換,并且需要記錄行和列上還有多少是沒有遍歷過的,每次方向轉(zhuǎn)換都需要減少一個(gè)待遍歷的行或列 - 代碼
// https://leetcode.cn/problems/spiral-matrix-ii/description/ class Solution { public:vector<vector<int>> generateMatrix(int n) {// direction = 0 => 從左到右,direction = 1 => 從上到下// direction = 2 => 從右到左,direction = 3 => 從下到上int direction = 0;int row_count = n, col_count = n;int i_index = 0, j_index = 0; int num = 1;// 初始化結(jié)果vector<vector<int>> res;for (int i = 0; i < n; i ++) {vector<int> r(n);res.push_back(r);}while (num <= n * n) {// printf("direction = %d\n", direction);switch(direction) {case 0:// printf("case0, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < col_count; i ++) {res[i_index][j_index] = num;j_index ++;num ++;}i_index ++;j_index --;row_count --;break;case 1:// printf("case1, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < row_count; i ++) {res[i_index][j_index] = num;i_index ++;num ++;}i_index --;j_index --;col_count --;break;case 2:// printf("case2, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < col_count; i ++) {res[i_index][j_index] = num;j_index --;num ++;}j_index ++;i_index --;row_count --;break;case 3:// printf("case3, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < row_count; i ++) {res[i_index][j_index] = num;i_index --;num ++;}i_index ++;j_index ++;col_count --;break;}direction ++;direction = direction % 4;// for (int i = 0; i < n; i ++) {// for (int j = 0; j < n; j ++) {// cout << res[i][j];// }// cout << endl;// }}return res;} };
1.5 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
- 代碼
// https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/ class Solution { public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> ret(2, -1);// 有效區(qū)間[left, right]int left = 0, right = nums.size() - 1, mid;bool tag = false;while (left <= right) {mid = left + (right - left)/2;if (nums[mid] == target) {tag = true;break;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}if (!tag) return ret;// cout << left << " " << mid << " " << right << endl;// [left, mid - 1] 中尋找小于target的元素int l = left, r = mid - 1, from = left;while (l <= r) {int m = l + (r - l)/2;if (nums[m] < target) {from = m;break;} else {r = m - 1;}}// 向右找到第一個(gè)等于target的元素while (nums[from] != target) from ++;// [mid + 1, right] 中尋找大于target的元素l = mid + 1;r = right;int to = right;while (l <= r) {int m = l + (r - l)/2;if (nums[m] > target) {to = m;break;} else {l = m + 1;}}// 向左找到第一個(gè)等于target的元素while (nums[to] != target) to --;ret[0] = from;ret[1] = to;return ret;} };
二 鏈表
2.1 移除鏈表元素
- 思想
移除鏈表中指定元素的關(guān)鍵在于找到被移除元素的上一個(gè)節(jié)點(diǎn) - 代碼
// https://leetcode.cn/problems/remove-element/description/ class Solution { public:ListNode* removeElements(ListNode* head, int val) {// 定義虛擬頭節(jié)點(diǎn),不需要對(duì)第一個(gè)節(jié)點(diǎn)進(jìn)行特殊判斷ListNode *dummy_head = new ListNode(-1, head);// 定義pre和cur,方便刪除元素ListNode *pre = dummy_head;ListNode *cur = dummy_head->next;while (cur != NULL) {if (cur->val == val) {pre->next = cur->next;cur = pre->next;} else {pre = pre->next;cur = cur->next;}}return dummy_head->next;} };
2.2 設(shè)計(jì)鏈表
- 思想
- 設(shè)計(jì)虛擬頭節(jié)點(diǎn)可以簡(jiǎn)化對(duì)于第一個(gè)節(jié)點(diǎn)的操作
- 由題可知,大部分操作都需要找到下標(biāo)的為
index
的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn),因此設(shè)計(jì)了getPre(int index)
函數(shù) - 設(shè)計(jì)尾節(jié)點(diǎn)可以降低
addAtTail
的時(shí)間復(fù)雜度,但是在鏈表變化時(shí)需要對(duì)其進(jìn)行維護(hù)
- 代碼
// https://leetcode.cn/problems/design-linked-list/ class MyListNode { public:int val;MyListNode *next;MyListNode(int val, MyListNode *next) {this->val = val;this->next = next;} };class MyLinkedList { private:MyListNode *dummy_head;MyListNode *tail;int size;// 找到下標(biāo)為index的上一個(gè)節(jié)點(diǎn)MyListNode *getPre(int index) {MyListNode *node = dummy_head;while (index > 0) {node = node->next;index --;}return node;} public:MyLinkedList() {dummy_head = new MyListNode(-1, NULL);tail = NULL;size = 0;}int get(int index) {if (index >= size) {return -1;}MyListNode *node = getPre(index);return node->next->val;}void addAtHead(int val) {MyListNode *node = new MyListNode(val, NULL);node->next = dummy_head->next;dummy_head->next = node;if (tail == NULL) {tail = node;}size ++;}void addAtTail(int val) {if (tail == NULL) {addAtHead(val); } else {tail->next = new MyListNode(val, NULL);tail = tail->next;size ++;}}void addAtIndex(int index, int val) {// 如果 index 比長(zhǎng)度更大,該節(jié)點(diǎn)將 不會(huì)插入 到鏈表中if (index > size) {return ;}// 如果 index 等于鏈表的長(zhǎng)度,那么該節(jié)點(diǎn)會(huì)被追加到鏈表的末尾if (index == size) {addAtTail(val);} else {MyListNode *node = new MyListNode(val, NULL);MyListNode *p = getPre(index);node->next = p->next;p->next = node;size ++;}}void deleteAtIndex(int index) {if (index >= size) {return ;}MyListNode *p = getPre(index);// 要?jiǎng)h除的節(jié)點(diǎn)為尾節(jié)點(diǎn),需要修改tailif (p->next == tail) {p->next = NULL;tail = p;} else {p->next = p->next->next; }size --;} };
2.3 反轉(zhuǎn)鏈表
- 思想
- 為原鏈表添加虛擬頭節(jié)點(diǎn),刪除節(jié)點(diǎn)時(shí)不需要維護(hù)頭節(jié)點(diǎn),簡(jiǎn)化操作(新鏈表的虛擬頭節(jié)點(diǎn)同理)
- 反轉(zhuǎn)鏈表主要分為節(jié)點(diǎn)斷開和節(jié)點(diǎn)接入,分為兩部分實(shí)現(xiàn),可避免思路不清晰,導(dǎo)致鏈表成環(huán)(
q->next = NULL
可刪除)
- 代碼
// https://leetcode.cn/problems/reverse-linked-list/ class Solution { public:ListNode* reverseList(ListNode* head) {// 為原鏈表添加虛擬頭節(jié)點(diǎn),方便節(jié)點(diǎn)的刪除ListNode *dummy_head = new ListNode(-1, head);ListNode *p = dummy_head;// 為新鏈表添加虛擬頭節(jié)點(diǎn)ListNode *new_head = new ListNode(-1);while (p->next != NULL) {// 把節(jié)點(diǎn)從原鏈表斷開ListNode *q = p->next;p->next = q->next;q->next = NULL;// 把節(jié)點(diǎn)接入到新鏈表的頭部q->next = new_head->next;new_head->next = q;}return new_head->next;} };
2.4 兩兩交換鏈表中的節(jié)點(diǎn)
- 思想
- 多定義變量可一定程度上簡(jiǎn)化操作(變量不用🪙)
- 代碼
// https://leetcode.cn/problems/swap-nodes-in-pairs/description/ class Solution { public:ListNode* swapPairs(ListNode* head) {ListNode *dummy_head = new ListNode(-1, head);ListNode *p = dummy_head;while (p->next != NULL && p->next->next != NULL) {// a和b為要進(jìn)行交換的節(jié)點(diǎn),c為后面的節(jié)點(diǎn)ListNode *a = p->next;ListNode *b = a->next;ListNode *c = b->next;// 將a和b從原鏈表中斷開(為了方便理解,可省略)p->next = NULL;a->next = NULL;b->next = NULL;// 重新拼接p->next = b;b->next = a;a->next = c;p = a;} return dummy_head->next;} };
2.5 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
- 思想
先讓fast
跑n步,然后slow
和fast
再一起跑,fast
到達(dá)末尾時(shí),slow
剛好為倒數(shù)第n+1個(gè)節(jié)點(diǎn) - 代碼
// https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/ class Solution { public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *dummy_head = new ListNode(-1, head);ListNode *fast = dummy_head;ListNode *slow = dummy_head;while (n > 0) {fast = fast->next;n --;}while (fast->next != NULL) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummy_head->next; } };
2.6 鏈表相交
- 代碼
// https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/ class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 計(jì)算鏈表A和B的節(jié)點(diǎn)數(shù)int a_count = 0;int b_count = 0;ListNode *p = headA;while (p != NULL) {a_count ++;p = p->next;}p = headB;while (p != NULL) {b_count ++;p = p->next;}// 若兩個(gè)鏈表相差sub個(gè)節(jié)點(diǎn),則讓長(zhǎng)的鏈表先跑sub步while (a_count > b_count) {headA = headA->next;a_count --;}while (b_count > a_count) {headB = headB->next;b_count --;}// 兩個(gè)鏈表同時(shí)往前,此時(shí)遇到的第一個(gè)相同節(jié)點(diǎn)即為結(jié)果while (headA != headB) {headA = headA->next;headB = headB->next;}return headA;} };
2.7 環(huán)形鏈表II
- 思想
- 通過快慢指針法確定鏈表是否存在環(huán),并找到環(huán)中的任意一個(gè)節(jié)點(diǎn)
- 遍歷環(huán),直至將環(huán)中的所有節(jié)點(diǎn)添加到
set
集合中 - 從
head
開始遍歷,當(dāng)節(jié)點(diǎn)存在與set
集合中時(shí),即為環(huán)的入口節(jié)點(diǎn)
- 代碼
// https://leetcode.cn/problems/linked-list-cycle-ii/ class Solution { public:ListNode *detectCycle(ListNode *head) {// 通過快慢指針法確定鏈表是否存在環(huán),并找到環(huán)中的任意一個(gè)節(jié)點(diǎn)ListNode *fast = head;ListNode *slow = head;bool tag = false;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {tag = true;break;}}if (tag) {// 此時(shí)fast和slow都是環(huán)中的節(jié)點(diǎn),遍歷環(huán),直至將環(huán)中的所有節(jié)點(diǎn)添加到`set`集合中set<ListNode*> st;while (st.find(fast) == st.end()) {st.insert(fast);fast = fast->next;}// 從`head`開始遍歷,當(dāng)節(jié)點(diǎn)存在與`set`集合中時(shí),即為環(huán)的入口節(jié)點(diǎn)while (st.find(head) == st.end()) {head = head->next;}return head;} else {return NULL;}} };
- 最優(yōu)解法
// https://leetcode.cn/problems/linked-list-cycle-ii/solutions/12616/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/ class Solution { public:ListNode *detectCycle(ListNode *head) {ListNode *fast = head;ListNode *slow = head;bool tag = false;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {tag = true;break;}}if (!tag) return NULL;fast = head;while (fast != slow) {fast = fast->next;slow = slow->next;}return fast;} };
三 哈希表
3.1 有效的字母異位詞
- 思想
- 兩個(gè)字符串長(zhǎng)度不同,直接返回
false
- 遍歷字符串
s
,使用map
統(tǒng)計(jì)第一個(gè)字符串s
中每各字符出現(xiàn)的次數(shù) - 遍歷字符串
t
,若字符不存在于map
中,則返回false
;存在則進(jìn)行減操作,當(dāng)字符次數(shù)減為0時(shí),從map
移除 map
為空則表示兩個(gè)字符串是字母異位詞
- (進(jìn)階)由于題目中說明字符串都由小寫字母組成,那么我們可以將所有字符映射到長(zhǎng)度為26的數(shù)組,簡(jiǎn)化操作
- 兩個(gè)字符串長(zhǎng)度不同,直接返回
- 代碼(基礎(chǔ)解法)
// https://leetcode.cn/problems/valid-anagram/description/ class Solution { public:bool isAnagram(string s, string t) {if (s.length() != t.length()) {return false;}map<char, int> mp;for (int i = 0; i < s.length(); i ++) {char key = s[i];auto it = mp.find(key);if (it != mp.end()) {it->second += 1;} else {mp.insert(pair<char, int>(key, 1));}}for (int i = 0; i < t.length(); i ++) {char key = t[i];auto it = mp.find(key);if (it == mp.end()) {return false;} else {if (it->second == 0) {return false;} else if (it->second == 1) {mp.erase(it);} else {it->second -= 1;}}}return mp.empty();} };
- 最優(yōu)解法
// https://leetcode.cn/problems/valid-anagram/description/ class Solution { public:bool isAnagram(string s, string t) {if (s.length() != t.length()) {return false;}vector<int> mp(26, 0);for (char c : s) {mp[c - 'a'] ++;}for (char c : t) {mp[c - 'a'] --;}for (int c : mp) {if (c != 0) return false;}return true;} };
3.2 兩個(gè)數(shù)組的交集
- 代碼
// https://leetcode.cn/problems/intersection-of-two-arrays/ class Solution { public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;set<int> st;// 將nums1的所有元素添加到set中,會(huì)自動(dòng)去重for (int num : nums1) {st.insert(num);}// 遍歷nums2,判斷元素是否存在st中,存在則是兩個(gè)數(shù)組的交集,添加到結(jié)果數(shù)組ret中// 為防止元素重復(fù)添加,需要將其從st中移除for (int num : nums2) {if (st.find(num) != st.end()) {ret.push_back(num);st.erase(num);}}return ret;} };