链表
- 🍁 链表
-
- 🍄 PCN指针
-
- 🌸 25. K个一组反转链表 [PSEN区间] [PCN指针]
- 🌸 61. 旋转链表 [PSEN区间] [PCN指针]
- 🌸 92. 链表的区间反转 [PSEN区间] [PCN指针]
- 🌸 143. 重排链表 [P12指针] [CP12指针] [PCN指针]
- 🌸 206. 反转链表 [PCN指针]
- 🌸 234. 回文链表 [P12指针] [PCN指针]
- 🍄 CP12指针
-
- 🌸 2. 链表相加 [CP12指针]
- 🌸 21. 合并两个有序链表 [CP12指针]
- 🌸 23. 合并 K 个有序链表 [优先队列] [等效CP12指针]
- 🌸 86. 分隔链表 [CP12指针]
- 🌸 142. 环形链表 [P12指针]
- 🌸 160. 链表相交 [P12指针]
- 🍄 RW指针
-
- 🌸 82. 删除有序链表中的重复元素 [RW指针]
- 🍁 矩阵
-
- 🍄 二分法
-
- 10.09. 排序矩阵查找 [二分法]
- 🌸 双指针
-
- 🍻 数组
-
- 🍻 两数之和 II – 输入有序数组 [有序数组] > [子序列和] > (合并指针)
- 🍻 删除有序数组中的重复项 [有序数组] > [去重] > (读写指针)
- 🍻 移除元素 [数组] > [去值] > (读写指针)
- 🍻 移动零 [数组] > [去值] > (读写指针)
- 🍻 字符串
-
- 🍻 反转字符串 [字符串] > [反转] > (合并指针)
- 🍻 最长回文子串 [字符串] > [回文子串] > (扩散指针)
- 🍻 反转字符串中的单词 [字符串] > [单词匹配] > (窗口指针)
- 🍻 无重复字符的最长子串 [字符串] > [无重子串匹配] > (窗口指针) > (哈希表)
- 🍻 找到字符串中所有字母异位词 [字符串] > [异位词匹配] > (窗口指针) > (哈希表)
- 🍻 字符串的排列 [字符串] > [子串匹配] > (窗口指针) > (哈希表)
- 🍻 最小覆盖子串 [字符串] > [子串匹配] > (窗口指针) > (哈希表)
- 🍻 重复的DNA序列 [字符串] > [重复子串寻找] > (窗口指针) > (哈希表) > (KMP算法)
- 🍻 找出字符串中第一个匹配项的下标 [字符串] > [子串匹配] > (窗口指针) > (KMP算法)
- 🍺 二分法
-
- 🍻 框架
-
- 🍻 寻找元素
- 🍻 寻找元素边界
- 🍻 线性函数
- 🍻 数组
-
- 🍻 二分查找 [有序数组] > [寻找元素] > (二分法)
- 🍻 在排序数组中查找元素的第一个和最后一个位置 [有序数组] > [寻找元素边界] > (二分法)
- 🍻 在 D 天内送达包裹的能力 [线性函数] > [寻找元素边界] > (二分法)
- 🍻 分割数组的最大值 [线性函数] > [寻找元素边界] > (二分法)
- 🍻 爱吃香蕉的珂珂 [线性函数] > [寻找元素边界] > (二分法)
- 🍺 前缀和
-
- 🍻 数组
-
- 🥂 [笔试]. 平均数为 K 的最长连续子数组 (区间均值) (区间长度) (区间和) (前缀和) (哈希表 PRE, IDX)
- 🥂 560. 和为 K 的子数组 (区间和) (区间个数) (前缀和) (哈希表 PRE, NUM)
- 🍻 区域和检索 – 数组不可变 [数组] > [区间和] > (前缀和)
- 🍻 矩阵
-
- 🍻 二维区域和检索 – 矩阵不可变 [矩阵] > [子矩阵和] > (前缀和)
- 🍺 差分
-
- 🍻 数组
-
- 🍻 拼车 [数组] > [区间叠加和] > (差分)
- 🍻 航班预订统计 [数组] > [区间叠加和] > (差分)
🍁 链表
🍄 PCN指针
🌸 25. K个一组反转链表 [PSEN区间] [PCN指针]
题目：给定一个链表，{1，2，3，4}变为{2，1，4，3}，k 为 2。
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1); dummy->next = head;
ListNode* pre = dummy, * end = dummy;
while (end->next != nullptr) {
for (int i = 0; i < k && end != nullptr; ++i) {
end = end->next;
}
if (end == nullptr) break;
// [PRE] >> [START] >> [NODE] >> [END] >> [NEXT] >> [NODE]
ListNode* start = pre->next, * next = end->next;
end->next = nullptr;
pre->next = reverse(start);
start->next = next;
pre = start;
end = start;
}
return dummy->next;
}
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr, * cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
🌸 61. 旋转链表 [PSEN区间] [PCN指针]
题目：给定一个链表，旋转。
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1);
dummy->next = reverse(head);
int size = 0;
ListNode* cur = dummy->next;
while (cur != nullptr) {
++size;
cur = cur->next;
}
if (size <= 1) return head;
k = k % size;
// [DUMMY/PRE] >> [START] >> [NODE] >> [END] >> [NEXT] >> [NODE]
ListNode* pre = dummy, * end = dummy;
for (int i = 0; i < k; ++i) end = end->next;
ListNode* start = pre->next, * next = end->next;
// 防止 K 为 0 的情况发生
if (start == next) return reverse(start);
// [PRE] >> [START] >> [NODE] >> [END] || [NEXT] >> [NODE]
end->next = nullptr;
// [PRE] >> [END] >> [NODE] >> [START] || [NODE] >> [NEXT]
pre->next = reverse(start);
start->next = reverse(next);
return dummy->next;
}
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr, * cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
🌸 92. 链表的区间反转 [PSEN区间] [PCN指针]
题目：给定一个链表，进行区间反转。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(-1); dummy->next = head;
ListNode* pre = dummy, * end = dummy;
// [NODE] >> [PRE] >> [START] >> [NODE] >> [END] >> [NEXT]
for (int i = 0; i < left - 1; ++i) pre = pre->next;
for (int j = 0; j < right; ++j) end = end->next;
ListNode* start = pre->next, * next = end->next;
// [NODE] >> [PRE] >> [START] >> [NODE] >> [END] || [NEXT]
end->next = nullptr;
// [NODE] >> [PRE] >> [END] >> [NODE] >> [START] || [NEXT]
pre->next = reverse(start);
// [NODE] >> [PRE] >> [END] >> [NODE] >> [START] >> [NEXT]
start->next = next;
return dummy->next;
}
// 链表反转
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr, * cur = head;
while (cur != nullptr) {
// [PRE] >> [CUR] >> [NEXT]
ListNode* next = cur->next;
// [PRE] << [CUR] >> [NEXT]
cur->next = pre;
// [NULL] << [PRE] << [CUR]
pre = cur;
cur = next;
}
// [NODE] << [PRE] << [NULL]
return pre;
}
};
🌸 143. 重排链表 [P12指针] [CP12指针] [PCN指针]
题目：给定一个链表，{1，2，3，4，5} 变为{1，5，2，4，3}
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* dummy = new ListNode(-1); dummy->next = head;
// 找到中点拆成两半
ListNode* p1 = dummy, * p2 = dummy;
while (p2 != nullptr && p2->next != nullptr) {
p1 = p1->next;
p2 = p2->next->next;
}
// 反转链表
p2 = reverse(p1->next);
p1->next = nullptr;
p1 = dummy->next;
// 合并链表
ListNode* cur = dummy;
while (p1 != nullptr && p2 != nullptr) {
cur->next = p1;
p1 = p1->next;
cur = cur->next;
cur->next = p2;
p2 = p2->next;
cur = cur->next;
}
if (p1 != nullptr) cur->next = p1;
}
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr, * cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
🌸 206. 反转链表 [PCN指针]
题目：给定一个链表，进行全部反转。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr, * cur = head;
while (cur != nullptr) {
// [PRE] >> [CUR] >> [NEXT]
ListNode* next = cur->next;
// [PRE] << [CUR] >> [NEXT]
cur->next = pre;
// [NULL] << [PRE] << [CUR]
pre = cur;
cur = next;
}
// [NODE] << [PRE] << [NULL]
return pre;
}
};
🌸 234. 回文链表 [P12指针] [PCN指针]
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* dummy = new ListNode(-1); dummy->next = head;
ListNode *p1 = dummy, *p2 = dummy;
// [1, 2, 3]: 2 [1, 2, 3, 4]: 2
while (p2!= nullptr && p2->next != nullptr) {
p1 = p1->next;
p2 = p2->next->next;
}
ListNode* newHead = reverse(p1->next);
p1 = head, p2 = newHead;
while (p2 != nullptr) {
if (p1->val != p2->val) return false;
p1 = p1->next;
p2 = p2->next;
}
return true;
}
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr, * cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
🍄 CP12指针
🌸 2. 链表相加 [CP12指针]
题目：给定两个链表相加，如 {2, 4, 3} + {5, 6, 4} = {7, 0, 8}。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* p1, ListNode* p2) {
ListNode* dummy = new ListNode(-1), * cur = dummy;
int carry = 0;
while (p1 != nullptr || p2 != nullptr) {
int x = p1 != nullptr ? p1->val : 0;
int y = p2 != nullptr ? p2->val : 0;
int sum = x + y + carry;
// 判断相加是否大于等于 10
carry = sum / 10;
sum = sum % 10;
// 创建节点
ListNode* node = new ListNode(sum);
cur->next = node;
cur = cur->next;
if (p1 != nullptr) p1 = p1->next;
if (p2 != nullptr) p2 = p2->next;
}
// 剩余还有进位
if (carry == 1) cur->next = new ListNode(1);
return dummy->next;
}
};
🌸 21. 合并两个有序链表 [CP12指针]
题目：给定两个有序链表，合并。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* p1, ListNode* p2) {
ListNode* dummy = new ListNode(-1), * cur = dummy;
while (p1 != nullptr && p2 != nullptr) {
if (p1->val < p2->val) { // 取出 p1
cur->next = p1;
p1 = p1->next;
} else { // 取出 p2
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
// 拼接剩余的
if (p1 != nullptr) cur->next = p1;
if (p2 != nullptr) cur->next = p2;
return dummy->next;
}
};
🌸 23. 合并 K 个有序链表 [优先队列] [等效CP12指针]
题目：给定 K 个有序链表，合并。
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* dummy = new ListNode(-1), * cur = dummy;
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
// 依次把节点放入 pq
for (auto list : lists) {
if (list != nullptr) pq.push(list);
}
// 每次取出一个，移动一个
while (!pq.empty()) {
ListNode* node = pq.top(); pq.pop();
cur->next = node;
cur = cur->next;
if (node->next != nullptr) pq.push(node->next);
}
return dummy->next;
}
struct cmp {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
};
🌸 86. 分隔链表 [CP12指针]
题目：给定一个链表，分成大于 x 和小于 x 两部分
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
// 两条链表分别存放大于 x 和小于 x 的数
ListNode* dummy1 = new ListNode(-1), * cur1 = dummy1;
ListNode* dummy2 = new ListNode(-1), * cur2 = dummy2;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* node = cur;
cur = cur->next;
if (node->val < x) {
cur1->next = node;
cur1 = cur1->next;
} else {
cur2->next = node;
cur2 = cur2->next;
}
}
// 拼接起来，并且将 dummy2 的末尾置空。
cur1->next = dummy2->next;
cur2->next = nullptr;
return dummy1->next;
}
};
🌸 142. 环形链表 [P12指针]
题目：判断链表是否有环，且返回环的交点
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr) return head;
ListNode* dummy = new ListNode(-1); dummy->next = head;
ListNode* p1 = dummy, * p2 = dummy;
while (p2 != nullptr) {
p1 = p1->next;
if (p2->next != nullptr) p2 = p2->next->next;
else p2 = p2->next;
// p1 p2 相遇, 一定有环
if (p1 == p2) break;
}
// 此时 P2 为空, 一定无环
if (p2 == nullptr) return nullptr;
// 如果 p2 不为空，找环
p1 = dummy;
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
🌸 160. 链表相交 [P12指针]
题目：给定两个链表，判断他们是否相交
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* p1 = headA, * p2 = headB;
while (p1 != p2) {
if (p1 == nullptr) p1 = headB;
else p1 = p1->next;
if (p2 == nullptr) p2 = headA;
else p2 = p2->next;
}
return p1;
}
};
🍄 RW指针
🌸 82. 删除有序链表中的重复元素 [RW指针]
题目：比如{1，2，3，3，4，4，5} >> {1，2，5}
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(-1); dummy->next = head;
ListNode* read = head, * write = dummy;
while (read != nullptr) {
// 找到一个非重复节点
while (read->next != nullptr && read->val == read->next->val) {
read = read->next;
}
if (write->next == read) { // WRITE 和 READ 相邻，肯定无重复节点
write = read;
} else { // WRITE 和 READ 不相邻，肯定有重复节点
write->next = read->next;
}
read = read->next;
}
return dummy->next;
}
};
🍁 矩阵
🍄 二分法
10.09. 排序矩阵查找 [二分法]
题目：给定一个排序的矩阵，找到 target。
思路：一层一层的二分查找，注意过滤无用的行。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size() == 0) return false;
for (auto& nums : matrix) {
if (nums[0] > target || nums[nums.size() - 1] < target) continue;
if (search(nums, target) != -1) return true;
}
return false;
}
int search(vector<int>& nums, int target) {
// [LEFT, RIGHT)
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
// [LEFT, MID) [MID] [MID + 1, RIGHT)
if (nums[mid] > target) right = mid;
else if (nums[mid] < target) left = mid + 1;
else return mid;
}
return -1;
}
};
🌸 双指针
🍻 数组
🍻 两数之和 II – 输入有序数组 [有序数组] > [子序列和] > (合并指针)
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size() - 1;
// 二分查找
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum > target) {
// 减少最大值
right--;
} else if (sum < target) {
// 增加最小值
left++;
} else {
// 找到
return {left, right};
}
}
return {};
}
};
🍻 删除有序数组中的重复项 [有序数组] > [去重] > (读写指针)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int write = 1, read = 1;
while (read < nums.size()) {
if (nums[read] != nums[write - 1]) {
// 读取的内容不重复, 写入, 读写移动
nums[write++] = nums[read++];
} else {
// 读取的内容重复, 读移动
read++;
}
}
}
};
🍻 移除元素 [数组] > [去值] > (读写指针)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int write = 0, read = 0;
while (read < nums.size()) {
if (nums[read] != val) {
// 无需去除, 写入新值
nums[write++] = nums[read++];
} else {
// 去除
read++;
}
}
return write;
}
};
🍻 移动零 [数组] > [去值] > (读写指针)
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int write = 0, read = 0;
while (read < nums.size()) {
if (nums[read] != 0) {
// 无需去除, 写入新值
nums[write++] = nums[read++];
} else {
// 去除
read++;
}
}
// 剩余位置补0
while (write < nums.size()) {
nums[write++] = 0;
}
}
};
🍻 字符串
🍻 反转字符串 [字符串] > [反转] > (合并指针)
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0, right = s.size() - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++, right--;
}
}
};
🍻 最长回文子串 [字符串] > [回文子串] > (扩散指针)
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int max_num = 1;
string res = s.substr(0, 1);
// 奇数情况
for (int i = 0; i < n; ++i) {
int left = i - 1, right = i + 1;
string s1 = getSub(s, left, right);
if (s1.size() > max_num) {
max_num = s1.size();
res = s1;
}
}
// 偶数情况
for (int i = 0; i < n - 1; ++i) {
int left = i, right = i + 1;
string s2 = getSub(s, left, right);
if (s2.size() > max_num) {
max_num = s2.size();
res = s2;
}
}
return res;
}
string getSub(string s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--, right++;
}
return s.substr(left + 1, right - left - 1);
}
};
🍻 反转字符串中的单词 [字符串] > [单词匹配] > (窗口指针)
class Solution {
public:
string reverseWords(string s) {
string res = "";
int n = s.size();
int i = 0, j = n - 1;
while (s[i] == ' ') i++;
while (s[j] == ' ') j--;
s = s.substr(i, j - i + 1);
// 滑动
n = s.size();
i = n - 1, j = n - 1;
while (i >= 0) {
// 找到第一个空格
while (i >= 0 && s[i] != ' ') i--;
res += s.substr(i + 1, j - i) + " ";
// 找到下一个非空格
while (i >= 0 && s[i] == ' ') i--;
j = i;
}
// 去掉多余的空格
return res.substr(0, res.size() - 1);
}
};
🍻 无重复字符的最长子串 [字符串] > [无重子串匹配] > (窗口指针) > (哈希表)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> umap; // 滑动窗口
int n = s.size();
int res = 0; // 存放结果
int left = 0, right = 0; // 窗口边界
while (right < n) {
char cur_r = s[right++]; // 取当前字符串
umap[cur_r]++; // 更新窗口内容
// 判断是否该缩小窗口, 目的是 hash 中无出现 2 次的元素
while (umap[cur_r] > 1) {
char cur_l = s[left++];
umap[cur_l]--;
}
res = max(res, right - left);
}
return res;
}
};
🍻 找到字符串中所有字母异位词 [字符串] > [异位词匹配] > (窗口指针) > (哈希表)
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int left = 0, right = 0, valid = 0;
vector<int> res;
// 当前窗口内容, 满足需要的内容
unordered_map<char, int> window, need;
for (auto ch : p) {
need[ch]++;
}
// 开始滑动
while (right < s.size()) {
char ch = s[right++];
if (need.count(ch)) {
window[ch]++;
if (window[ch] == need[ch]) {
valid++;
}
}
// 左边界
while (right - left == p.size()) {
if (valid == need.size()) {
res.push_back(left);
}
// 左移
char ch = s[left++];
if (need.count(ch)) {
if (window[ch] == need[ch]) {
valid--;
}
window[ch]--;
}
}
}
return res;
}
};
🍻 字符串的排列 [字符串] > [子串匹配] > (窗口指针) > (哈希表)
class Solution {
public:
bool checkInclusion(string s1, string s2) {
// 当前窗口内容, 满足需要的内容
unordered_map<char, int> window, need;
for (auto ch : s1) {
need[ch]++;
}
int left = 0, right = 0, valid = 0;
// 开始滑动
while (right < s2.size()) {
char ch = s2[right++];
if (need.count(ch)) {
window[ch]++;
if (window[ch] == need[ch]) {
valid++;
}
}
// 左边界
while (right - left == s1.size()) {
if (valid == need.size()) {
return true;
}
// 左移
char ch = s2[left++];
if (need.count(ch)) {
if (need[ch] == window[ch]) {
valid--;
}
window[ch]--;
}
}
}
return false;
}
};
🍻 最小覆盖子串 [字符串] > [子串匹配] > (窗口指针) > (哈希表)
class Solution {
public:
string minWindow(string s, string t) {
int left = 0, right = 0;
int start = 0, len = INT_MAX;
// 统计符合条件的字符数
int valid = 0;
unordered_map<char, int> window, need;
for (auto ch : t) {
need[ch]++;
}
// 开滑
while (right < s.size()) {
char ch = s[right++];
if (need.count(ch)) {
window[ch]++;
if (window[ch] == need[ch]) {
valid++;
}
}
// 缩小
while (left <= right && valid == need.size()) {
// 更新最优子串
if (right - left < len) {
start = left;
len = right - left;
}
// 移动左边界
char ch = s[left++];
if (need.count(ch)) {
if (window[ch] == need[ch]) {
valid--;
}
window[ch]--;
}
}
}
if (len == INT_MAX) {
return "";
} else {
return s.substr(start, len);
}
}
};
🍻 重复的DNA序列 [字符串] > [重复子串寻找] > (窗口指针) > (哈希表) > (KMP算法)
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
// 将字符串映射为数字数组
vector<int> nums(s.size());
for (int i = 0; i < s.size(); ++i) {
switch (s[i]) {
case 'A':
nums[i] = 0;
break;
case 'G':
nums[i] = 1;
break;
case 'C':
nums[i] = 2;
break;
case 'T':
nums[i] = 3;
break;
}
}
// 滑动窗口, 找相同的数字
int left = 0, right = 0;
// 进制, 数字长度
int R = 4, L = 10, RL = pow(R, L - 1);
int windowHash = 0;
// 已经出现的字符串的哈希值
unordered_set<int> seen;
// 记录重复出现的字符串, 用 set 去重
unordered_set<string> res;
// 开始滑动窗口
while (right < nums.size()) {
windowHash = windowHash * R + nums[right++];
if (right - left == L) {
if (seen.count(windowHash)) {
res.insert(s.substr(left, right - left));
} else {
seen.insert(windowHash);
}
// 缩小窗口, 左边界移动
windowHash = windowHash - nums[left] * RL;
left++;
}
}
return vector<string>(res.begin(), res.end());
}
};
🍻 找出字符串中第一个匹配项的下标 [字符串] > [子串匹配] > (窗口指针) > (KMP算法)
class Solution {
public:
int strStr(string haystack, string needle) {
// 长度, 进制, 最大位权值, 模
int L = needle.size(), R = 256, RL = 1;
int Q = 61111;
for (int i = 0; i < L - 1; ++i) {
RL = RL * R % Q;
}
// 计算目标值的哈希
int hashN = 0;
for (int i = 0; i < needle.size(); ++i) {
hashN = (hashN * R + int(needle[i])) % Q;
}
// 寻找哈希值相同的数
int left = 0, right = 0;
int hashW = 0;
while (right < haystack.size()) {
hashW = (hashW * R % Q + int(haystack[right++]) % Q) % Q;
// 判断是否满足条件
if (right - left == L) {
if (hashW == hashN) {
if (haystack.substr(left, right - left) == needle) {
return left;
}
}
// 缩窗口, 因为 hashW - RL*s[left] 可能为负数, +Q 确保不为负
hashW = (hashW - int(haystack[left]) * RL % Q + Q) % Q;
left++;
}
}
return -1;
}
};
🍺 二分法
🍻 框架
🍻 寻找元素
int find(vector<int>& nums, int target) {
int left = 0, right = nums.size();
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
// 如果存在目标值，则左右边界确定不了
// 如果不存在目标值，则 left == right == [target_idx]
return -1;
}
🍻 寻找元素边界
int find_left(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = nums.size();
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 如果数组中存在目标，则 left == right == [观测索引]
// 如果数组中不存在目标，则 left == right == [观测索引]
if (left < 0 || left >= n || nums[left] != target) left = -1;
return left;
}
int find_right(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = nums.size();
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
// 如果数组中存在目标，则 left == right == [观测索引] + 1
// 如果数组中不存在目标，则 left == right == [观测索引]
if (right - 1 < 0 || right - 1 >= n || nums[right - 1] != target) right = 0;
return right - 1;
}
🍻 线性函数
// 单调递减函数
int func(vector<int>& nums, int x);
int find_left(vector<int>& nums, int x) {
int n = nums.size();
int left = x_left, right = x_right;
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (func(nums, mid) > target) {
left = mid + 1;
} else {
right = mid;
}
}
// 如果查找的元素存在，则 left == right == [target_idx]
return left;
}
int find_right(vector<int>& nums, int x) {
int n = nums.size();
int left = x_left, right = x_right;
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (func(nums, mid) > target) {
left = mid + 1;
} else {
right = mid;
}
}
// 如果查找的元素存在，则 left == right == [target_idx] + 1
return right - 1;
}
🍻 数组
🍻 二分查找 [有序数组] > [寻找元素] > (二分法)
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size();
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
// left = right = [target_idx] + 1
cout << left << " " << right << endl;
return -1;
}
};
🍻 在排序数组中查找元素的第一个和最后一个位置 [有序数组] > [寻找元素边界] > (二分法)
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = find_left(nums, target);
int right = find_right(nums, target);
return {left, right};
}
int find_left(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = nums.size();
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 如果数组中存在目标，则 left == right == [观测索引]
// 如果数组中不存在目标，则 left == right == [观测索引]
if (left < 0 || left >= n || nums[left] != target) left = -1;
return left;
}
int find_right(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = nums.size();
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
// 如果数组中存在目标，则 left == right == [观测索引] + 1
// 如果数组中不存在目标，则 left == right == [观测索引]
if (right - 1 < 0 || right - 1 >= n || nums[right - 1] != target) right = 0;
return right - 1;
}
};
🍻 在 D 天内送达包裹的能力 [线性函数] > [寻找元素边界] > (二分法)
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
return find_left(weights, days);
}
// 运送量为 x 时, 天数 f(x) 为多少
int func(vector<int>& weights, int x) {
int day = 0;
int sum = 0;
for (int i = 0; i < weights.size(); ++i) {
sum += weights[i];
if (sum <= x) continue;
if (sum > x) {
day++;
sum = weights[i];
}
}
if (sum > 0) day++;
return day;
}
int find_left(vector<int>& nums, int target) {
int n = nums.size();
int max_num = *max_element(nums.begin(), nums.end());
int left = max_num, right = 500 * n;
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (func(nums, mid) > target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};
🍻 分割数组的最大值 [线性函数] > [寻找元素边界] > (二分法)
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
return find_left(nums, k);
}
// 当每次可以装 x 时，需要分成几份
int func(vector<int>& nums, int x) {
int k = 0;
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
if (sum <= x) continue; // 还可以装，不分
if (sum > x) { // 装不下了，划分下一次装
k++;
sum = nums[i];
}
}
if (sum > 0) k++; // 最后一车
return k;
}
int find_left(vector<int>& nums, int target) {
int max_num = *max_element(nums.begin(), nums.end());
int left = max_num, right = max_num * nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (func(nums, mid) > target) {
left = mid + 1;
} else if (func(nums, mid) <= target) {
right = mid;
}
}
return left;
}
};
🍻 爱吃香蕉的珂珂 [线性函数] > [寻找元素边界] > (二分法)
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
return find_left(piles, h);
}
// 吃香蕉函数
long func(vector<int>& nums, int K) {
int H = 0;
for (auto num : nums) {
H += num / K;
if (num % K != 0) {
H++;
}
}
return H;
}
int find_left(vector<int>& nums, int x) {
int n = nums.size();
long left = 1, right = 10e9;
// [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (func(nums, mid) > x) {
left = mid + 1;
} else {
right = mid;
}
}
// 如果查找的元素存在，则 left == right == [target_idx]
return left;
}
};
🍺 前缀和
🍻 数组
🥂 [笔试]. 平均数为 K 的最长连续子数组 (区间均值) (区间长度) (区间和) (前缀和) (哈希表 PRE, IDX)
1. 求满足 nums[i] 到 nums[j] 的均值为 K 的连续子区间
2. 将所有元素减 K，等价于求满足 nums[i] 到 nums[j] 的区间和为 0 的连续子区间
3. 定义一个哈希表，表示 {前缀和 preSum[i], 前缀和等于 preSum[i] 的索引}
4. 如果前缀和第一次出现，则添加
5. 如果前缀和第二次出现，则将其与先前的前缀下标计算区间距离
// pre[j] - pre[i] = 0, i < j, j = cur
// pre[j] = pre[i], i < j, j = cur
class Solution {
public:
void maxLen(vector<long>& nums, long mean) {
int size = nums.size();
unordered_map<long, long> preSum; // 前缀和数组 (前缀和, 索引)
long res = 0, cur_sum = 0;
// 构建新数组
for (auto& num : nums) num -= mean;
// 构造前缀和数组
preSum[0] = 0;
for (int i = 0; i < size; ++i) {
cur_sum += nums[i];
// 找到有出现过
if (preSum.find(cur_sum) != preSum.end()) {
max_len = max(max_len, i + 1 - preSum[cur_sum]);
} else {
preSum[cur_sum] = i + 1;
}
}
if (res == 0) res = -1;
cout << res;
}
};
🥂 560. 和为 K 的子数组 (区间和) (区间个数) (前缀和) (哈希表 PRE, NUM)
1. 求从 nums[i] 到 nums[j] 的区间和为 K 的区间个数
2. 等效于求 preSum[j] - preSum[i] == K 的区间个数
3. 将 j 从 0 到 size 遍历，依次求 i 中满足 preSum[preSum[j] - K] 的个数
4. 定义一个哈希表，表示 {前缀和 preSum[i], 前缀和等于 preSum[i] 的个数}
5. 将这和符合条件的个数累加起来，得到结果
// pre[j] - pre[i] = k, i < j
// pre[i] = pre[j] - k, i < j, j = cur
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int size = nums.size();
int cur_sum = 0;
int count = 0;
unordered_map<int, int> prefixSum; // [前缀和, i 满足次数]
prefixSum[0] = 1;
for (int i = 0; i < size; ++i) {
cur_sum += nums[i];
// 找有前缀和为 sum - k 的 i
if (prefixSum.find(cur_sum - k) != prefixSum.end()) {
count += prefixSum[cur_sum - k];
}
// 更新 j 的前缀和数组
prefixSum[cur_sum]++;
}
return count;
}
};
🍻 区域和检索 – 数组不可变 [数组] > [区间和] > (前缀和)
class NumArray {
private:
vector<int> nums;
vector<int> preSum;
public:
NumArray(vector<int>& nums) {
this->nums = nums;
preSum.resize(nums.size());
preSum[0] = nums[0];
for (int i = 1; i < preSum.size(); ++i) {
preSum[i] = preSum[i - 1] + nums[i];
}
}
int sumRange(int left, int right) {
return preSum[right] - preSum[left] + nums[left];
}
};
🍻 矩阵
🍻 二维区域和检索 – 矩阵不可变 [矩阵] > [子矩阵和] > (前缀和)
class NumMatrix {
private:
vector<vector<int>> matrix;
vector<vector<int>> preSum;
public:
NumMatrix(vector<vector<int>>& matrix) {
this->matrix = matrix;
int m = matrix.size(), n = matrix[0].size();
preSum = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i < m + 1; ++i) {
for (int j = 1; j < n + 1; ++j) {
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1]
- preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1]
- preSum[row1][col2 + 1] + preSum[row1][col1];
}
};
🍺 差分
🍻 数组
🍻 拼车 [数组] > [区间叠加和] > (差分)
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
int start = INT_MAX, end = 0;
// 寻找边界
for (auto trip : trips) {
if (trip[1] < start) start = trip[1];
if (trip[2] > end) end = trip[2];
}
int len = end - start + 1;
vector<int> diff(len);
vector<int> res(len);
// 因为到站了下车, 所以应该在 diff[to] 处减, 而不是 diff[to+1]
for (auto trip : trips) {
diff[trip[1] - start] += trip[0]; // 上车
diff[trip[2] - start] -= trip[0]; // 下车
}
// 计算柱状图
res[0] = diff[0];
if (res[0] > capacity) return false;
for (int i = 1; i < end - start + 1; ++i) {
res[i] = res[i - 1] + diff[i];
if (res[i] > capacity) return false;
}
return true;
}
};
🍻 航班预订统计 [数组] > [区间叠加和] > (差分)
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
int start = 1, end = n;
vector<int> diff(n); // 差分
vector<int> res(n); // 叠加
for (auto book : bookings) {
diff[book[0] - start] += book[2];
if (book[1] < n) {
diff[book[1] - start + 1] -= book[2];
}
}
res[0] = diff[0];
for (int i = 1; i < n; ++i) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
};
版权声明：本文为博主作者：進擊的小老虎原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/qq_39547794/article/details/135620915
