企业网站建设采购,wordpress无法重定向,计算机最吃香的职业,简单的手机网站模板下载文章目录 参考资料一 数组1.1 二分查找1.2 移除元素1.3 长度最小的子数组1.4 螺旋矩阵1.5 在排序数组中查找元素的第一个和最后一个位置 二 链表2.1 移除链表元素2.2 设计链表2.3 反转链表2.4 两两交换链表中的节点2.5 删除链表的倒数第N个节点2.6 链表相交2.7 环形链表II 三 哈… 文章目录 参考资料一 数组1.1 二分查找1.2 移除元素1.3 长度最小的子数组1.4 螺旋矩阵1.5 在排序数组中查找元素的第一个和最后一个位置 二 链表2.1 移除链表元素2.2 设计链表2.3 反转链表2.4 两两交换链表中的节点2.5 删除链表的倒数第N个节点2.6 链表相交2.7 环形链表II 三 哈希表3.1 有效的字母异位词3.2 两个数组的交集 参考资料
代码随想录 https://programmercarl.com/ LeetCode https://leetcode.cn/
一 数组
1.1 二分查找
前提 有序数组元素唯一有重复元素使用二分查找法返回的元素下标可能不是唯一思想 定义 target 是在一个在左闭右闭的区间里也就是[left, right]while (left right) 要使用 因为left right是有意义的所以使用 if (nums[middle] target) right 要赋值为 middle - 1因为当前这个nums[middle]一定不是target那么接下来要查找的左区间结束下标位置就是 middle - 1若要通过二分查找确定插入位置则最后需判断nums[mid] target若是则mid为结果若不是则mid 1为结果 代码// https://leetcode.cn/problems/binary-search/description/
class Solution {public:int search(vectorint 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)空间不要求保留原顺序思想 将要删除的元素用数组最后面的元素进行替换代码// https://leetcode.cn/problems/remove-element/description/
class Solution {public:int removeElement(vectorint 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]为需要保留的元素长度位right 1return right 1;}
};1.3 长度最小的子数组
前提 O(1)空间子数组连续思想 定义区间[left, right)当区间和sum target时移动right相反则记录当前区间长度right - left并移动left直到right 数组总长度时结束循环代码// https://leetcode.cn/problems/minimum-size-subarray-sum/description/
class Solution {public:int minSubArrayLen(int target, vectorint nums) {int left 0, right 0; // [left, right)int sum 0, ans 0;while (right nums.size()) {if (sum target) {// 此时right指针已达到末尾且子数组和小于target// 结束循环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 螺旋矩阵
思想 关键在于方向的转换并且需要记录行和列上还有多少是没有遍历过的每次方向转换都需要减少一个待遍历的行或列代码// https://leetcode.cn/problems/spiral-matrix-ii/description/
class Solution {
public:vectorvectorint 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;// 初始化结果vectorvectorint res;for (int i 0; i n; i ) {vectorint 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 在排序数组中查找元素的第一个和最后一个位置
代码// https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorint ret(2, -1);// 有效区间[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;}}// 向右找到第一个等于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;}}// 向左找到第一个等于target的元素while (nums[to] ! target) to --;ret[0] from;ret[1] to;return ret;}
};二 链表
2.1 移除链表元素
思想 移除链表中指定元素的关键在于找到被移除元素的上一个节点代码// https://leetcode.cn/problems/remove-element/description/
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 定义虚拟头节点不需要对第一个节点进行特殊判断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 设计链表
思想 设计虚拟头节点可以简化对于第一个节点的操作由题可知大部分操作都需要找到下标的为index的节点的上一个节点因此设计了getPre(int index)函数设计尾节点可以降低addAtTail的时间复杂度但是在链表变化时需要对其进行维护 代码// 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;// 找到下标为index的上一个节点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 比长度更大该节点将 不会插入 到链表中if (index size) {return ;}// 如果 index 等于链表的长度那么该节点会被追加到链表的末尾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);// 要删除的节点为尾节点需要修改tailif (p-next tail) {p-next NULL;tail p;} else {p-next p-next-next; }size --;}
};2.3 反转链表
思想 为原链表添加虚拟头节点删除节点时不需要维护头节点简化操作新链表的虚拟头节点同理反转链表主要分为节点断开和节点接入分为两部分实现可避免思路不清晰导致链表成环q-next NULL可删除 代码// https://leetcode.cn/problems/reverse-linked-list/
class Solution {
public:ListNode* reverseList(ListNode* head) {// 为原链表添加虚拟头节点方便节点的删除ListNode *dummy_head new ListNode(-1, head);ListNode *p dummy_head;// 为新链表添加虚拟头节点ListNode *new_head new ListNode(-1);while (p-next ! NULL) {// 把节点从原链表断开ListNode *q p-next;p-next q-next;q-next NULL;// 把节点接入到新链表的头部q-next new_head-next;new_head-next q;}return new_head-next;}
};2.4 两两交换链表中的节点
思想 多定义变量可一定程度上简化操作变量不用 代码// 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为要进行交换的节点c为后面的节点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 删除链表的倒数第N个节点
思想 先让fast跑n步然后slow和fast再一起跑fast到达末尾时slow刚好为倒数第n1个节点代码// 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) {// 计算链表A和B的节点数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;}// 若两个链表相差sub个节点则让长的链表先跑sub步while (a_count b_count) {headA headA-next;a_count --;}while (b_count a_count) {headB headB-next;b_count --;}// 两个链表同时往前此时遇到的第一个相同节点即为结果while (headA ! headB) {headA headA-next;headB headB-next;}return headA;}
};2.7 环形链表II
思想 通过快慢指针法确定链表是否存在环并找到环中的任意一个节点遍历环直至将环中的所有节点添加到set集合中从head开始遍历当节点存在与set集合中时即为环的入口节点 代码// https://leetcode.cn/problems/linked-list-cycle-ii/
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) {// 此时fast和slow都是环中的节点遍历环直至将环中的所有节点添加到set集合中setListNode* st;while (st.find(fast) st.end()) {st.insert(fast);fast fast-next;}// 从head开始遍历当节点存在与set集合中时即为环的入口节点while (st.find(head) st.end()) {head head-next;}return head;} else {return NULL;}}
};最优解法// 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 有效的字母异位词
思想 两个字符串长度不同直接返回false遍历字符串s使用map统计第一个字符串s中每各字符出现的次数遍历字符串t若字符不存在于map中则返回false存在则进行减操作当字符次数减为0时从map移除map为空则表示两个字符串是字母异位词进阶由于题目中说明字符串都由小写字母组成那么我们可以将所有字符映射到长度为26的数组简化操作 代码基础解法// https://leetcode.cn/problems/valid-anagram/description/
class Solution {
public:bool isAnagram(string s, string t) {if (s.length() ! t.length()) {return false;}mapchar, 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(pairchar, 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();}
};最优解法// https://leetcode.cn/problems/valid-anagram/description/
class Solution {
public:bool isAnagram(string s, string t) {if (s.length() ! t.length()) {return false;}vectorint 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 两个数组的交集
代码// https://leetcode.cn/problems/intersection-of-two-arrays/
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {vectorint ret;setint st;// 将nums1的所有元素添加到set中会自动去重for (int num : nums1) {st.insert(num);}// 遍历nums2判断元素是否存在st中存在则是两个数组的交集添加到结果数组ret中// 为防止元素重复添加需要将其从st中移除for (int num : nums2) {if (st.find(num) ! st.end()) {ret.push_back(num);st.erase(num);}}return ret;}
};
