class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
for (int i = 0; i < nums.size(); i++) {
while (!q.empty() && q.front() <= i - k)
q.pop_front();
while (!q.empty() && nums[q.back()] <= nums[i])
q.pop_back();
q.push_back(i);
if (i >= k - 1)
ans.push_back(nums[q.front()]);
}
return ans;
}
private:
deque<int> q;
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i++) {
if (h.find(target - nums[i]) != h.end())
return {h[target - nums[i]], i};
h[nums[i]] = i;
}
return {};
}
private:
// <值, 下标>
unordered_map<int, int> h;
};
class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
unordered_set<long long> obs;
for (const vector<int>& obstacle : obstacles) {
obs.insert(calc(obstacle));
}
int x = 0, y = 0;
int dir = 0;
int ans = 0;
for (int& command : commands) {
if (command == -2)
dir = (dir + 3) % 4;
else if (command == -1)
dir = (dir + 1) % 4;
else {
for (int i = 0; i < command; i++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (obs.find(calc({nx, ny})) != obs.end()) break;
x = nx;
y = ny;
}
}
ans = max(ans, x * x + y * y);
}
return ans;
}
private:
long long calc(const vector<int>& obstacle) {
return (obstacle[0] + 3e4) * (6e4 + 1) + obstacle[1] + 3e4;
}
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
};
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
for (string& str : strs) {
string copy = str;
sort(copy.begin(), copy.end());
groups[copy].push_back(str);
}
vector<vector<string>> ans;
for (const pair<string, vector<string>>& group : groups) {
ans.push_back(group.second);
}
return ans;
}
private:
unordered_map<string, vector<string>> groups;
};
-
30. 串联所有单词的子串 - 力扣（LeetCode）
O(MN*ls)
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
int tot = 0;
for (string& word : words) {
tot += word.length();
wordMap[word]++;
}
vector<int> ans;
k = words[0].length();
for (int i = 0; i + tot <= s.length(); i++) {
if (isValid(s.substr(i, tot)))
ans.push_back(i);
}
return ans;
}
private:
unordered_map<string, int> wordMap;
int k;
bool isValid(const string& str) {
unordered_map<string, int> splitMap;
for (int i = 0; i + k <= str.length(); i+= k) {
splitMap[str.substr(i, k)]++;
}
return equalsMap(wordMap, splitMap);
}
bool equalsMap(unordered_map<string, int>& a, unordered_map<string, int>& b) {
for (auto& kv : a) {
const string& key = kv.first;
int val = kv.second;
if (b.find(key) == b.end() || b[key] != val)
return false;
}
for (auto& kv : b) {
const string& key = kv.first;
int val = kv.second;
if (a.find(key) == a.end() || a[key] != val)
return false;
}
return true;
}
};
O(N*ls)
class Solution {
public:
vector<int> findSubstring(string &s, vector<string> &words) {
// 存储结果的数组
vector<int> res;
// 单词数量、单词长度、字符串 s 的长度
int m = words.size(), n = words[0].size(), ls = s.size();
// 外层循环，从每个可能的起始位置 i 开始
for (int i = 0; i < n && i + m * n <= ls; ++i) {
// 用于统计当前窗口内单词的出现次数 与 words 中的差异
unordered_map<string, int> differ;
// 统计从当前起始位置 i 开始的 m 个单词
for (int j = 0; j < m; ++j)
// 将子串加入到 differ 中并计数
++differ[s.substr(i + j * n, n)];
// 遍历 words 中的每个单词，从 differ 中减去
for (string &word: words)
// 此处如若differ中不存在word，则插入时其值为负数
// 如果单词的计数减为 0，则从 differ 中删除
if (--differ[word] == 0)
differ.erase(word);
// 内层循环，从起始位置 i 开始滑动窗口
for (int start = i; start < ls - m * n + 1; start += n) {
if (start != i) {
// 添加新进入窗口的单词到 differ 中
string newWord = s.substr(start + (m - 1) * n, n);
// 由于differ的值中存在负数，所以++后会出现0
if (++differ[newWord] == 0)
differ.erase(newWord);
// 移除窗口左侧移出的单词
string oldWord = s.substr(start - n, n);
if (--differ[oldWord] == 0)
differ.erase(oldWord);
}
// 如果 differ 为空，表示当前窗口符合要求，将起始位置加入结果数组 res
if (differ.empty())
res.push_back(start);
}
}
return res;
}
};
class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
head = new Node();
tail = new Node();
head->next = tail;
tail->pre = head;
}
int get(int key) {
if (map.find(key) == map.end()) return -1;
Node* node = map[key];
remove(node);
insert(node);
return node->value;
}
void put(int key, int value) {
if (map.find(key) == map.end()) {
Node* node = new Node();
node->key = key;
node->value = value;
map[key] = node;
insert(node);
if (map.size() > capacity) {
Node* node = tail->pre;
map.erase(node->key);
remove(node);
}
}
else {
Node* node = map[key];
remove(node);
insert(node);
node->value = value;
}
}
private:
struct Node {
int key;
int value;
Node* pre;
Node* next;
};
Node* head;
Node* tail;
int capacity;
unordered_map<int, Node*> map;
void remove(Node* node) {
node->pre->next = node->next;
node->next->pre = node->pre;
}
void insert(Node* node) {
node->next = head->next; head->next->pre = node;
head->next = node; node->pre = head;
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
1.头部删除
2.随机访问每个元素
3.中间删除
*/
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
// 原问题：子段的奇数数量
// 新问题：奇数看作0，偶数看作1，统计子段和为k的子段数量
// 即 s[r] - s[l-1] == k
// 两数之差问题
int n = nums.size();
vector<int> preSum(n + 1);
preSum[0] = 0;
for (int i = 1; i <= n; i++)
preSum[i] = preSum[i - 1] + nums[i - 1] % 2;
vector<int> count(n + 1);
count[preSum[0]]++;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (preSum[i] - k >= 0)
ans += count[preSum[i] - k];
count[preSum[i]]++;
}
return ans;
}
};
