合肥网站建设正规公司,wordpress 发布软件,怎样推广小程序,网站举报网文章目录 LeetCode#xff1a;双指针法正序同向而行#xff08;快慢指针#xff09;移除元素移动零#xff08;Hot 100#xff09;删除有序数组中的重复项颜色分类#xff08;Hot 100#xff09;压缩字符串移除链表元素删除排序链表中的重复元素删除排序链表中的重复元素… 文章目录 LeetCode双指针法正序同向而行快慢指针移除元素移动零Hot 100删除有序数组中的重复项颜色分类Hot 100压缩字符串移除链表元素删除排序链表中的重复元素删除排序链表中的重复元素 II反转链表 Hot 100删除链表的倒数第 N 个结点 Hot 100链表的中间结点K 个一组翻转链表 Hot 100排序链表 Hot 100 倒序同向而行合并两个有序数组Hot 100寻找两个正序数组的中位数Hot 100字符串相加反转字符串中的单词 相向而行有序数组的平方盛最多水的容器 (Hot100)接雨水 (Hot 100)三数之和 (Hot 100)反转字符串 滑动窗口无重复字符的最长子串Hot100)找到字符串中所有字母异位词Hot100)最小覆盖子串Hot100)滑动窗口最大值Hot100) LeetCode双指针法
双指针法通常是指使用两个指针相向而行或同向而行来遍历对象如数组、链表或字符串以避免多层循环从而降低算法的时间复杂度。
正序同向而行快慢指针
移除元素
移除元素
class Solution {
public:int removeElement(vectorint nums, int val) {int slow 0, fast 0; while (fast nums.size()) { if (nums[fast] ! val) { // fast_i没遇到目标值nums[slow] nums[fast]; // 保留 nums[fast]// slow和fast都前进一步slow; fast; }else{ // 遇到目标值slow不动fast前进一步fast; }}return slow; }
};简化代码
class Solution {
public:int removeElement(vectorint nums, int val) {int slow 0, fast 0; while (fast nums.size()) { if (nums[fast] ! val) { nums[slow] nums[fast]; }fast; }return slow;
}
};移动零Hot 100
移动零
class Solution {
public:void moveZeroes(vectorint nums) {int slow 0, fast 0;while (fast nums.size()) {if (nums[fast] ! 0) { // fast 指向非零数swap(nums[slow], nums[fast]); // 保留非零数slow; // slow和fast 都前进一步 }fast; // 指向零数 slow不动fast前进一步}}
};
删除有序数组中的重复项 删除有序数组中的重复项
class Solution {
public:int removeDuplicates(vectorint nums) {int fast 1, slow 1;while (fast nums.size()) {// fast 没指向重复项slow和fast都移动if (nums[fast] ! nums[fast - 1]) {nums[slow] nums[fast]; // 保留非重复项slow; // slow指向未保留的元素可能是要去除的元素}fast; // fast指向重复项则不让slow移动}return slow;}
};颜色分类Hot 100
颜色分类
class Solution {
public:void sortColors(vectorint nums) {int slow 0, fast 0;// 把0往前移while(fast nums.size()) {if (nums[fast] 0) {swap(nums[fast], nums[slow]);slow;}fast;}fast slow;// 把1往前移while(fast nums.size()) {if (nums[fast] 1) {swap(nums[fast], nums[slow]);slow;}fast;}}
};
压缩字符串
压缩字符串
class Solution {
public:int compress(vectorchar chars) {int slow 0;int fast 0;while(fast chars.size()){char cur chars[fast];int count 0; // 重复数量while(fast chars.size() chars[fast] cur){fast;count;}chars[slow] cur; // 记录当前字符if(count 1){ // 记录当前字符重复数量for(char c: to_string(count)) chars[slow] c;}}return slow;}
};移除链表元素
移除链表元素
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy_head new ListNode(0, head);ListNode* cur dummy_head;// 双指针cur和 cur.nextwhile(cur-next ! nullptr){if(cur-next-val ! val){cur cur-next;}else{cur-next cur-next-next;}}return dummy_head-next;}
};删除排序链表中的重复元素
删除排序链表中的重复元素
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (head nullptr) return head;// 第一个节点肯定不是重复元素ListNode* cur head;// 双指针cur和 cur.nextwhile(cur-next ! nullptr){if(cur-next-val ! cur-val){cur cur-next;}else{cur-next cur-next-next;}}return head;}
};删除排序链表中的重复元素 II
删除排序链表中的重复元素 II
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* hair new ListNode(0,head);ListNode* cur hair;while(cur-next cur-next-next){if(cur-next-next-val cur-next-val) // 数值val存在重复{int val cur-next-val; // 记录数值// 去掉cur-next之后所有值为val的节点while(cur-next cur-next-val val){ cur-next cur-next-next;}}else{cur cur-next;} }return hair-next;}
};反转链表 Hot 100
反转链表
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev nullptr;ListNode* cur head;while(cur){ListNode* temp cur-next;cur-next prev;prev cur;cur temp;}return prev;}
};删除链表的倒数第 N 个结点 Hot 100
删除链表的倒数第 N 个结点
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0, head);// 相邻节点fast slowListNode* fast head;ListNode* slow dummy;// 使得slow和fast之间的节点数为nfor (int i 0; i n; i) fast fast-next; // 同时移动slow和fast直到fast为nullptrwhile (fast) {fast fast-next;slow slow-next;}// 删除倒数第n个节点slow-next slow-next-next;return dummy-next;}
};链表的中间结点
链表的中间结点
class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* slow head;ListNode* fast head;while (fast ! nullptr fast-next ! nullptr) {// fast 速度是slow的两倍fast达到尾部时slow到达中间slow slow-next;fast fast-next-next;}return slow;}
};K 个一组翻转链表 Hot 100
K 个一组翻转链表 class Solution {
private:void reverseGroup(ListNode* head, ListNode* tail,int k){ListNode* pre nullptr;ListNode* cur head;for(int i 0 ; i k; i){ListNode* temp cur-next;cur-next pre;pre cur;cur temp;}}public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummy new ListNode(0,head);ListNode* tail dummy;while(head){ListNode* pre tail; for(int i 0 ;i k; i){tail tail-next;// 如果节点总数不是 k 的整数倍那么最后剩余的节点保持原有顺序。if(!tail) return dummy-next;}ListNode* temp tail-next;reverseGroup(head, tail, k);swap(head, tail); // 子链表头变成尾尾变成头// 把子链表重新接回原链表pre-next head;tail-next temp;head temp;}return dummy-next;}
};排序链表 Hot 100
排序链表
class Solution {
public:ListNode* sortList(ListNode* head) {if (head nullptr) return head;return sort(head, nullptr);}// 归并排序ListNode* sort(ListNode* head, ListNode* tail) {// 如果链表只有一个节点将其与后续节点断开并返回该节点if (head-next tail) {head-next nullptr;return head;}ListNode* slow head, *fast head;while (fast ! tail fast-next ! tail) {slow slow-next;fast fast-next-next;}ListNode* mid slow;return merge(sort(head, mid), sort(mid, tail));}// 升序合并ListNode* merge(ListNode* head1, ListNode* head2) {ListNode* dummyHead new ListNode(0);ListNode* temp dummyHead, *temp1 head1, *temp2 head2;while (temp1 ! nullptr temp2 ! nullptr) {if (temp1-val temp2-val) {temp-next temp1;temp1 temp1-next;} else {temp-next temp2;temp2 temp2-next;}temp temp-next;}if (temp1 ! nullptr) temp-next temp1; else if (temp2 ! nullptr) temp-next temp2;return dummyHead-next;}
};倒序同向而行
合并两个有序数组Hot 100
合并两个有序数组
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int i nums1.size() - 1;m--;n--;while(n 0){if(m 0 nums1[m] nums2[n]) nums1[i--] nums1[m--];else nums1[i--] nums2[n--]; }}
};寻找两个正序数组的中位数Hot 100
寻找两个正序数组的中位数
class Solution {
public:double findMedianSortedArrays(std::vectorint nums1, std::vectorint nums2) { std::vectorint merged; int i 0, j 0; int m nums1.size(), n nums2.size(); // 合并两个数组 while (i m j n) { if (nums1[i] nums2[j]) { merged.push_back(nums1[i]); } else { merged.push_back(nums2[j]); } } // 添加剩余的元素 while (i m) merged.push_back(nums1[i]); while (j n) merged.push_back(nums2[j]); int totalSize merged.size(); if (totalSize % 2 1) { // 奇数个元素中位数是中间的那个 return merged[totalSize / 2]; } else { // 偶数个元素中位数是中间两个数的平均值 return (merged[totalSize / 2 - 1] merged[totalSize / 2]) / 2.0; } }
};字符串相加
字符串相加
class Solution {
public:string addStrings(string num1, string num2) {int i num1.size() - 1;int j num2.size() - 1;int add 0;string result ;while(i 0 || j 0 || add 0){int x i 0 ? num1[i] - 0 : 0;int y j 0 ? num2[j] - 0 : 0;int val x y add;result.push_back(0 val % 10);add val / 10;i --; j--;}reverse(result.begin(), result.end());return result;}
};反转字符串中的单词
反转字符串中的单词
// https://leetcode.cn/problems/reverse-words-in-a-string/solutions/2361551/151-fan-zhuan-zi-fu-chuan-zhong-de-dan-c-yb1r/class Solution {
public:std::string reverseWords(std::string s) {std::vectorstd::string wordsVector; // 存储分割后的单词的向量int i, j;i s.size() - 1; // i 从字符串末尾开始向前扫描j i; // j 用于标记单词的尾字符索引while (i 0) {// 跳过单词间的空格while (i 0 s[i] ) i--;j i; // 更新单词的尾字符索引while (i 0 s[i] ! ) i--; // 找到单词前的空格// 将找到的单词添加到向量中注意要避免将空格作为单词存储if (i ! j) wordsVector.push_back(s.substr(i 1, (j - i)));}std::string result;// 将向量中的单词连接成一个字符串for (int n 0; n wordsVector.size(); n) {result wordsVector[n];if (n ! wordsVector.size() - 1) result ; // 添加单词间的空格}return result;}
};相向而行
有序数组的平方
有序数组的平方
class Solution {
public:vectorint sortedSquares(vectorint nums) {vectorint result(nums.size());int l 0;int r nums.size() - 1;int pos nums.size() - 1;// 非递减数组平方后数值由两侧向中间递减while(l r){// 左侧的值比右侧的值高if(nums[l] * nums[l] nums[r] * nums[r]){result[pos] nums[l] * nums[l];l; }else{ // 右侧的值比左侧的值高result[pos] nums[r] * nums[r];r--;}pos--;}return result;}
};盛最多水的容器 (Hot100)
盛最多水的容器
class Solution {
public:int maxArea(vectorint height) {int l 0;int r height.size() - 1;int result 0;while(l r){int capacity min(height[l],height[r])*(r -l);result max(result, capacity);// 宽度缩小尝试增大最小高度if(height[l] height[r]) l; else r--;}return result;}
};接雨水 (Hot 100)
接雨水
class Solution {
public:int trap(vectorint height) {int l 0;int r height.size() - 1;int ans 0;int left_max INT_MIN;int right_max INT_MIN;while(l r){left_max max(left_max, height[l]);right_max max(right_max, height[r]);if(height[l] height[r] ){ // 满足 height[l] height[r] 且 height[l] left_maxans left_max - height[l];l;}else{ans right_max - height[r];r--;}}return ans;}
};三数之和 (Hot 100)
三数之和
class Solution {
public:vectorvectorint threeSum(vectorint nums) { vectorvectorint result; // 对数组进行排序从左到右递增sort(nums.begin(), nums.end()); for (int i 0; i nums.size(); i) { // 跳过第一个数的重复元素以避免重复的三元组 // 保证i在相同值的最左这样left才可以取相同值if (i 0 nums[i] nums[i - 1]) continue; // a≤b≤c保证了只有 (a,b,c)这个顺序会被枚举到int left i 1; int right nums.size() - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) left; // 如果和小于0右移左指针尝试增大值 else if (sum 0) right--; // 如果和大于0左移右指针尝试较小值else { // 跳过第二个数的重复元素, 保证left为最右while (left right nums[left] nums[left 1]) left; // 跳过第三个数的重复元素, 保证left为最左while (left right nums[right] nums[right - 1]) right--; // 找到了一个和为0的组合 result.push_back({nums[i], nums[left], nums[right]}); // 继续寻找下一个组合left; right--; } } } return result; }
};反转字符串
反转字符串
class Solution {
public:void reverseString(vectorchar s) {int n s.size();int left 0, right n - 1;while (left right) {swap(s[left], s[right--]);}}
};滑动窗口
滑动窗口通过双指针实现一个指针右指针用于扩展窗口另一个指针左指针收缩窗口。与普通的双指针不同的是滑动窗口法的计算过程一般涉及双指针之间的值而不仅仅是两个指针指向的值。
无重复字符的最长子串Hot100)
无重复字符的最长子串
class Solution {
public:int lengthOfLongestSubstring(string s) {if (s.size() 0) return 0;unordered_setchar char_set; // 窗口内的字符int ans 0;int left 0;for (int right 0; right s.size(); right) {while (char_set.count(s[right]) ! 0) { // 重复了char_set.erase(s[left]);left; // left指向s[right]最后一次出现的地方的下一个位置}ans max(ans, right - left 1);char_set.insert(s[right]);}return ans;}
};
找到字符串中所有字母异位词Hot100)
找到字符串中所有字母异位词
class Solution {
public:vectorint findAnagrams(string s, string p) {int s_len s.size(), p_len p.size();if (s_len p_len) return vectorint();vectorint ans;// 存放字符串中字母(a-z)出现的词频vectorint s_count(26);vectorint p_count(26);// 当滑动窗口的首位在s[0]处时相当于放置滑动窗口进入数组for (int i 0; i p_len; i) {s_count[s[i] - a]; //记录s中前p_len个字母的词频p_count[p[i] - a]; //记录要寻找的字符串中每个字母的词频(只用进行一次来确定)}// 判断放置处是否有异位词if (s_count p_count) ans.push_back(0);//开始让窗口向右进行滑动,遍历起始索引for (int i 1; i s_len - p_len; i) { // 向右移动滑块相当于去掉左边第一个字符在右边加入一个字母--s_count[s[i - 1] - a]; // 左边去掉的字母的词频减1s_count[s[i p_len - 1] - a]; // 右边加入的字母的词频加1if (s_count p_count) { // 判断滑动后处是否有异位词ans.push_back(i);}}return ans;}
};最小覆盖子串Hot100)
最小覆盖子串
class Solution {
public:// 检查当前窗口是否覆盖目标字符串bool check(unordered_mapchar, int map_t,unordered_mapchar, int map_s) {for (const auto p : map_t) {if (map_s[p.first] p.second)return false;}return true;}string minWindow(string s, string t) {// 最小覆盖子串的起始位置和长度int ans_left -1, ans_len INT_MAX;// map_t记录目标字符串t中每个字符及其出现次数// map_s记录记录s在当前窗口内每个字符的出现次数unordered_mapchar, int map_t, map_s;// 初始化ori记录目标字符串t每个字符及其出现次数for (const auto c : t)map_t[c];// 窗口左右指针int left 0, right 0;// 向右扩大窗口直到右指针达到s末尾while (right int(s.size())) {// 将字符s[right]加入到map_s中if (map_t.find(s[right]) ! map_t.end())map_s[s[right]];// 当前窗口包含了目标字符串t中的所有字符时while (check(map_t, map_s) left right) {if (right - left 1 ans_len) { // 更新最小覆盖子串的起始位置和长度ans_len right - left 1;ans_left left;}// 将左指针指向的字符从cnt中移除if (map_t.find(s[left]) ! map_t.end())--map_s[s[left]];// 移动左指针缩小窗口left;}right; // 向右扩大窗口}// 如果ans_left仍为-1说明s中不存在包含t的子串返回空字符串// 否则返回从ans_left开始长度为len的子串return ans_left -1 ? string() : s.substr(ans_left, ans_len);}
};滑动窗口最大值Hot100)
滑动窗口最大值
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {if(nums.size() 0 || k 0) return {};dequeint deque; vectorint result(nums.size() - k 1);int left 1 - k,right 0;while(right nums.size()) {// 队列最前元素为nums[left-1]则删除if(left 0 deque.front() nums[left - 1]) deque.pop_front();// 单调队列 删除小于nums[right]的数保持 deque 递减while(!deque.empty() deque.back() nums[right]) deque.pop_back(); // 添加nums[right]deque.push_back(nums[right]);// 记录窗口最大值if(left 0) result[left] deque.front();left, right;}return result;}
};
