滑动窗口题

LC3 LC424
https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/fen-xiang-zhen-cang-de-shuang-zhi-zhen-m-fdsk/
首先需要区分两个概念：子串（子数组） 和 子序列。这两个名词经常在题目中出现，非常有必要加以区分。子串sub-string（子数组 sub-array）是连续的，而子序列 subsequence 可以不连续。

3. 无重复字符的最长子串

难度中等4905
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) {
  4.         int n = s.size();
  5.         int left = 0, right = 0;
  6.         int ans = 0;
  7.         unordered_set<char> mem;
  8.         while(right < n){
  9.             while(mem.count(s[right])){
  10.                 mem.erase(s[left]);
  11.                 left++;
  12.             }
  13.             ans = max(ans, right - left + 1);
  14.             mem.emplace(s[right]);
  15.             right ++;
  16.         }
  17.         return ans;
  18.     }
  19. };

424. 替换后的最长重复字符

难度中等281
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 104。

  1. class Solution {
  2. public:
  3.     int characterReplacement(string s, int k) {
  4.         int n = s.size();
  5.         int left = 0, right = 0;
  6.         int maxnow = 0;
  7.         int ans = 0;
  8.         vector<int> mem(26);
  9.         //右指针维护
  10.         while(right < n)
  11.         {
  12.             mem[s[right] - 'A'] ++ ;
  13.             maxnow = max(maxnow, mem[s[right] - 'A']);
  14.             //移动left到满足题目条件为止
  15.             //本题即是用总长度减去最大出现的数字个数
  16.             //令剩下数字的数量要小于k
  17.             while(right - left + 1 - maxnow > k){
  18.                 mem[s[left] - 'A'] --;
  19.                 left ++;
  20.             }
  21.             ans = max(ans, right - left + 1);
  22.             right ++;
  23.         }
  24.         return ans;
  25.     }
  26. };

以上两题大体模版相同 只在根据题意判断是否符合并且移动左指针时有所不同。

30. 串联所有单词的子串

难度困难409
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

  1. class Solution {
  2. public:
  3.     vector<int> findSubstring(string s, vector<string>& words) {
  4.         int n = s.size();
  5.         int word_len = words[0].size(), all_len = words.size();
  6.         vector<int> ans;
  7.         int left = 0, right;
  8.         //记录原words
  9.         unordered_map<string, int> mem;
  10.         for(auto& c: words)
  11.             mem[c] ++;
  12.         unordered_map<string, int> window;
  13.         for(int i = 0; i < word_len; ++ i){
  14.             while(left + word_len * all_len <= n){
  15.                 right = left;
  16.                 while(right <= n){
  17.                     if(mem == window){
  18.                         ans.push_back(left);
  19.                     }
  20.                     string ns = s.substr(right, word_len);
  21.                     window[ns] ++;
  22.                     //不存在或次数超过
  23.                     if(!mem.count(ns)) break;
  24.                     if(window[ns] > mem[ns]) break;
  25.                     right += word_len;
  26.                 }
  27.                 window.clear();
  28.                 left ++;
  29.             }
  30.         }
  31.         return ans;
  32.     }
  33. };

995. K 连续位的最小翻转次数

难度困难181
在仅包含 0 和 1 的数组 A 中，一次 _K_ 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

示例 1：
输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：
输入：A = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：
输入：A = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
提示：

  1. 1 <= A.length <= 30000
  2. 1 <= K <= A.length

双指针包括快慢指针和左右指针，其实滑动窗口也是一种双指针，但是几种方法的适用情况都不同。

  1. class Solution {
  2. public:
  3.     int minKBitFlips(vector<int>& A, int K) {
  4.         int n = A.size();
  5.         int ans = 0;
  6.         int right = 0;
  7.         //用队列来模拟滑动窗口
  8.         //存的是下标，表示的是哪些位置（在k范围内）进行翻转
  9.         //那么队列的大小n就表示了前k个单位中要翻转几次
  10.         //那么n为偶数时当前的数就等于没有翻转，为奇数则翻转
  11.         queue<int> que;
  12.         while(right < n){
  13.             //无法再翻转，或者过了要翻转的数字距离
  14.             if(!que.empty() && right >= que.front() + K)
  15.                 que.pop();
  16.             //综合得出的结论，要翻转，记录
  17.             if(que.size() % 2 == A[right]){
  18.                 if(right + K > n)
  19.                     return -1;
  20.                 que.push(right);
  21.                 ans ++;
  22.             }
  23.             right ++;
  24.         }
  25.         return ans;
  26.     }
  27. };

剑指 Offer II 015. 字符串中的所有变位词

  1. class Solution {
  2. public:
  3.     vector<int> findAnagrams(string s, string p) {
  4.         vector<int> ans;
  5.         int sLen = s.size(), pLen = p.size();
  6.         if(sLen < pLen){
  7.             return {};
  8.         }
  9.         vector<int> sCount(26, 0);
  10.         vector<int> pCount(26, 0);
  11.         for(int i = 0; i < pLen; ++ i){
  12.             sCount[s[i] - 'a'] ++;
  13.             pCount[p[i] - 'a'] ++;
  14.         }
  15.         if(sCount == pCount){
  16.             ans.push_back(0);
  17.         }
  18.         for(int i = 0; i < sLen - pLen; ++ i){
  19.             sCount[s[i] - 'a'] --;
  20.             sCount[s[i + pLen] -'a'] ++;
  21.             if(sCount == pCount){
  22.                 ans.push_back(i + 1);
  23.             }
  24.         }
  25.         return ans;
  26.     }
  27. };

双指针题

左右指针：

11. 盛最多水的容器

难度中等2235
给你 n 个非负整数 a1，a2，...，a``n，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。

示例 1：
字符串-双指针/滑动窗口 - 图1
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2

提示：

  • n = height.length
  • 2 <= n <= 3 * 104
  • 0 <= height[i] <= 3 * 104
    1. class Solution {
    2. public:
    3.   int maxArea(vector<int>& height) {
    4.       int res = 0;
    5.       int n = height.size();
    6.       int left = 0, right = n - 1;
    7.       while(left < right){
    8.           int high = min(height[left], height[right]);
    9.           int width = right - left;
    10.           res = max(res, high * width);
    11.           if(height[left] == high){
    12.               left ++;
    13.           }else{
    14.               right --;
    15.           }
    16.           //好像不是很能找到滑动的情况
    17.           // if(height[left] == high){
    18.           //     left ++;
    19.           // }
    20.       }
    21.       return res;
    22.   }
    23. };

    15. 三数之和

    难度中等3030
    给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 _a + b + c = _0 ？请你找出所有和为 0 且不重复的三元组。
    注意：答案中不可以包含重复的三元组。

    示例 1：
    输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]
    示例 2：
    输入：nums = []
    输出：[]
    示例 3：
    输入：nums = [0]
    输出：[]
    1. class Solution {
    2. public:
    3.   vector<vector<int>> threeSum(vector<int>& nums) {
    4.       int n = nums.size();
    5.       vector<vector<int> > ans;
    6.       if(n < 2) return ans;
    7.       sort(nums.begin(), nums.end());
    8.       for(int i = 0; i < n - 2; ++ i){
    9.           if(nums[i] > 0)break;
    10.           if(i > 0 && nums[i] == nums[i - 1]) continue;
    11.           int low = i + 1, high = n - 1;
    12.           while(low < high){
    13.               int temp = nums[i] + nums[low] + nums[high];
    14.               if(temp == 0){
    15.                   ans.push_back({nums[i], nums[low], nums[high]});
    16.                   while(low < high && nums[low] == nums[low + 1]) low ++;
    17.                   while(low < high && nums[high] == nums[high - 1]) high --;
    18.                   low ++;
    19.                   high --;
    20.               }
    21.               if(temp < 0) low ++;
    22.               if(temp > 0) high --;
    23.           }
    24.       }
    25.       return ans;
    26.   }
    27. };

75. 颜色分类

难度中等801
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]

  1. class Solution {
  2. public:
  3.     void sortColors(vector<int>& nums) {
  4.         int n = nums.size();
  5.         int p0 = 0, p2 = n - 1;
  6.         int i = 0;
  7.         while(i <= p2){
  8.             if(nums[i] == 0){
  9.                 swap(nums[i], nums[p0]);
  10.                 p0 ++;
  11.                 //这里必须要i++, 因为p0必然是1，如果是2的话已经被换再i后面了，这点是可以保证的
  12.                 i ++;
  13.             }else if(nums[i] == 1){
  14.                 i ++;
  15.             }else{
  16.                 swap(nums[i], nums[p2]);
  17.                 p2 --;
  18.                 //这里不要i++ 因为我们只能保证nums[i] == 2,但是不能保证nums[p2] == 1
  19.             }
  20.         }
  21.     }
  22. };

141. 环形链表

难度简单986
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：**pos** 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：
你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：
字符串-双指针/滑动窗口 - 图2
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
字符串-双指针/滑动窗口 - 图3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
字符串-双指针/滑动窗口 - 图4
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。


提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105

  • pos 为 -1 或者链表中的一个 有效索引 。

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode(int x) : val(x), next(NULL) {}
    7. * };
    8. */
    9. class Solution {
    10. public:
    11.   bool hasCycle(ListNode *head) {
    12.       if(!head || !head->next){
    13.           return false;
    14.       }
    15.       ListNode* slow = head;
    16.       ListNode* quick = head->next;
    17.       while(slow != quick){
    18.           if(!quick || !quick->next){
    19.               return false;
    20.           }
    21.           slow = slow->next;
    22.           quick = quick->next->next;
    23.       }
    24.       return true;
    25.   }
    26. };

    142. 环形链表 II

    难度中等912
    给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，**pos** 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
    说明：不允许修改给定的链表。
    进阶：

  • 你是否可以使用 O(1) 空间解决此题？


    示例 1：
    字符串-双指针/滑动窗口 - 图5
    输入：head = [3,2,0,-4], pos = 1
    输出：返回索引为 1 的链表节点
    解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
字符串-双指针/滑动窗口 - 图6
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
字符串-双指针/滑动窗口 - 图7
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。


提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引
    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode(int x) : val(x), next(NULL) {}
    7. * };
    8. */
    9. class Solution {
    10. public:
    11.   ListNode *detectCycle(ListNode *head) {
    12.       if(head == nullptr){
    13.           return nullptr;
    14.       }
    15.       ListNode* slow = head;
    16.       ListNode* fast = head;
    17.       while(fast != nullptr){
    18.           slow = slow->next;
    19.           if(fast->next == nullptr){
    20.               return nullptr;
    21.           }
    22.           fast = fast->next->next;
    23.           if(slow == fast){
    24.               //利用公式a = c + (n - 1)(b + c)
    25.               ListNode* p = head;
    26.               while(p != slow){
    27.                   p = p->next;
    28.                   slow = slow->next;
    29.               }
    30.               return slow;
    31.           }
    32.       }
    33.       return nullptr;
    34.   }
    35. };