赞
踩
滑动窗口算法是在可以利用单调性使用“同向双指针”来解决问题时使用。
int minSubArrayLen(int target, vector<int>& nums)
{
size_t left = 0;
size_t right = 0;
long long sum = 0;
int len = nums.size() + 1;
while(right < nums.size())
{
sum += nums[right]; // 进窗口
while (sum >= target)
{
// 更新结果
if (right - left + 1 < len)
{
len = right - left + 1;
}
sum -= nums[left++]; // 出窗口
}
++right;
}
return len == nums.size() + 1 ? 0 : len;
}
int lengthOfLongestSubstring(string s)
{
char arr[256];
memset(arr, 0, 256);
size_t len = 0;
for(size_t left = 0, right = 0; right < s.size(); ++right)
{
++arr[s[right]]; // 进窗口
while(arr[s[right]] > 1) // 判断
{
--arr[s[left++]]; // 出窗口
}
if(right - left + 1 > len ) len = right - left + 1; // 更新结果
}
return len;
}
int longestOnes(vector<int>& nums, int k)
{
size_t left = 0;
size_t right = 0;
size_t len = 0;
while(right < nums.size())
{
if(nums[right] != 0)
{
if(len < right - left + 1) len = right - left + 1;
}
else
{
if(k > 0)
{
if(len < right - left + 1) len = right - left + 1;
--k;
}
else
{
while (nums[left++] != 0);
}
}
++right;
}
return len;
}
int minOperations(vector<int>& nums, int x)
{
size_t sum = 0;
for(int e : nums) sum += e;
x = sum - x;
if(x == 0) return nums.size();
size_t left = 0;
size_t right = 0;
sum = 0;
size_t len = 0;
while(right < nums.size())
{
sum += nums[right]; // 进窗口
while(sum > x) // 判断
{
sum -= nums[left];
++left; // 出窗口
}
if(sum == x && len < right - left + 1) len = right - left + 1; // 更新结果
++right;
}
return len == 0 ? -1 : nums.size() - len;
}
struct Basket
{
int type = -1;
int num = 0;
};
class Solution {
public:
int totalFruit(vector<int>& fruits)
{
size_t left = 0;
size_t right = 0;
int max = 0;
Basket basket[2];
while(right < fruits.size())
{
// 如果有空篮子或水果类型相同,就入窗口
if(basket[0].type == -1 || basket[0].type == fruits[right])
{
basket[0].type = fruits[right];
basket[0].num++;
if(max < basket[0].num + basket[1].num) max = basket[0].num + basket[1].num;
}
else if(basket[1].type == -1 || basket[1].type == fruits[right])
{
basket[1].type = fruits[right];
basket[1].num++;
if(max < basket[0].num + basket[1].num) max = basket[0].num + basket[1].num;
}
else
{
while(true)
{
if(basket[0].type == fruits[left])
{
++left;
--basket[0].num;
if(basket[0].num == 0)
{
basket[0].type = fruits[right];
basket[0].num++;
break;
}
}
else if(basket[1].type == fruits[left])
{
++left;
--basket[1].num;
if(basket[1].num == 0)
{
basket[1].type = fruits[right];
basket[1].num++;
break;
}
}
}
}
++right;
}
return max;
}
};
vector<int> findAnagrams(string s, string p)
{
vector<int> v;
if(s.size() < p.size()) return v;
int count = 0; // 记录相同的有效元素的个数
int hash_p[26];
memset(hash_p, 0, 26 * sizeof(int));
for(char c : p) hash_p[c - 'a']++;
int hash_s[26];
memset(hash_s, 0, 26 * sizeof(int));
for(size_t i = 0; i < p.size(); ++i)
if(hash_s[s[i] - 'a']++ < hash_p[s[i] - 'a']) ++count;
size_t left = 0;
size_t right = p.size() - 1;
while(right < s.size())
{
if(count == p.size()) v.push_back(left);
if (hash_s[s[left] - 'a']-- <= hash_p[s[left] - 'a']) --count;
++left;
if(++right < s.size() && hash_s[s[right] - 'a']++ < hash_p[s[right] - 'a']) ++count;
}
return v;
}
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> v;
if (s.size() < words.size() * words[0].size()) return v;
// words的hash
unordered_map<string, int> m_wd;
for (string& s : words) m_wd[s]++;
// s的hash
unordered_map<string, int> m_s;
// 步长step
size_t step = words[0].size();
// 有效元素个数count
size_t count = 0;
// words的单词合并长度
size_t words_length = words.size() * words[0].size();
// 回归坐标index
// 只需要滑动窗口step步长次即可
for (size_t index = 0; index < step; ++index)
{
m_s.clear();
count = 0;
for (size_t i = index, size = 0; i < s.size() && size < words.size(); i += step, ++size)
{
string tmp = s.substr(i, step);
if (m_wd.count(tmp) && m_s[tmp]++ < m_wd[tmp])
{
++count;
}
}
size_t left = index, right = left + words_length;
while (right <= s.size())
{
if (count == words.size())
{
v.push_back(left);
}
string tmp_left = s.substr(left, step);
if (m_wd.count(tmp_left) && m_s[tmp_left]-- <= m_wd[tmp_left])
{
--count;
}
left += step;
right += step;
if (right <= s.size())
{
string tmp_right = s.substr(right - step, step);
if (m_wd.count(tmp_right) && m_s[tmp_right]++ < m_wd[tmp_right])
{
++count;
}
}
}
}
return v;
}
string minWindow(string s, string t)
{
string ret = s;
if (s.size() < t.size()) return "";
unordered_map<char, int> t_map;
for (char c : t) t_map[c]++;
unordered_map<char, int> s_map;
size_t count = 0;
size_t left = 0, right = 0;
while (right < s.size() && count < t.size())
{
if (t_map.count(s[right]) && s_map[s[right]]++ < t_map[s[right]])
{
++count;
}
++right;
}
if (right == s.size())
{
if (count < t.size())
{
return "";
}
else
{
// 到达临界点
while (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]])
{
s_map[s[left]]--;
++left;
}
return s.substr(left, right - left);
}
}
while (right < s.size())
{
if (count == t.size())
{
// 到达临界点
while (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]])
{
s_map[s[left]]--;
++left;
}
if (count == t.size() && ret.size() > right - left) ret = s.substr(left, right - left);
// 出窗口
s_map[s[left]]--;
++left;
--count;
}
while (right < s.size() && count < t.size())
{
if (t_map.count(s[right]) && s_map[s[right]]++ < t_map[s[right]]) // 元素存在且小于
{
++count;
}
++right;
}
}
// 到达临界点
while (left < right && (!t_map.count(s[left]) || s_map[s[left]] > t_map[s[left]]))
{
s_map[s[left]]--;
++left;
}
if (count == t.size() && ret.size() > right - left) ret = s.substr(left, right - left);
return ret;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。