xcode动态改变窗口大小_有点难度，几道和「滑动窗口」有关的算法面试题

前言科普&＃xff1a;什么是滑动窗口算法

滑动问题包含一个滑动窗口&＃xff0c;它是一个运行在一个大数组上的子列表&＃xff0c;该数组是一个底层元素集合。

假设有数组 [a b c d e f g h ]&＃xff0c;一个大小为 3 的 滑动窗口 在其上滑动&＃xff0c;则有&＃xff1a;

[a b c] [b c d] [c d e] [d e f] [e f g] [f g h]

一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动&＃xff0c;同时 动态地 记录一些有用的数据&＃xff0c;很多情况下&＃xff0c;能够极大地提高算法地效率。

1. 滑动窗口最大值

题目来源于 LeetCode 上第 239 号问题&＃xff1a;滑动窗口最大值。题目难度为 Hard&＃xff0c;目前通过率为 40.5% 。

给定一个数组 nums&＃xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。

返回滑动窗口最大值。

示例:

输入: nums &＃61; [1,3,-1,-3,5,3,6,7], 和 k &＃61; 3输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7题目解析

利用一个 双端队列&＃xff0c;在队列中存储元素在数组中的位置&＃xff0c; 并且维持队列的严格递减,&＃xff0c;也就说维持队首元素是 **最大的 **&＃xff0c;当遍历到一个新元素时, 如果队列里有比当前元素小的&＃xff0c;就将其移除队列&＃xff0c;以保证队列的递减。当队列元素位置之差大于 k&＃xff0c;就将队首元素移除。

Deque 的含义是 “double ended queue”&＃xff0c;即双端队列&＃xff0c;它具有队列和栈的性质的数据结构。顾名思义&＃xff0c;它是一种前端与后端都支持插入和删除操作的队列。

Deque 继承自 Queue(队列)&＃xff0c;它的直接实现有 ArrayDeque、LinkedList 等。

动画描述 Made by Jun Chen

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { //有点坑&＃xff0c;题目里都说了数组不为空&＃xff0c;且 k > 0。但是看了一下&＃xff0c;测试用例里面还是有nums &＃61; [], k &＃61; 0&＃xff0c;所以只好加上这个判断 if (nums &＃61;&＃61; null || nums.length (); for (int i &＃61; 0; i &＃61; k - 1) { res[i - k &＃43; 1] &＃61; nums[deque.getFirst()]; } } return res; }}

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

题目来源于 LeetCode 上第 3 号问题&＃xff1a;无重复字符的最长子串。题目难度为 Medium&＃xff0c;目前通过率为 29.0% 。

给定一个字符串&＃xff0c;请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"&＃xff0c;所以其长度为 3。题目解析

建立一个256位大小的整型数组 freg &＃xff0c;用来建立字符和其出现位置之间的映射。

维护一个滑动窗口&＃xff0c;窗口内的都是没有重复的字符&＃xff0c;去尽可能的扩大窗口的大小&＃xff0c;窗口不停的向右滑动。

• (1)如果当前遍历到的字符从未出现过&＃xff0c;那么直接扩大右边界&＃xff1b;
• (2)如果当前遍历到的字符出现过&＃xff0c;则缩小窗口(左边索引向右移动)&＃xff0c;然后继续观察当前遍历到的字符&＃xff1b;
• (3)重复(1)(2)&＃xff0c;直到左边索引无法再移动&＃xff1b;
• (4)维护一个结果res&＃xff0c;每次用出现过的窗口大小来更新结果 res&＃xff0c;最后返回 res 获取结果。

动画描述

// 滑动窗口// 时间复杂度: O(len(s))// 空间复杂度: O(len(charset))class Solution {public: int lengthOfLongestSubstring(string s) { int freq[256] &＃61; {0}; int l &＃61; 0, r &＃61; -1; //滑动窗口为s[l...r] int res &＃61; 0; // 整个循环从 l &＃61;&＃61; 0; r &＃61;&＃61; -1 这个空窗口开始 // 到l &＃61;&＃61; s.size(); r &＃61;&＃61; s.size()-1 这个空窗口截止 // 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值 while(l

3. 存在重复元素 II

题目来源于 LeetCode 上第 219 号问题&＃xff1a;存在重复元素 II。题目难度为 Easy&＃xff0c;目前通过率为 33.9% 。

题目描述

给定一个整数数组和一个整数 k&＃xff0c;判断数组中是否存在两个不同的索引 i 和 j&＃xff0c;使得 nums [i] &＃61; nums [j]&＃xff0c;并且 i 和 j 的差的绝对值最大为 k。

示例 1:

输入: nums &＃61; [1,2,3,1], k &＃61; 3输出: true

示例 2:

输入: nums &＃61; [1,0,1,1], k &＃61; 1输出: true

示例 3:

输入: nums &＃61; [1,2,3,1,2,3], k &＃61; 2输出: false题目解析

使用用滑动窗口与查找表来解决。

• 设置查找表record&＃xff0c;用来保存每次遍历时插入的元素&＃xff0c;record的最大长度为k
• 遍历数组nums&＃xff0c;每次遍历的时候在record查找是否存在相同的元素&＃xff0c;如果存在则返回true&＃xff0c;遍历结束
• 如果此次遍历在record未查找到&＃xff0c;则将该元素插入到record中&＃xff0c;而后查看record的长度是否为k &＃43; 1
• 如果此时record的长度是否为k &＃43; 1&＃xff0c;则删减record的元素&＃xff0c;该元素的值为nums[i - k]
• 如果遍历完整个数组nums未查找到则返回false

动画描述

动画描述

代码实现

// 时间复杂度: O(n)// 空间复杂度: O(k)class Solution {public: bool containsNearbyDuplicate(vector& nums, int k) { if(nums.size() <&＃61; 1) return false; if(k <&＃61; 0) return false; unordered_set record; for(int i &＃61; 0 ; i

4. 长度最小的子数组

题目来源于 LeetCode 上第 209 号问题&＃xff1a;长度最小的子数组。题目难度为 Medium&＃xff0c;目前通过率为 37.7% 。

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s &＃xff0c;找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组&＃xff0c;返回 0。

示例:

输入: s &＃61; 7, nums &＃61; [2,3,1,2,4,3]输出: 2解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。题目解析

定义两个指针 left 和 right &＃xff0c;分别记录子数组的左右的边界位置。

• (1)让 right 向右移&＃xff0c;直到子数组和大于等于给定值或者 right 达到数组末尾&＃xff1b;
• (2)更新最短距离&＃xff0c;将 left 像右移一位, sum 减去移去的值&＃xff1b;
• (3)重复(1)(2)步骤&＃xff0c;直到 right 到达末尾&＃xff0c;且 left 到达临界位置

动画描述

设置滑动窗口的长度为 0 &＃xff0c;位于数轴的最左端。

1 .滑动窗口右端 R 开始移动&＃xff0c;直到区间满足给定的条件&＃xff0c;也就是和大于 7 &＃xff0c;此时停止于第三个元素 2&＃xff0c;当前的最优长度为 4

图 1

2. 滑动窗口左端 L 开始移动&＃xff0c;缩小滑动窗口的大小&＃xff0c;停止于第一个元素 3&＃xff0c;此时区间和为 6&＃xff0c;使得区间和不满足给定的条件(此时不大于 7)

图片 2

3. 滑动窗口右端 R 继续移动&＃xff0c;停止于第四个元素 4&＃xff0c;此时和位 10 &＃xff0c;但最优长度仍然为 4

图片 3

代码实现

// 滑动窗口的思路// 时间复杂度: O(n)// 空间复杂度: O(1)class Solution { public int minSubArrayLen(int s, int[] nums) { int l&＃61; 0,r &＃61; -1; // nums[l...r]为我们的滑动窗口 int sum &＃61; 0; int result &＃61; nums.length &＃43; 1; while (l &＃61; s){ result &＃61; (r-l&＃43;1)