目录
哈希
两数之和
要找出和为target的两个元素，用哈希查找表存储数组元素x，看看有没有target-x的元素在就行了
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashMap;
for (int i = 0; i < nums.size(); ++i) {
auto ans = hashMap.find(target - nums[i]);
if (ans != hashMap.end()) {
return {ans->second, i};
}
hashMap[nums[i]] = i;
}
return {};
}
};字母异位词分组
排序完后相同的即为一组
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hash;
for (auto& str : strs) {
string key = str;
sort(key.begin(), key.end());
hash[key].emplace_back(move(str));
}
vector<vector<string>> ans;
for (auto&& it = hash.begin(); it != hash.end(); ++it) {
ans.emplace_back(move(it->second));
}
return ans;
}
};最长连续序列
用哈希表存储数组的元素，key是元素，value是元素对应连续序列的长度，对于元素x，如果x-1存在哈希表中，map[x]应该就等于map[x-1]+1，如果x+1存在的话，map[x]应该就等于map[x+1]+1，如果x-1和x+1都存在的话，map[x]应该就等于map[x-1]+map[x+1]+1，并且还需要更新这个连续序列两端对应的value
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> hash;
int ans = 0;
for (auto& num : nums) {
if (hash.find(num) == hash.end()) {
// + smaller
int leftOffset = 0;
auto smaller = hash.find(num - 1);
if (smaller != hash.end()) {
leftOffset = smaller->second;
}
// + bigger
int rightOffset = 0;
auto bigger = hash.find(num + 1);
if (bigger != hash.end()) {
rightOffset = bigger->second;
}
hash[num - leftOffset] = hash[num + rightOffset] = hash[num] =
leftOffset + rightOffset + 1;
ans = max(hash[num], ans);
}
}
return ans;
}
};双指针
移动零
反过来思考，移动非零的元素，剩下的改成0
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int zeroes = -1;
for (auto& num : nums) {
if (num) {
nums[++zeroes] = num;
}
}
for(int i=zeroes+1;i<nums.size();++i){
nums[i] = 0;
}
}
};盛最多水的容器
容量的计算长乘于宽，从两端开始计算容量，宽只能缩短，所以容量的增大必须要找到更高的柱子
所以每次换掉短的那根柱子
class Solution {
public:
int maxArea(vector<int>& height) {
int ans = 0, left = 0, right = height.size() - 1;
while(left<right){
ans=max(ans,min(height[left],height[right])*(right-left));
if(height[left]<height[right]){
++left;
}else{
--right;
}
}
return ans;
}
};三数之和
先排序，然后从头寻找小于0的元素，在这个元素的后面和末端开始寻找和为0的两个元素，因为是有序的，所以如果和大于0得往左移动找小的，如果和小于0得往右移动找大的
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
if (nums[0] > 0)
return {};
vector<vector<int>> ans;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ans.push_back({nums[i], nums[left], nums[right]});
++left;
--right;
while (left < right && nums[left] == nums[left -1]) {
++left;
}
while (left < right && nums[right + 1] == nums[right]) {
--right;
}
} else if (sum > 0) {
--right;
} else {
++left;
}
}
}
return ans;
}
};接雨水
先找出最高的柱子，然后以开头和末尾两根柱子作为边界的高度，分别往最高处移动，如果边界碰到更矮的说明可以接水，碰到更高的说明边界可以更新
class Solution {
public:
int trap(vector<int>& height) {
int highest_index = 0, ans = 0;
int left_edge = height[0], right_edge = height[height.size() - 1];
int left = 1, right = height.size() - 2;
for (int i = 1; i < height.size(); ++i) {
if (height[i] > height[highest_index]) {
highest_index = i;
}
}
while (left < highest_index) {
if (left_edge > height[left]) {
ans += left_edge - height[left];
} else {
left_edge = height[left];
}
++left;
}
while (highest_index < right) {
if (right_edge > height[right]) {
ans += right_edge - height[right];
} else {
right_edge = height[right];
}
--right;
}
return ans;
}
};滑动窗口
无重复字符的最长子串
用两个指针记录无重复字符子串的起点和终点，移动终点，从起点开始遍历如果有字符和终点相同则更新起点
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
for (int begin = 0, end = 0; end < s.size(); ++end) {
for (int i = begin; i < end; ++i) {
if (s[i] == s[end]) {
begin = i + 1;
break;
}
}
ans = max(ans, end - begin + 1);
}
return ans;
}
};找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
异位词判断相同不一定需要排序，统计各个字符的个数看看是否相同即可，用一个滑动窗口统计窗口内字符的种类个数，移动的时候减去跑掉的字符加上新来的字符
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> answer;
int s_size = s.size(), length = p.size();
if (s_size < length) {
return {};
}
vector<int> son(26), target(26);
for (int i = 0; i < length; ++i) {
++son[s[i] - 'a'];
++target[p[i] - 'a'];
}
if (son == target) {
answer.emplace_back(0);
}
for (int i = 0; i < s_size - length; ++i) {
--son[s[i] - 'a'];
++son[s[i + length] - 'a'];
if (son == target) {
answer.emplace_back(i + 1);
}
}
return answer;
}
};子串
和为k的子数组
将前缀和记录下来，对应的出现次数也记录下来，因为0 k这里就有两个满足要求的子数组
遍历元素累加前缀和，判断前缀和-k是否出现过就行了
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0, prefix = 0;
unordered_map<int, int> hash;
hash[0] = 1;
for (auto& num : nums) {
prefix += num;
if (hash.find(prefix - k) != hash.end()) {
ans += hash[prefix - k];
}
++hash[prefix];
}
return ans;
}
};滑动窗口最大值
滑动窗口思想，用一个堆记录滑动窗口里面的最大值和索引，移动滑动窗口，如果堆顶的索引不在滑动窗口内就弹堆顶离开
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int>ans;
priority_queue<pair<int,int>>heap;
for(int i=0;i<k;++i)
heap.emplace(nums[i],i);
ans.push_back(heap.top().first);
for(int i=k;i<nums.size();++i){
heap.emplace(nums[i],i);
while(heap.top().second<=i-k)
heap.pop();
ans.push_back(heap.top().first);
}
return ans;
}
};最小覆盖子串
双指针+滑动窗口，覆盖子串即统计目标子串的字符种类和对应的数目，用一个指针标识满足要求的子串的起点，一个指针移动窗口，移动窗口的时候更新新来字符对应的数目减一，检查起点指针是否可以移动（起点字符对应的数目小于0），如果字符对应的数目减一后为0说明该类字符收集完成，如果所有类字符收集完成说明找到覆盖子串了
class Solution {
public:
string minWindow(string s, string t) {
int length=0,begin=0;
unordered_map<int, int> hash;
for (auto& c : t) {
++hash[c - 'a'];
}
int kinds = hash.size();
for (int i = 0, j = 0; j < s.size(); ++j) {
if (--hash[s[j] - 'a'] == 0) {
--kinds;
}
while (hash[s[i] - 'a'] < 0) {
++hash[s[i] - 'a'];
++i;
}
if (kinds == 0 &&(length==0||length > j - i + 1)) {
length=j-i+1;
begin=i;
}
}
return s.substr(begin,length);
}
};普通数组
最大子数组和
数组中每个元素都是一个子数组的结尾，dp[i]是以num[i]为结尾的最大子数组和，dp[i]要么是前一个子数组和加上当前元素，要么就是当前元素新开一个子数组，取决于这两个值哪个大
class Solution {
public:
int maxSubArray(vector<int> &nums) {
int *dp = new int[nums.size()];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
max = std::max(max, dp[i]);
}
return max;
}
};合并区间
先按左区排序，遍历区间，装第一个区间进入答案容器，判断答案容器最后一个区间的右区是否小于当前遍历区间的左区，是则不能合并是新区间加入容器，否则可以合并更新容器最后一个区间的右区
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>>ans;
std::sort(intervals.begin(),intervals.end());
for(auto&one:intervals){
if(ans.empty()||ans.back()[1]<one[0]) // 空或者可以不能合并
ans.push_back(one);
else
ans.back()[1]=max(ans.back()[1],one[1]); // 合并
}
return ans;
}
};轮转数组
首先让k=k%n去掉无效移动
方法一：
使用额外的空间直接对应赋值old[i]=new[(i+k)%n]，这样时间是O(n)的，空间是O(n)的
方法二：
原地移动，循环移动k次，每次就整体往后移动一格，用一个额外的变量作为缓存，这样时间是O(kn)的，空间是O(1)的
方法三：
考虑轮转的结果，向右移动k个位置的结果其实相当于整体翻转一次，然后0到k-1翻转一次，k到n-翻转一次的结果，向左移动的话则是k=n-k即可，这样每个元素被移动2次，时间复杂度为O(n)
class Solution {
public:
void rotate(vector<int> &nums, int k) {
auto reverse = [](vector<int> &nums, int begin, int end) -> void {
while (begin < end) {
swap(nums[begin++], nums[end--]);
}
};
k = k % nums.size();
reverse(nums, 0, nums.size() - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.size() - 1);
}
};除自身以外数组的乘积
238. 除自身以外数组的乘积 - 力扣（LeetCode）
要找除开本身以外其他元素的乘积，如果可以用除法的话，直接累积所有元素然后除以每个元素
不能用除法，可以用两个数组计算元素的前缀乘积和后缀乘积，然后相乘即可
只能用一个数组操作的话，可以先用这个数组记录前缀累积，然后再用一个变量记录后缀累积，用前缀累积乘以后缀累积就是答案
class Solution {
public:
vector<int> productExceptSelf(vector<int> &nums) {
vector<int> ans(nums.size());
ans[0] = 1;
for (int i = 1; i < nums.size(); ++i)
ans[i] = ans[i - 1] * nums[i - 1];
int suffix = 1;
for (int i = nums.size() - 1; i >= 0; --i) {
ans[i] = ans[i] * suffix;
suffix = suffix * nums[i];
}
return ans;
}
};缺失的第一个正数
要找出这个数组里面没有出现的最小的正数，最小的正数是1，n个元素的数组能够让答案最大为n+1，也就是位置0对应1，位置1对应2……的情况，所以答案的范围只会是[1, n+1]
对于一个数组来说，如果它的元素num[i]就等于索引i+1，也就是位置0对应1，位置1对应2……的情况，那么缺失的第一个正数就是不对应的位置索引+1
按照这样的对应关系重新整理一下数组，从0到n-1遍历，找到范围在1到n之间的num[i]，它正确的位置应该在num[i]-1，交换这两个的值
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for(int i=0;i<nums.size();++i){
while(nums[i]>0&&nums[i]<=nums.size()&&nums[i]!=nums[nums[i]-1]){
swap(nums[i],nums[nums[i]-1]);
}
}
for(int i=0;i<nums.size();++i){
if(nums[i]!=i+1){
return i+1;
}
}
return nums.size()+1;
}
};矩阵
矩阵置零
遍历二维数组，如果元素为0，记录对应的行和列
再次遍历矩阵，如果行或列之前被记录过，赋值为0
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
vector<bool> row(matrix.size(), false), column(matrix[0].size(), false);
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[0].size(); ++j)
if (matrix[i][j] == 0)
row[i] = column[j] = true;
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[0].size(); ++j)
if (row[i] || column[j])
matrix[i][j] = 0;
}
};螺旋矩阵
绕圈走，可以用四个变量记录边界，就沿着边界走，走完一个边界就缩一下
要注意不是方的情况，有可能走完一条或者一竖就应该结束了
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int left = 0, top = 0, right = matrix[0].size() - 1,
bottom = matrix.size() - 1;
size_t count = matrix.size() * matrix[0].size();
vector<int> ans;
while (ans.size() < count) {
for (int i = left; i <= right; ++i) {
ans.push_back(matrix[top][i]);
}
++top;
for (int i = top; i <= bottom; ++i) {
ans.push_back(matrix[i][right]);
}
--right;
if (ans.size() == count)
break;
for (int i = right; i >= left; --i) {
ans.push_back(matrix[bottom][i]);
}
--bottom;
for (int i = bottom; i >= top; --i) {
ans.push_back(matrix[i][left]);
}
++left;
}
return ans;
}
};旋转图像
可以先斜对角线翻转再上下翻转，也可以先上下翻转再主对角线翻转
先斜对角线翻转再上下翻转
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < n - i - 1; ++j)
swap(matrix[i][j], matrix[n - j - 1][n - i - 1]);
for (int i = 0; i < n / 2; ++i)
for (int j = 0; j < n; ++j)
swap(matrix[i][j], matrix[n - i - 1][j]);
}
};先上下翻转再主对角线翻转
class Solution {
public:
void rotate(vector<vector<int> > &matrix) {
int n = matrix.size();
for (int i = 0; i < n / 2; ++i)
for (int j = 0; j < n; ++j)
swap(matrix[i][j], matrix[n - i - 1][j]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
swap(matrix[i][j], matrix[j][i]);
}
};搜索二维矩阵 II
从右上角开始搜索，如果当前元素比目标小，那么说明目标只能存在下面矩阵，搜索范围往下压扁，如果当前元素比目标大，说明目标只能存在左边的矩阵里，搜索范围往左压窄
这样最多需要遍历n+m个元素就可以搜索完毕
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int n = matrix.size(), m = matrix[0].size(), x = 0, y = m - 1;
while (x < n && y >= 0) {
if (matrix[x][y] == target)
return true;
if (matrix[x][y] > target)
--y;
else
++x;
}
return false;
}
};链表
相交链表
记A链表=a+c，B链表=b+c，要找到c的起始节点
让一个指针走a+c+b，另一个指针走b+c+a，此时这两个指针都指向c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode *pa = headA, *pb = headB;
while (pa != pb) {
pa = pa ? pa->next : headB;
pb = pb ? pb->next : headA;
}
return pa;
}
};反转链表
先记录前一个节点和后一个节点的指针，然后把当前节点的后驱节点更新为前节点，继续操作后一个节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* cur) {
ListNode* prev = nullptr;
while (cur) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};回文链表
简单的可以取出来放到数组里面，然后从头尾一起走比较，这需要额外的空间
如果要原地比较，先用快慢指针找出中间节点，翻转后面一半节点，从中间和起始一起走比较
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> values;
ListNode* p = head;
while (p) {
values.push_back(p->val);
p = p->next;
}
for (int i = 0, j = values.size() - 1; i < j; i++, j--) {
if (values[i] != values[j])
return false;
}
return true;
}
};环形链表
用快慢指针走，如果有环两个指针会相遇，没环快指针能走完
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr)
return false;
ListNode* fast = head->next;
ListNode* slow = head;
while (fast != slow) {
if (fast == nullptr || fast->next == nullptr)
return false;
fast = fast->next->next;
slow = slow->next;
}
return true;
}
};环形链表 II
先用快慢指针判断有没有环，同时如果有环的话记录下快慢指针相遇的地方
假设从链表头到环入口距离为a，快慢指针相遇处距入口距离为b，那么慢指针走了a+b，而快指针走了2a+2b，记相遇处绕回到入口处距离为c，那么快指针多走了一圈（假设），即c+b，即a=c，此时让一个指针从链表头开始走c步，一个指针同时在相遇处走c步，那么他们会在入口相遇
实际上如果相遇，快指针比慢指针会多跑k圈（一圈就是b+c），此时慢指针走了a+b，快指针走了2（a+b），就会有2（a+b）=a+b+k（b+c）
可以算出来a=k（b+c）-b，就是a=（k-1）（b+c）+c
此时让一个指针从起点跑a步会到达入口处，一个指针从相遇处跑a步也就是几圈+c步也会到达入口处，此时他们相遇于入口
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode *slow = head, *fast = head;
do {
if (fast == nullptr || fast->next == nullptr)
return nullptr;
slow = slow->next;
fast = fast->next->next;
} while (fast != slow);
fast = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
};合并两个有序链表
创建一个头节点作为接头，然后同步遍历两个链表节点取较小的节点接上去直到某个链表为空，再把不为空的链表接上去
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode head{};
ListNode* cur = &head;
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2;
return head.next;
}
};两数相加
同步遍历两个链表，用一个数记录进位，用一个数记录和，链表到空了就当成0继续加起来，直到两个链表都遍历完并且用完进位
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode head{};
ListNode* cur = &head;
int carry = 0;
while (l1 || l2 || carry) {
int a = l1 == nullptr ? 0 : l1->val;
int b = l2 == nullptr ? 0 : l2->val;
int sum = a + b + carry;
cur->next = new ListNode(sum % 10);
cur = cur->next;
carry = sum / 10;
if (l1)
l1 = l1->next;
if (l2)
l2 = l2->next;
}
return head.next;
}
};删除链表的倒数第N个节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
链表倒数可以利用递归从最后一个开始往前数，到了该删的那个先记录后驱节点，然后释放本节点
再返回后驱节点接上
还可以用双指针的方法，记链表总个数为L，倒数第N个也就是正数第L-N个，用一个指针先跑到第N个节点，然后让另一个指针从起点开始跑，当前面一个指针跑到末尾时，它跑了L-N个节点，也就是后面一个节点跑了L-N个节点，即倒数第N个节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
int count = 0;
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == nullptr)
return head;
head->next = removeNthFromEnd(head->next, n);
++count;
if (count == n) {
ListNode* next = head->next;
delete head;
return next;
}
return head;
}
};两两交换链表中的节点
就先看两个，先取第二个的指针，递归颠倒第二个后面的节点，链接到第一个节点上，然后把第一个节点链接到第二个节点上，返回第二个节点指针
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr)
return head;
ListNode* next = head->next;
head->next = swapPairs(next->next);
next->next = head;
return next;
}
};随机链表的复制
非常妙的思路，用映射将旧链表的节点和新链表的节点一一对应起来，然后将新链表的节点串起来，对于random可以根据哈希表里面的对应找到新链表里面对应的节点，妙哉
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> hash;
Node* cur = head;
while (cur) {
hash[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while (cur) {
hash[cur]->next = hash[cur->next];
hash[cur]->random = hash[cur->random];
cur = cur->next;
}
return hash[head];
}
};排序链表
最快的方法是取出来放数组里面排序数组再装回去
原地排序的话可以使用归并排序，用快慢指针找到中间节点拆成两个链表，递归继续拆，拆到只有一个节点的链表，合并两个有序链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2) {
if (l1 == nullptr)
return l2;
if (l2 == nullptr)
return l1;
if (l1->val < l2->val) {
l1->next = merge(l1->next, l2);
return l1;
}
l2->next = merge(l1, l2->next);
return l2;
}
ListNode* findMidst(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* sortList(ListNode* left) {
if (left == nullptr || left->next == nullptr)
return left;
ListNode* midst = findMidst(left);
ListNode* right = midst->next;
midst->next = nullptr;
return merge(sortList(left), sortList(right));
}
};K个一组翻转链表
每K个一组里面翻转，先找出每一个组的头，翻转这一个组，然后将这一个组接到当前组的后面
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* cur, int k) {
ListNode* newHead = cur;
for (int i = 0; i < k; ++i) {
if (newHead == nullptr) {
return cur;
}
newHead = newHead->next;
}
ListNode* prev = reverseKGroup(newHead, k);
for (int i = 0; i < k; ++i) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};合并K个升序链表
方法一：每次取最小的一个节点出来返回，递归取更小的节点作为后驱节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
int min = INT_MAX, index = -1;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i] && lists[i]->val < min) {
min = lists[i]->val;
index = i;
}
}
if (index == -1)
return nullptr;
ListNode *head = lists[index];
lists[index] = lists[index]->next;
head->next = mergeKLists(lists);
return head;
}
};LRU缓存
双向链表存储key-value，哈希表存储key和链表节点指针
class LRUCache {
struct Node {
int key, value;
Node *prev, *next;
};
Node *head, *tail;
unordered_map<int, Node*> hash;
int capacity;
void moveToHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
public:
LRUCache(int capacity) {
this->capacity = capacity;
head = new Node{};
tail = new Node{};
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (hash.find(key) == hash.end()) {
return -1;
}
removeNode(hash[key]);
moveToHead(hash[key]);
return hash[key]->value;
}
void put(int key, int value) {
if (hash.find(key) == hash.end()) {
if (hash.size() == capacity) {
Node* node = tail->prev;
hash.erase(node->key);
removeNode(node);
delete node;
}
hash[key] = new Node{key, value, nullptr, nullptr};
} else {
hash[key]->value = value;
removeNode(hash[key]);
}
moveToHead(hash[key]);
}
};
二叉树
二叉树
一个节点有两个后驱节点，基本上二叉树的问题可以通过递归解决
二叉搜索树
左节点<父节点<右节点，二分查找快速定位数据，但当每次插入的元素为极值，二分搜索树退化成链表，查询从O(logn)降到O(n)，搜索树的中序遍历是有序序列
自平衡二叉搜索树
自己调整树的高度，使得左右子树高度差不超过1
红黑树
非严格平衡的二叉搜索树，查找O(logn)，根节点和叶子节点为黑，红节点的子节点为黑，简单路径上的黑节点数目相同
B树
自平衡的多叉搜索树，节点存储数据
B+树
自平衡的多叉搜索树，只有叶子节点存储数据，叶子节点之间构造双向链表
二叉树的前序遍历
递归遍历通用套路，只在访问元素和继续递归遍历子节点的顺序不同
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> ans;
void dfs(TreeNode* root) {
if (root == nullptr) {
return;
}
ans.emplace_back(root->val);
dfs(root->left);
dfs(root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};二叉树的中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> ans;
void dfs(TreeNode* root) {
if (root == nullptr) {
return;
}
dfs(root->left);
ans.emplace_back(root->val);
dfs(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};二叉树的后序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> ans;
void dfs(TreeNode* root) {
if (root == nullptr) {
return;
}
dfs(root->left);
dfs(root->right);
ans.emplace_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};二叉树的层序遍历
前序、中序、后序都是深度优先搜索，层序遍历是广度优先搜索，深度优先搜索一般通过栈或者递归实现，广度优先搜索一般通过队列实现
将起点放入队列，每一层遍历先记录队列中的元素个数，这是这一层需要遍历的个数，访问当前节点，出队，然后将子节点入队，直到队空
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr)
return {};
vector<vector<int>> ans;
queue<TreeNode*> level;
level.push(root);
while (!level.empty()) {
int levelSize = level.size();
vector<int> temp;
while (levelSize--) {
TreeNode* node = level.front();
level.pop();
temp.push_back(node->val);
if (node->left)
level.push(node->left);
if (node->right)
level.push(node->right);
}
ans.emplace_back(std::move(temp));
}
return ans;
}
};二叉树的最大深度
树的深度，往下遍历一次子节点深度就加一，取左右子节点较大的加一返回就行了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
翻转二叉树
把指向左右节点的指针交换就行了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};对称二叉树
递归解决，如果都空那么相等，否则有一个为空那么不相等，剩下就是都不为空，判断元素是否相等，接着递归判断左边的左子树是否等于右边的右子树，左边的右子树是否等于右边的左子树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) { return dfs(root, root); }
bool dfs(TreeNode* left, TreeNode* right) {
if (left == nullptr && right == nullptr) {
return true;
}
if (left == nullptr || right == nullptr) {
return false;
}
return left->val == right->val && dfs(left->left, right->right) &&
dfs(left->right, right->left);
}
};二叉树的直径
其实就是找两个子节点深度的最大和，去计算每个节点的深度，然后在过程中记录最大的和
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int ans = 0;
int dfs(TreeNode* root) {
if (root == nullptr)
return 0;
int left = dfs(root->left);
int right = dfs(root->right);
ans = max(ans, left + right);
return 1 + max(left, right);
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return ans;
}
};将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
通过取中间元素作为根节点，左半部分递归地构造左子树，右半部分递归地构造右子树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &nums) {
return build(nums, 0, nums.size() - 1);
}
TreeNode *build(vector<int> &nums, int left, int right) {
if (left > right)
return nullptr;
int root = (left + right) / 2;
return new TreeNode(nums[root], build(nums, left, root - 1), build(nums, root + 1, right));
}
};验证二叉搜索树
即左边的小于根小于右边的，不仅仅是这样，根必须得比左子树的都要大，比右子树的都要小，因此对于每个节点都需要小于某个值大于某个值
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
bool assist(TreeNode* root, long long low, long long high) {
if (root == nullptr)
return true;
if (root->val <= low || root->val >= high)
return false;
return assist(root->left, low, root->val) &&
assist(root->right, root->val, high);
}
bool isValidBST(TreeNode* root) {
return assist(root, LONG_LONG_MIN, LONG_LONG_MAX);
}
};
二叉搜索树中第K小的元素
230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）
二叉搜索树中序遍历的结果就是有序序列
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> nums;
void inOrder(TreeNode* root) {
if (root == nullptr)
return;
inOrder(root->left);
nums.push_back(root->val);
inOrder(root->right);
}
int kthSmallest(TreeNode* root, int k) {
inOrder(root);
return nums[k - 1];
}
};二叉树的右视图
即每一个深度都装一个最右边的节点，深度优先遍历右节点，根据已经装的节点数和深度判断这个深度有没有装节点
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> ans;
void dfs(TreeNode* root, int depth) {
if (root == nullptr)
return;
if (depth == ans.size())
ans.push_back(root->val);
dfs(root->right, depth + 1);
dfs(root->left, depth + 1);
}
vector<int> rightSideView(TreeNode* root) {
dfs(root, 0);
return ans;
}
};二叉树展开为链表
方法一：
要求链表顺序和二叉树的前序遍历顺序一样，那么可以先前序遍历放到容器里，然后根据遍历顺序把节点链接起来
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> assist;
void dfs(TreeNode* root) {
if (root == nullptr)
return;
assist.push_back(root);
dfs(root->left);
dfs(root->right);
}
void flatten(TreeNode* root) {
dfs(root);
for (int i = 0; i < int(assist.size()) - 1; i++) {
assist[i]->left = nullptr;
assist[i]->right = assist[i + 1];
}
}
};方法二：
还有一种空间复杂度为O(h)的，h为二叉树的高度，这是因为它看起来是O(1)的空间，实际上因为函数调用栈是O(h)的空间，反前序遍历，从前序遍历最后一个节点开始操作，记录前驱节点的指针
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
TreeNode* prev = nullptr;
void flatten(TreeNode* root) {
if (root == nullptr) {
return;
}
flatten(root->right);
flatten(root->left);
root->left = nullptr;
root->right = prev;
prev = root;
}
};从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
前序遍历是根在前面，然后是左子树，再是右子树，中序遍历是左子树-根-右子树，通过前序遍历可以找到根，在中序遍历里面确定根的位置后可以知道左子树的长度和右子树的长度，如此可以在前序遍历中找到左子树和右子树的根，如此递归下去
为了更快的找到中序遍历里面根的位置，可以用哈希表存储下来根对应的索引
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
unordered_map<int, int> index;
vector<int> preorder, inorder;
TreeNode* build(int pre_left, int pre_right, int in_left, int in_right) {
if (pre_left > pre_right)
return nullptr;
TreeNode* root = new TreeNode(preorder[pre_left]);
int in_root = index[preorder[pre_left]];
int left_size = in_root - in_left;
root->left =
build(pre_left + 1, pre_left + left_size, in_left, in_root - 1);
root->right =
build(pre_left + left_size + 1, pre_right, in_root + 1, in_root);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
this->inorder = inorder;
for (int i = 0; i < inorder.size(); i++)
index[inorder[i]] = i;
return build(0, preorder.size() - 1, 0, inorder.size() - 1);
}
};路径总和
要判断从根节点到叶子节点的路径和是否等于目标，可以每层减去节点值更新目标值，判断叶子节点值是否等于目标值
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return false;
}
if (root->left == nullptr && root->right == nullptr) {
return targetSum == root->val;
}
return hasPathSum(root->left, targetSum - root->val) ||
hasPathSum(root->right, targetSum - root->val);
}
};路径总和 II
要判断从根节点到叶子节点的路径和是否等于目标，可以每层减去节点值更新目标值，判断叶子节点值是否等于目标值，在这过程中记录下路径，注意回溯时pop即可
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int target, ans = 0;
unordered_map<long long, int> prefix;
void dfs(TreeNode* root, long long sum) {
if (root == nullptr)
return;
sum += root->val;
if (prefix.find(sum - target) != prefix.end())
ans += prefix[sum - target];
++prefix[sum];
dfs(root->left, sum);
dfs(root->right, sum);
--prefix[sum];
}
int pathSum(TreeNode* root, int targetSum) {
target = targetSum;
prefix[0] = 1;
dfs(root, 0);
return ans;
}
};路径总和 III
先用深度遍历记录每个节点到根的路径和，然后用哈希表记录前缀和出现的次数，两个前缀和之差就是节点到节点的路径和，要注意回溯时次数减一
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int target, ans = 0;
unordered_map<long long, int> prefix;
void dfs(TreeNode* root, long long sum) {
if (root == nullptr)
return;
sum += root->val;
if (prefix.find(sum - target) != prefix.end())
ans += prefix[sum - target];
++prefix[sum];
dfs(root->left, sum);
dfs(root->right, sum);
--prefix[sum];
}
int pathSum(TreeNode* root, int targetSum) {
target = targetSum;
prefix[0] = 1;
dfs(root, 0);
return ans;
}
};二叉树的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
递归查找两个节点的所在地，如果两个节点一个在root的左子树一个在右子树，说明root就是公共祖先，并且因为是递归，root就是最近的，如果不是，往左右子树递归的时候返回来空的，那说明最近公共祖先在非空的一侧，如果root就是两个节点之一，那么就直接返回
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left == nullptr)
return right;
if (right == nullptr)
return left;
return root;
}
};二叉树中的最大路径和
124. 二叉树中的最大路径和 - 力扣（LeetCode）
深度遍历计算每个节点的最大路径，然后记录左右两边和的最大值
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int ans = INT_MIN;
int dfs(TreeNode* root) {
if (root == nullptr)
return 0;
int left = max(0, dfs(root->left));
int right = max(0, dfs(root->right));
ans = max(ans, left + right + root->val);
return root->val + max(left, right);
}
public:
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
};图论
岛屿数量
遍历这个世界，如果是岛屿，那么从这里出发能到达的地方全部标记，继续遍历下一个没有标记的岛屿，这样可以得到岛屿数量
class Solution {
public:
int rows, columns;
vector<vector<char> > grid;
bool isValid(int x, int y) {
return x >= 0 && y >= 0 && x < rows && y < columns;
}
void dfs(int x, int y) {
if (isValid(x, y) == false || grid[x][y] != '1')
return;
grid[x][y] = '!';
dfs(x - 1, y);
dfs(x + 1, y);
dfs(x, y - 1);
dfs(x, y + 1);
}
int numIslands(vector<vector<char> > &grid) {
rows = grid.size();
columns = grid[0].size();
this->grid = move(grid);
int ans = 0;
for (int i = 0; i < rows; ++i)
for (int j = 0; j < columns; ++j)
if (this->grid[i][j] == '1') {
dfs(i, j);
++ans;
}
return ans;
}
};腐烂的橘子
污染，感染源会将周围的可感染的东西污染，就像一滴墨水滴入清水一样，层层扩散，求几层扩散后污染整个世界
先一次遍历，用一个队列存储所有的感染源并记录当前还没有被感染的数量，在每轮感染中取出队列的感染源进行污染操作，并将新污染的感染源入队，直到所有感染源用完或者没有可以感染的
class Solution {
public:
int rows, columns, ans = 0, fresh = 0;
vector<vector<int>> grid;
queue<pair<int, int>> source;
bool isValid(int x, int y) {
return x >= 0 && y >= 0 && x < rows && y < columns;
}
void pollute(int x, int y) {
if (isValid(x, y) && this->grid[x][y] == 1) {
this->grid[x][y] = 2;
source.emplace(x, y);
--fresh;
}
}
int orangesRotting(vector<vector<int>>& grid) {
rows = grid.size();
columns = grid[0].size();
this->grid = move(grid);
for (int i = 0; i < rows; ++i)
for (int j = 0; j < columns; ++j)
if (this->grid[i][j] == 1)
++fresh;
else if (this->grid[i][j] == 2)
source.emplace(i, j);
while (fresh > 0 && !source.empty()) {
int scale = source.size();
while (--scale >= 0) {
auto [x, y] = source.front();
pollute(x - 1, y);
pollute(x, y - 1);
pollute(x + 1, y);
pollute(x, y + 1);
source.pop();
}
++ans;
}
if (fresh > 0)
return -1;
return ans;
}
};课程表
这是一个判断拓扑有序的问题，看看会不会成环
用邻接表建立有向图，记录每个顶点的入度，把入度为0的入队列
入度为0的说明没有先修课程，取出来修，并将相连的节点的入度减一，说明先修课程已经修了一个了，再判断有没有新的课程可以修的入队
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int> > &prerequisites) {
vector<vector<int> > map(numCourses, vector<int>(numCourses));
vector<int> inDegree(numCourses);
for (auto must: prerequisites) {
int from = must[1], to = must[0];
++inDegree[to];
map[from][to] = 1;
}
queue<int> learned;
for (int i = 0; i < numCourses; ++i)
if (inDegree[i] == 0)
learned.emplace(i);
int pass = 0;
while (!learned.empty()) {
int passed = learned.front();
learned.pop();
pass++;
for (int i = 0; i < numCourses; ++i) {
if (map[passed][i]) {
--inDegree[i];
if (inDegree[i] == 0)
learned.emplace(i);
}
}
}
if (pass == numCourses)
return true;
return false;
}
};实现 Trie (前缀树)
208. 实现 Trie (前缀树) - 力扣（LeetCode）
前缀树是如何做到高效查找字符串的呢，先说单词查找树吧，一共就只有26个字母，先给节点结构
struct Node {
Node*next[26];
};这样存储字符串abc和abcd只会多一个d指向的节点，也就是相同的前缀用相同的节点，每一个字母会有26种后缀，因此有26个指针指向后缀节点，如果某节点指针为空，说明没有该字母后缀
如果26个指针都为空，说明该节点是末尾节点，但是我们可以增加一个布尔变量标记是否是结尾，而不需要每次遍历判断26个指针，但是反过来一个单词末尾节点的指针是可以不为空的像abc和abcd的c节点是结尾，但是指向d，所以这个结尾标记是需要的
struct Node {
vector<Node*>next;
bool end;
Node():next(26,nullptr),end(false){}
};插入字符串的时候，从头到尾安排单词的每个字母，如果不存在当前字母，为它创建一个新的节点
Node *tree;
void insert(string word) {
Node *node = tree;
for (char letter: word) {
letter -= 'a';
if (node->next[letter] == nullptr)
node->next[letter] = new Node();
node = node->next[letter];
}
node->end = true;
}为了判断是否是前缀和存在单词，可以写一个查找前缀的函数，如果前缀存在返回节点指针，代码基本和插入相同，不同的地方在于当不存在当前字母时说明没有该前缀，直接返回空
Node *isPrefix(string &prefix) {
Node *node = tree;
for (char letter: prefix) {
letter -= 'a';
if (node->next[letter] == nullptr)
return nullptr;
node = node->next[letter];
}
return node;
}
那么查找前缀就直接调用看看结果是不是空的，查找单词就先看前缀结果是不是空，不是空看看是不是单词结尾
bool search(string word) {
Node *result = isPrefix(word);
return result != nullptr && result->end;
}
bool startsWith(string prefix) {
return isPrefix(prefix) != nullptr;
}全部代码
class Trie {
struct Node {
vector<Node *> next;
bool end;
Node(): next(26, nullptr), end(false) {
}
};
Node *tree;
public:
Trie(): tree(new Node()) {
}
void insert(string word) {
Node *node = tree;
for (char letter: word) {
letter -= 'a';
if (node->next[letter] == nullptr)
node->next[letter] = new Node();
node = node->next[letter];
}
node->end = true;
}
Node *isPrefix(string &prefix) {
Node *node = tree;
for (char letter: prefix) {
letter -= 'a';
if (node->next[letter] == nullptr)
return nullptr;
node = node->next[letter];
}
return node;
}
bool search(string word) {
Node *result = isPrefix(word);
return result != nullptr && result->end;
}
bool startsWith(string prefix) {
return isPrefix(prefix) != nullptr;
}
};回溯
全排列
深度优先搜索寻找一种组合，标记访问过的元素，回溯取消标记，换元素继续深搜
class Solution {
public:
vector<bool> visited;
vector<vector<int> > ans;
void dfs(vector<int> &array, vector<int> &nums) {
if (array.size() == nums.size()) {
ans.push_back(array);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (visited[i] == false) {
visited[i] = true;
array.push_back(nums[i]);
dfs(array, nums);
array.pop_back();
visited[i] = false;
}
}
}
vector<vector<int> > permute(vector<int> &nums) {
visited.assign(nums.size(), false);
vector<int> array;
dfs(array, nums);
return ans;
}
};子集
方法一：
子集就是对于每个元素来说，要么选它要么不选它，用0和1来表示，n个元素就2的n次方个状态
可以从0数到2的n次方减一，左移再和1做与运算取它对应的位看看是不是1，是1就加上去
class Solution {
public:
vector<vector<int> > ans;
vector<vector<int> > subsets(vector<int> &nums) {
int n = nums.size();
for (int binary = 0; binary < 1 << n; ++binary) {
vector<int> son;
for (int i = 0; i < n; i++) {
if (binary >> i & i)
son.push_back(nums[i]);
}
ans.push_back(std::move(son));
}
return ans;
}
};方法二：
递归，对于一个子集来说，这个元素它要么不选，是一个子集，要么选，也是一个子集
class Solution {
public:
vector<vector<int> > ans;
vector<int> nums;
vector<int> array;
void dfs(int depth) {
if (depth == nums.size()) {
ans.push_back(array);
return;
}
array.push_back(nums[depth]);
dfs(depth + 1);
array.pop_back();
dfs(depth + 1);
}
vector<vector<int> > subsets(vector<int> &nums) {
this->nums = nums;
dfs(0);
return ans;
}
};电话号码的字母组合
组合的过程是一个长树的过程，可以用深度遍历实现，每一个数字对应的字符串都是一层，一种字母组合就是一条路径，当递归的深度达到层数就找到了一种字母组合
class Solution {
public:
string code[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;
string digits;
void dfs(string combine, int depth) {
if (depth == digits.size())
ans.push_back(std::move(combine));
else
for (auto &it: code[digits[depth] - '2'])
dfs(combine + it, depth + 1);
}
vector<string> letterCombinations(string digits) {
this->digits = digits;
if (digits.size() == 0)return {};
dfs("", 0);
return ans;
}
};组合总和
由于可以重复使用数字，所以不用标记已访问，直接深度搜索寻找所有组合累加求和直到大于等于目标结束
可以先从小到大排序一下这样可以更快的结束深搜
class Solution {
public:
vector<vector<int>> ans;
vector<int> an;
vector<int> candidates;
int target, sum = 0;
void dfs(int begin) {
if (sum == target) {
ans.push_back(an);
return;
} else if (sum > target)
return;
for (int i = begin; i < candidates.size(); ++i) {
sum += candidates[i];
an.push_back(candidates[i]);
dfs(i);
an.pop_back();
sum -= candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
this->candidates = candidates;
this->target = target;
dfs(0);
return ans;
}
};括号生成
n对括号说明要n个左括号和n个右括号，不同的组合可以通过每次尾加左括号或者右括号寻找，什么是有效的括号呢，那就是在尾加的时候右括号的数量不能超过左括号
class Solution {
public:
vector<string> ans;
void dfs(string an, int left, int right) {
if (left < 0 || left > right)
return;
if (left == 0 && right == 0) {
ans.push_back(std::move(an));
return;
}
dfs(an + '(', left - 1, right);
dfs(an + ')', left, right - 1);
}
vector<string> generateParenthesis(int n) {
dfs("", n, n);
return ans;
}
};单词搜索
遍历二维数组找到匹配的单词字符，然后往上下左右深度遍历，因为元素不能重复使用，所以访问过的元素直接修改成字符串结束符，访问完改回去
class Solution {
public:
string word;
int row, column;
vector<vector<char> > board;
bool dfs(int i, int j, int count) {
if (i >= row || j >= column || i < 0 || j < 0 || board[i][j] != word[count])
return false;
if (count == word.size() - 1)
return true;
board[i][j] = '\0';
++count;
bool next = dfs(i - 1, j, count) || dfs(i, j - 1, count) || dfs(i + 1, j, count) || dfs(i, j + 1, count);
board[i][j] = word[--count];
return next;
}
bool exist(vector<vector<char> > &board, string word) {
this->board = move(board);
this->word = move(word);
row = this->board.size();
column = this->board[0].size();
for (int i = 0; i < row; ++i)
for (int j = 0; j < column; ++j) {
if (dfs(i, j, 0))
return true;
}
return false;
}
};分割回文串
先写一个判断回文串的函数，然后深度搜索分割方案，比如aab，先判断a是不是回文串是的话此处分割往后继续判断a是不是回文串，继续判断b，然后这就是一个可行解，回溯判断aa回文串，分割再判断b
class Solution {
public:
vector<vector<string> > ans;
vector<string> an;
string s;
bool isPalindromes(int left, int right) {
while (left < right) {
if (s[left++] != s[right--])
return false;
}
return true;
}
void dfs(int i) {
if (i == s.size()) {
ans.push_back(an);
return;
}
for (int j = i; j < s.size(); ++j) {
if (isPalindromes(i, j)) {
an.push_back(s.substr(i, j - i + 1));
dfs(j + 1);
an.pop_back();
}
}
}
vector<vector<string> > partition(string s) {
this->s = move(s);
dfs(0);
return ans;
}
};N皇后
深度遍历，一层放一个，检查竖直方向、左右斜向上方向有无冲突，无冲突继续放下一层，回溯时移开皇后
class Solution {
public:
vector<vector<string> > ans;
vector<string> an;
int n;
bool isValid(int i, int j) {
for (int k = 0; k < i; ++k) // 竖直方向
if (an[k][j] == 'Q')
return false;
for (int x = i, y = j; x >= 0 && y >= 0; --x, --y) // 左斜向上
if (an[x][y] == 'Q')
return false;
for (int x = i, y = j; x >= 0 && y < n; --x, ++y) // 右斜向上
if (an[x][y] == 'Q')
return false;
return true;
}
void dfs(int level) {
if (level == n) {
ans.push_back(an);
return;
}
for (int i = 0; i < n; ++i) {
if (isValid(level, i)) {
an[level][i] = 'Q';
dfs(level + 1);
an[level][i] = '.';
}
}
}
vector<vector<string> > solveNQueens(int n) {
this->n = n;
an.assign(n, string(n, '.'));
dfs(0);
return ans;
}
};二分查找
搜索插入位置
要在一个有序数组里面查找一个元素的位置，就是要找第一个大于等于目标元素的位置，每次和中间位置元素进行比较，然后确定下一次的查找范围是在左半部分还是右半部分
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (right + left) >> 1;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
};搜索二维矩阵
从右上角开始查找，如果当前元素比目标小，说明应该在下面范围，矩阵压扁，如果当前元素比目标大，说明在左边范围，矩阵压扁，这样最多只需要遍历m+n个元素可以确定元素是否存在
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int x = 0, y = matrix[0].size() - 1, n = matrix.size();
while (x < n && y >= 0) {
if (matrix[x][y] == target)
return true;
if (matrix[x][y] < target)
++x;
else
--y;
}
return false;
}
};在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
先用二分找到元素的位置，然后往前找第一次出现的位置，往后找最后一次出现的位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int begin = -1, end = -1, left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
begin = end = mid;
while (begin > 0 && nums[begin - 1] == target)
--begin;
while (end + 1 < nums.size() && nums[end + 1] == target)
++end;
return {begin, end};
}
if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return {-1, -1};
}
};搜索旋转排序数组
方法一：技巧
因为题目说了元素不超过10000，那么就给第二段升序的部分加上10000，这样就是升序数组了，如果目标元素小于nums[0]说明它在第二段里面，也给它加上10000，不要误会循环加是O(n)的复杂度，只需要在比较的时候相加即可
class Solution {
public:
int search(vector<int> &nums, int target) {
int left = 0, right = nums.size() - 1;
if (target < nums[0])
target += 10000;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[0])
nums[mid] += 10000;
if (nums[mid] == target)
return mid;
if (target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
};方法二：
先不管，直接二分会得到一个有序数组和一个可能无序的数组，可以通过比较两端的数值大小区分
判断目标在不在有序数组里面，如果在就在有序数组里面二分，否则在无序数组里面二分回到初始问题但规模减少一半
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
};寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
假设第一个是最小的，从第二个开始二分查找，如果当前元素比第一个小，说明最小值要么就是当前这个，要么在它之前，二分查找的规模减半，如果比第一个大，说明最小值在后面，二分查找的规模减半
class Solution {
public:
int findMin(vector<int>& nums) {
int min = nums[0], left = 1, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[0]) {
min = nums[mid];
right = mid - 1;
} else {
left = mid + 1;
}
}
return min;
}
};寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
方法一：
在两个有序数组中在不合并的前提下寻找他们合并后的中位数，这个可以转换成寻找第k大的数
我们来看看这个第k大的数应该在什么地方，下标从0开始，那么a[i]前面有i个数，b[j]前面有j个数
那么如果i+j=k，那么说明a[i]和b[j]前面有k个数，如果a[i-1]<=b[j]并且b[j-1]<=a[i]，这就说明这k个数就是合并后有序的前k个数，那么第k大的数就是a[i-1]和b[j-1]之间的较大者
所以可以在a中二分查找符合条件的i，让j=k-i，如果b[j-1]>a[i]说明i的位置应该往后挪查找，否则往前查找
这里需要注意j的范围，因为b[j-1]和b[j]可以不存在，比如a=123，b=456，如果要找3，那么i=3，j=0，此时b[i-1]是不存在的，a[i]也是不存在的，因此0<=j<=m，即0<=k-i<=m，即i<=k，i>=k-m
这样可以二分确定第k大的范围，那么要找中位数，如果总长度是偶数，那么中位数就是中间两个数的平均值，否则就是中间那个数
class Solution {
public:
int findK(vector<int> &nums1, vector<int> &nums2, int k) {
int left = max(0, int(k - nums2.size())), right = min(k, int(nums1.size()));
while (left < right) {
int mid = (left + right) / 2;
if (nums2[k - mid - 1] > nums1[mid])
left = mid + 1;
else
right = mid;
}
return max(left ? nums1[left - 1] : INT_MIN, k - left ? nums2[k - left - 1] : INT_MIN);
}
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
int mn = nums1.size() + nums2.size();
if (mn & 1)
return findK(nums1, nums2, mn / 2 + 1);
return (findK(nums1, nums2, mn / 2) + findK(nums1, nums2, mn / 2 + 1)) / 2.0;
}
};方法二：
如果面试碰到这道题要你用二分查找，一般是面试官不想要你了， 说实话这道题上二分查找非常难，主要是当场手撕很难，我碰到这道题只会合并数组
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> nums;
nums.reserve(nums1.size() + nums2.size());
int i = 0, j = 0;
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] < nums2[j]) {
nums.emplace_back(nums1[i]);
++i;
} else {
nums.emplace_back(nums2[j]);
++j;
}
}
while (i < nums1.size()) {
nums.emplace_back(nums1[i]);
++i;
}
while (j < nums2.size()) {
nums.emplace_back(nums2[j]);
++j;
}
if (nums.size() & 1)
return nums[nums.size() / 2];
else
return (nums[nums.size() / 2] + nums[nums.size() / 2 - 1]) / 2.0;
}
};栈
有效的括号
如果是左括号压栈，如果是右括号，看栈顶元素是否与之匹配，如果不匹配或者空栈说明不对，如果匹配就弹栈，最后如果栈不是空的说明有没有匹配的括号，那也不对
class Solution {
public:
bool isValid(string s) {
stack<char> bracket;
for (auto &it: s) {
if (it == '[' || it == '{' || it == '(')
bracket.push(it);
else if (bracket.empty() || bracket.top() == '(' && it != ')' || bracket.top() == '[' && it != ']' ||
bracket.top() == '{' && it != '}')
return false;
else bracket.pop();
}
return bracket.empty();
}
};最小栈
多用一个栈存储每个状态下的最小值，先压一个上限入栈，然后元素入栈的时候比较一下和最小栈当前栈顶的大小，如果当前元素更小那么入最小栈，否则将栈顶再次入栈，这样可以记录下每个时期栈的最小值，元素出栈的时候最小栈也弹栈
class MinStack {
stack<int> Stack, Min;
public:
MinStack() {
Min.push(INT32_MAX);
}
void push(int val) {
Stack.push(val);
Min.push(min(Min.top(), val));
}
void pop() {
Stack.pop();
Min.pop();
}
int top() {
return Stack.top();
}
int getMin() {
return Min.top();
}
};字符串解码
主要会套娃，里面的会被反复重复，所以要先计算操作最里层的字符串
用栈记录要重复字符串的起始位置和重复次数，不需要记录要重复字符串的长度
遍历目标字符串，遇到数字先计算数字，遇到左括号就将字符串的起始位置和重复次数入栈
遇到正常字符就尾加上去，遇到右括号就需要开始重复字符串了，根据栈中的重复次数和字符串的起始位置进行重复
class Solution {
public:
string decodeString(string s) {
stack<pair<int, int>> szu;
string ans;
int num = 0;
for (auto &it: s) {
if (isdigit(it))
num = num * 10 + it - '0'; // 计算重复次数
else if (it == '[') {
szu.emplace(ans.size(), num); // 存储要重复的字符串的起始位置和重复次数
num = 0;
} else if (it == ']') {
string repeat = ans.substr(szu.top().first, ans.size() - szu.top().first); // 计算重复字符串
for (int i = 0; i < szu.top().second - 1; i++)
ans += repeat;
szu.pop();
} else
ans += it; // 存储重复字符串
}
return ans;
}
};柱状图中最大的矩形
要找最大的矩形这意味着需要将每个柱子都当作矩形的高算一次，问题是宽怎么算，每个柱子为高时，所形成的矩形的边界一定是比高要低的，否则就会是矩形的一部分
因此，每一个柱子作为矩形的高时，矩形的延申一定是碰到更高的或等高的柱子，如果碰到更低的，那么说明就到了矩形的边界
可以用一个单调递增栈，存储下标，一直记录更高或等高的柱子，一旦碰到低的柱子，此时栈顶可作为矩形的高，当前柱子作为右边界（不含），栈顶往下一个元素可作为左边界（不含），计算完成后弹出栈顶，这样可以以每个柱子的高度为矩形的高计算一次面积，且边界都是尽可能延申的
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
heights.insert(heights.begin(), 0);
heights.emplace_back(0);
stack<int> s;
for (int i = 0; i < heights.size(); ++i) {
while (s.empty() == false && heights[s.top()] > heights[i]) {
int h = heights[s.top()];
s.pop();
ans = max(ans, h * (i - s.top() - 1));
}
s.emplace(i);
}
return ans;
}
};每日温度
这实际上是在往右找第一个更大的数，用一个单调递减栈记录一直变小的数，一旦遇到比栈顶大的数，这就是答案，不停的弹栈比较栈顶就行了
class Solution {
public:
vector<int> dailyTemperatures(vector<int> &temperatures) {
vector<int> ans(temperatures.size()); // 默认为0
stack<int> index; // 存储下标
for (int i = 0; i < temperatures.size(); i++) {
while (!index.empty() && temperatures[index.top()] < temperatures[i]) { // 找到比前面温度高的
ans[index.top()] = i - index.top(); // 更新前面温度低的天数
index.pop();
}
index.push(i); // 将温度低的压入栈
}
return ans;
}
};堆
数组中的第K个最大元素
215. 数组中的第K个最大元素 - 力扣（LeetCode）
要找第K个最大的元素至少有三种方法
方法一：直接排序，时间复杂度O(nlogn)
方法二：建立容量n的大顶堆，然后弹k次，这里建堆的时间复杂度是O(n)，弹是O(klogn)
方法三：建立容量k的小顶堆，然后遍历数组，将比堆顶大的元素换进来，这样堆里就是k个最大的元素，堆顶就是k个最大的里面最小的，也就是说堆顶就是第k个最大，这里建堆的时间复杂度是O(k)，遍历过程的时间复杂度是O(nlogk)
建堆的问题，这里说的是从数组建堆，意味着需要从第一个有叶子节点的节点开始往下调整，调整的最大深度是logn，看起来时间复杂度是nlogn，但是由于深度由根节点到叶子节点变化是从logn到1，并且数量从1到n/2变化，所以实际上并不是n个logn相加，在算法导论中可以证明从数组建堆的时间复杂度是O(n)
如果是从0建堆，不断插入元素，插入元素会放到数组的最后一个位置然后向上调整，如果插入的是极值，要么就在叶子节点，O(1)的操作，要么在根节点，O(logn)的操作，假设最坏的情况，每次插入都需要调整到堆顶，那么插入n个元素的时间复杂度是O(nlogn)吗，不一定，因为向上调整logn的n是堆的容量，插入过程n是从1到n变化的，所以并不是n个logn相加，这里需要严格数学计算，嗯……实际上就是O(nlogn)@_@
class Solution {
int heapSize;
vector<int> data;
void adjustDown(int root) {
int next = root;
int left = 2 * root + 1;
int right = left + 1;
if (left < heapSize && data[left] < data[next]) {
next = left;
}
if (right < heapSize && data[right] < data[next]) {
next = right;
}
if (next != root) {
swap(data[next], data[root]);
adjustDown(next);
}
}
void buildHeap() {
for (int i = heapSize / 2 - 1; i >= 0; --i) {
adjustDown(i);
}
}
public:
int findKthLargest(vector<int>& nums, int k) {
data = move(nums);
heapSize = k;
buildHeap();
for (int i = k; i < data.size(); ++i) {
if (data[i] > data[0]) {
swap(data[i], data[0]);
adjustDown(0);
}
}
return data[0];
}
};直接用堆容器
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int i = 0; i < k; ++i)
minHeap.push(nums[i]);
for (int i = k; i < nums.size(); i++) {
if (minHeap.top() < nums[i]) {
minHeap.pop();
minHeap.push(nums[i]);
}
}
return minHeap.top();
}
};前K个高频元素
先统计元素出现的频率，然后建立容量为K的小顶堆，遍历数组，将出现频率更高的元素换掉堆顶
这样堆里就是K个出现频率最高的元素
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> hash;
for (auto& num : nums) {
++hash[num];
}
auto cmp = [&hash](int a, int b) { return hash[a] > hash[b]; };
priority_queue<int, vector<int>, decltype(cmp)> heap(cmp);
auto&& it = hash.begin();
for (int i = 0; i < k; ++i, ++it) {
heap.emplace(it->first);
}
for (; it != hash.end(); ++it) {
if (it->second > hash[heap.top()]) {
heap.pop();
heap.emplace(it->first);
}
}
vector<int> ans;
while (!heap.empty()) {
ans.emplace_back(heap.top());
heap.pop();
}
return ans;
}
};数据流的中位数
不停插入元素要求找到每个状态的中位数，用两个堆，把中位数左边的数记为left，右边的数记为right，一个大顶堆记录小于等于中位数的left，一个小顶堆记录大于中位数的right，数组长度为奇数时大顶堆比小顶堆多一个中位数，数组长度为偶数时，中位数就是两个堆顶的平均值
插入元素时，如果两个堆长度一样，先入小顶堆，这样小顶堆堆顶就是right里面最小的，弹出来放到left里面，此时left比right多一个数，并且left堆顶就是中位数，因为它比right都小，比left都大
如果left堆比right堆多一个数，那么先入left，那么left堆顶是left里面最大的数，弹出来送到right里面去，这样left和right数目相同，并且left堆顶元素小于right，right堆顶元素大于left，两个平均值就是中位数
注意优先队列默认是大顶堆
class MedianFinder {
public:
priority_queue<int> left;
priority_queue<int, vector<int>, greater<int> > right;
MedianFinder() {
}
void addNum(int num) {
if (left.size() == right.size()) {
right.push(num);
left.push(right.top());
right.pop();
} else {
left.push(num);
right.push(left.top());
left.pop();
}
}
double findMedian() {
return left.size() == right.size() ? (left.top() + right.top()) / 2.0 : left.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/贪心算法
买卖股票的最佳时机
其实就是找数组里面最大的差值，并且最小值要出现在最大值之前才有效
所以一次遍历记录有效的最大差值
class Solution {
public:
int maxProfit(vector<int>& prices) {
int min = prices[0], profit = 0;
for (int i = 1; i < prices.size(); i++) {
min = std::min(prices[i], min);
profit = max(profit, prices[i] - min);
}
return profit;
}
};跳跃游戏
记录能跳多远，看看能不能一直往后跳
遍历元素，当前能跳到最远的距离就是当前元素的索引加上元素本身
如果当前元素的索引大于之前能跳的最远距离，说明跳不到当前元素
class Solution {
public:
bool canJump(vector<int> &nums) {
int farthest = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i > farthest)
return false;
farthest = max(farthest, i + nums[i]);
}
return true;
}
};跳跃游戏 II
数组的元素表示可以跳的最大长度，保证可以跳到最后，求跳的最少的次数
所以要尽可能的往前跳，能跳多远就跳多远
不断更新当前位置可以跳跃到达的最远距离farthest，记录上次跳跃可以到达的位置foothold，当到这个位置的时候，跳跃计数，更新foothold为farthest
逻辑就是如果我到达了可以到达的最远位置，说明我跳了一次，可以理解为上一次跳跃完成，但是由于最后一次跳跃也是跳最远距离可能超过了最后一个位置，无法计数，所以干脆不计数，因为一开始0==0的时候就多计数了一次
class Solution {
public:
int jump(vector<int>& nums) {
int farthest = 0, foothold = 0, ans = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (i == foothold) {
++ans;
foothold = farthest;
}
}
return ans;
}
};划分字母区间
要将一个字符串划分为多个子串，要求每个字母只能出现在一个子串里面
所以一个字母如果它是一个子串的结尾的话那么它应该是这个子串中最后出现的，也就是这个子串的字母在之后都不会出现
可以先用一个数组记录每个字母的最后出现的位置，然后再次遍历字符串，记录当前子串中字母最后出现的位置，如果当前字母的位置就是该位置，那么此处应该分离
class Solution {
public:
vector<int> partitionLabels(string s) {
int last[26];
for (int i = 0; s[i]; ++i)
last[s[i] - 'a'] = i;
int begin = 0, end = 0;
vector<int> ans;
for (int i = 0; s[i]; ++i) {
end = max(end, last[s[i] - 'a']);
if (i == end) {
ans.push_back(end - begin + 1);
begin = end + 1;
}
}
return ans;
}
};动态规划
爬楼梯
斐波那契数列
class Solution {
public:
int climbStairs(int n) {
int a = 0, b = 1, c = 1;
while (--n) {
a = b;
b = c;
c = a + b;
}
return c;
}
};杨辉三角
算就行了
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans(numRows);
for (int i = 0; i < numRows; ++i) {
ans[i] = vector<int>(i + 1, 1);
for (int j = 1; j < i; ++j) {
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
}
}
return ans;
}
};打家劫舍
dp[i]是打劫的最大金额，如果要打劫第i间，那么第i-1间就不能打劫，dp[i]=nums[i-1]+dp[i-2]，如果不打劫第i间，那么dp[i]=dp[i-1]
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 1);
dp[1] = nums[0];
for (int i = 2; i <= n; ++i) {
dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]);
}
return dp[n];
}
};01背包
P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
原生01背包，背包空间有限，物体有大小和价值，每个物体只有一个，我也一直没有搞懂
当成套路用，一维动态规划，外层物体顺序，内层空间倒序
#include<iostream>
#include<vector>
int main(){
int volume,n;
std::cin>>volume>>n;
std::vector<int>values(n),weights(n),dp(volume+1);
for(int i=0;i<n;++i){
std::cin>>weights[i]>>values[i];
}
for(int i=0;i<n;++i){
for(int j=volume;j>=weights[i];--j){
dp[j]=std::max(dp[j],dp[j-weights[i]]+values[i]);
}
}
std::cout<<dp[volume];
}P1060 [NOIP2006 普及组] 开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
01背包问题， 背包空间（钱）有限，物体有大小和价值（单价乘以重要度），每个物体只有一个
一维动态规划，外层物体顺序，内层空间倒序
#include<iostream>
#include<vector>
int main(){
int volume,n;
std::cin>>volume>>n;
std::vector<int>values(n),weights(n),dp(volume+1);
for(int i=0;i<n;++i){
std::cin>>weights[i]>>values[i];
}
for(int i=0;i<n;++i){
for(int j=volume;j>=weights[i];--j){
dp[j]=std::max(dp[j],dp[j-weights[i]]+weights[i]*values[i]);
}
}
std::cout<<dp[volume];
}P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
01背包， 背包空间有限，物体有大小和价值（物体大小），每个物体只有一个
一维动态规划，外层物体顺序，内层空间倒序
#include<iostream>
#include<vector>
int main(){
int volume,n;
std::cin>>volume>>n;
std::vector<int>values(n),dp(volume+1);
for(int i=0;i<n;++i){
std::cin>>values[i];
}
for(int i=0;i<n;++i){
for(int j=volume;j>=values[i];--j){
dp[j]=std::max(dp[j],dp[j-values[i]]+values[i]);
}
}
std::cout<<volume-dp[volume];
}P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
寻找数组中元素组合的和是某个数的个数
#include<iostream>
#include<vector>
int main(){
int volume,n;
std::cin>>n>>volume;
std::vector<int>v(n),dp(volume+1);
for(int i=0;i<n;++i){
std::cin>>v[i];
}
dp[0]=1;
for(int i=0;i<n;++i){
for(int j=volume;j>=v[i];--j){
dp[j]=dp[j]+dp[j-v[i]];
}
}
std::cout<<dp[volume];
}分割等和子集
寻找数组中元素组合的和能否是某个数
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (auto& num : nums) {
sum += num;
}
if (sum & 1) {
return false;
}
int target = sum / 2;
vector<int> dp(target + 1);
dp[0] = 1;
for (auto& num : nums) {
for (int i = target; i >= num; --i) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
};完全背包
P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
原生完全背包
背包空间有限，物体有大小和价值，每个物体有无数个
同01背包，不同之处在于内层正序遍历
#include<iostream>
#include<vector>
int main(){
int volume,n;
std::cin>>volume>>n;
std::vector<long long>values(n),weights(n),dp(volume+1);
for(int i=0;i<n;++i){
std::cin>>weights[i]>>values[i];
}
for(int i=0;i<n;++i){
for(int j=weights[i];j<=volume;++j){
dp[j]=std::max(dp[j],dp[j-weights[i]]+values[i]);
}
}
std::cout<<dp[volume];
}零钱兑换
完全背包问题，物体无限个，最少几个填满背包
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 0x3fffffff);
dp[0]=0;
for (auto& coin : coins) {
for (int i = coin; i <= amount; ++i) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] == 0x3fffffff ? -1 : dp[amount];
}
};完全平方数
完全背包问题，和就是背包容量，完全平方数就是物品大小，价值就是个数
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, 0x3fffffff);
dp[0]=0;
for (int i = 0; i <= sqrt(n); ++i) {
for (int j = i * i; j <= n; ++j) {
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
};单词拆分
完全背包问题，背包是目标单词，物体是给的单词集合，考虑顺序需要外层遍历背包容量
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size() + 1);
dp[0] = true;
for (int i = 1; i <= s.size(); ++i) {
for (auto& word : wordDict) {
int n = word.size();
if (i >= n && s.substr(i - n, n) == word) {
dp[i] = dp[i] || dp[i - n];
}
}
}
return dp[s.size()];
}
};最长递增子序列
让dp[i]是以nums[i]为结尾的子序列最长递增长度，遍历nums[i]之前的元素，如果有比nums[i]小的，说明递增子序列可以延申
class Solution {
public:
int lengthOfLIS(vector<int> &nums) {
int ans = 0;
vector<int> dp(nums.size(), 1);
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j)
if (nums[j] < nums[i])
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
return ans;
}
};乘积最大子数组
都是整数所以乘积的绝对值会越来越大，所以需要记录累乘过程中的最小值和最大值，遇上负数最小值就会变成最大值，最大值就会变成最小值
class Solution {
public:
int maxProduct(vector<int>& nums) {
int ans = nums[0], Max = nums[0], Min = nums[0];
for (int i = 1; i < nums.size(); ++i) {
int dpMax = nums[i] * Max, dpMin = nums[i] * Min;
Max = max(nums[i], max(dpMax, dpMin));
Min = min(nums[i], min(dpMax, dpMin));
ans = max(Max, ans);
}
return ans;
}
};最长有效括号
定义dp[i]是以s[i]为结尾的子串的最长长度，显然s[i]必须是），那就会有两种情况，对于s[i]=），如果s[i-1]=（，说明dp[i]应该是dp[i-2]+2，考虑到是...()这样的，那么状态转移方程为dp[i] = dp[i - 2]+ 2
如果是...))这样的，也就是s[i-1]=），也就是套壳状态，那么s[i]必定需要对应一个s[j]=（来闭环，那么j是多少呢，j和i之间应该隔了dp[i-1]个，那么j应该等于i-dp[i-1]-1，dp[i]就应该是dp[i-1]+2再加上dp[j-1]，那么状态转移方程应该为 dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
class Solution {
public:
int longestValidParentheses(string s) {
vector<int> dp(s.size());
int ans = 0;
for (int i = 1; i < s.size(); ++i) {
if (s[i] == ')') {
if (s[i - 1] == '(')
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(')
dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
ans = max(ans, dp[i]);
}
return ans;
}
};多维动态规划
不同路径
当前格子的路径数等于上方格子的路径数加上左边格子的路径数
最左边一束和最上边一横路径数都是1
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1));
for (int i = 1; i < m; ++i)
for (int j = 1; j < n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
return dp[m - 1][n - 1];
}
};最小路径和
到达当前格子的路径和要么是加上从上面格子来的，要么是加上左边格子来的，取这两个方向来的较小者就行了
对于最左边的和最上边的没有两个方向，直接累加一个方向的
class Solution {
public:
int minPathSum(vector<vector<int> >& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 1; i < m; ++i) {
grid[i][0] += grid[i - 1][0];
}
for (int i = 1; i < n; ++i) {
grid[0][i] += grid[0][i - 1];
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}
};最长回文子串
dp[i][j]表示字符串s[i,j]是不是回文字符串，取决于s[i]是否等于s[j]并且dp[i+1][j-1]为真或者i和j之间没有或者只有一个字符
由于dp[i][j]需要dp[i+1][j-1]，所以需要从左下角开始往右上角遍历
class Solution {
public:
string longestPalindrome(string s) {
int begin = 0, length = 0, n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
if (s[i] == s[j] && (j <= i + 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (length < j - i + 1) {
begin = i;
length = j - i + 1;
}
}
}
}
return s.substr(begin, length);
}
};最长公共子序列
记dp[i][j]是两个字符串的前i个和前j个子串的最长公共子序列（LCS）的长度，如果此刻遍历到的两个字符是相同的，那么dp[i][j]就应该等于dp[i-1][j-1]+1，否则应该是dp[i-1][j]和dp[i][j-1]的较大者
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>>dp(text1.size()+1,vector<int>(text2.size()+1));
for(int i=1;i<=text1.size();i++){
for(int j=1;j<=text2.size();j++){
if(text1[i-1]==text2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[text1.size()][text2.size()];
}
};编辑距离
定义dp[i][j]是将word1[0:i-1]转换成word2[0:j-1]所使用的最少操作数
如果word1[i-1]等于word2[j-1]，那么说明dp[i][j]=dp[i-1][j-1]，不需要操作，否则的话：
要么替换，操作数加一，变成上面的情况，当前这两个字符相等了，即dp[i][j]=dp[i-1][j-1]+1
要么插入，那么需要将word1[0:i-1]转换成word2[0:j-2]，即dp[i][j]=dp[i][j-1]+1
要么删除，那么需要将word1[0:i-2]转换成word2[0:j-1]，即dp[i][j]=dp[i-1][j]+1
取决于它们三个哪个最小，当然word中有一个为空的情况所需要的操作次数都是另一个的长度
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int> > dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; ++i)dp[i][0] = i;
for (int i = 0; i <= n; ++i)dp[0][i] = i;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (word1[i - 1] == word2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
return dp[m][n];
}
};技巧
只出现一次的数字
要找的元素只出现一次，其他出现两次，相同的数字相异或的结果是0，与0异或的结果是自己，运算的顺序不影响结果
所以将所有元素进行异或，结果就是只出现一次的元素
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans=0;
for(auto&num:nums){
ans^=num;
}
return ans;
}
};多数元素
由于要找的元素超过了总数的一半，所以如果让不同的元素同归于尽的话，最后会剩下要找的元素
遍历数组的元素，记录当前存活元素的数目，碰到异类就一换一，如果死光了就换下一个元素
class Solution {
public:
int majorityElement(vector<int>& nums) {
int count = 1;
int mode = nums[0];
for (int i = 1; i < nums.size(); ++i) {
if (mode == nums[i]) {
++count;
} else if (--count == 0) {
mode = nums[i];
count = 1;
}
}
return mode;
}
};颜色分离
元素固定的情况下记住各个元素的个数按顺序赋值就行了
class Solution {
public:
void sortColors(vector<int>& nums) {
int zeroes = 0, ones = 0;
for (auto& num : nums) {
if (num == 0) {
++zeroes;
} else if (num == 1) {
++ones;
}
}
for (int i = 0; i < nums.size(); ++i) {
if (i < zeroes) {
nums[i] = 0;
} else if (i < zeroes + ones) {
nums[i] = 1;
} else {
nums[i] = 2;
}
}
}
};下一个排列
就是要找这堆数字的组合中下一个较大的数，比如1243的下一个排列是1324，即让这个组合数变大一些，同时变大的程度尽可能的小
于是可以从右边开始找到一个比后面更小的数，如1243中的2，再找到一个比2更大的数，如1243中的3，把他们两个交换，得到1342，然后再将42翻转一下，因为42肯定是倒序的，正序后会变大，这样组合出来的数就会变大一些
可以发现2是不满足nums[i]>=nums[i+1]的数，而3是比2大的第一个右边的数，交换他们意味着得到更大的数，同时将后面部分翻转是为了得到更小的数
如果找不到2，即是4321这样的数，那直接翻转
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int small = nums.size() - 2;
while (small >= 0 && nums[small] >= nums[small + 1]) {
--small;
}
if (small >= 0) {
int big = nums.size() - 1;
while (nums[big] <= nums[small]) {
--big;
}
swap(nums[small], nums[big]);
}
reverse(nums.begin() + small + 1, nums.end());
}
};寻找重复数
n+1个数的范围在[1,n]，如果以值为下标作为链表指针，没有重复的数也能成环，有重复的数就是这个环有一个数可以由多个地方到达，也就是环有一个入口，这个入口就是重复的数
如nums[1]=3,nums[4]=3，3就是入口
用快慢指针必会在环里相遇，假设起点到入口的距离是a，入口到相遇的地方距离是b，相遇的地方继续往前走到入口的距离是c，如果相遇，那么快指针比慢指针会多跑k圈（一圈就是b+c），此时慢指针走了a+b，快指针走了2（a+b），就会有2（a+b）=a+b+k（b+c）
可以算出来a=k（b+c）-b，就是a=（k-1）（b+c）+c
此时让一个指针从起点跑a步会到达入口处，一个指针从相遇处跑a步也就是几圈+c步也会到达入口处，此时他们相遇于入口
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » 【Leetcode热题100】C++ 题解
发表评论 取消回复