Posts

LeetCode 排序 题目 56 合并区间 按照间隔的起始进行排序，判断下一个间隔的起始是否大于前一个间隔的末尾，如果大于的话就把之前的间隔加入结果数组，否则继续扩展当前的间隔。 class Solution { public: vector<vector<int>> merge(vector<vector<int>> &intervals) { vector<vector<int>> res; int n = intervals.size(); if (n == 0) return res; sort(intervals.begin(), intervals.end(), [](vector<int> const &v1, vector<int> const &v2) { return v1[0] < v2[0]; }); int start = intervals[0][0], end = intervals[0][1]; for (int i = 1; i < n; ++i) { if (intervals[i][0] > end) { res.push_back(vector<int>{start, end}); start = intervals[i][0]; } end = max(end, intervals[i][1]); } res.push_back(vector<int>{start, end}); return res; } }; 179 最大数 先把数字转换为字符串，然后自定义类似于字典序的排序规则 s1 + s2 > s2 + s1 进行排序。 ...

LeetCode 堆 题目 215 数组中的第 K 个最大元素 最简单的堆的应用。 class Solution { public: int findKthLargest(vector<int> &nums, int k) { priority_queue<int, vector<int>, greater<>> heap; for (auto &m:nums) { if (heap.size() < k || m > heap.top()) heap.push(m); if (heap.size() > k) heap.pop(); } return heap.top(); } }; 347 前 K 个高频元素 先遍历一次统计出数组中各个元素出现的次数，再用一个大根堆将前 k 个高频元素保存下来，最后再将这些元素依次 pop 出来存入结果数组。时间复杂度是 O(n)，空间复杂度是 O(n)。 class Solution { public: vector<int> topKFrequent(vector<int> &nums, int k) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> freq; unordered_map<int, int> count; vector<int> res(k, 0); for (auto &m:nums) ++count[m]; for (auto &c:count) { freq.push(pair<int, int>(c.second, c.first)); if (freq.size() > k) freq.pop(); } for (int i = 0; i < k; ++i) { pair<int, int> p = freq.top(); freq.pop(); res[i] = p.second; } return res; } }; 451 根据字符出现频率排序 用一个大根堆保存每个字符出现的频率，然后依次将原字符串覆盖即可。 ...

LeetCode DFS 题目 26 删除排序数组中的重复项 用两个指针 len 和 i 分别表示没有重复的项的下标与遍历数组的下标，将没有重复的项拷贝到 nums[len] 下然后 ++len 即可。 class Solution { public: int removeDuplicates(vector<int>& nums) { int count = 0, len = 1, n = nums.size(); if (n == 0) return 0; for (int i = 1; i < n; ++i) { if (nums[i] == nums[i - 1]) continue; nums[len] = nums[i]; ++len; } return len; } }; 80 删除排序数组中的重复项 II 用两个指针 len 和 i 分别表示没有最多重复 2 次的项的下标与遍历数组的下标，将重复数小于等于 1 的项拷贝到 nums[len] 下然后 ++len 即可。 class Solution { public: int removeDuplicates(vector<int>& nums) { int count = 0, len = 1, n = nums.size(); if (n == 0) return 0; for (int i = 1; i < nums.size(); ++i) { if (nums[i] == nums[i - 1]) { if (count > 0) continue; ++count; } else count = 0; nums[len] = nums[i]; ++len; } return len; } }; 922 按奇偶排序数组 II 用两个下标 i 和 j 分别表示偶数位和奇数位的下标，如果偶数位下标对应的数不是偶数那么将其与奇数位下标对应的数不是奇数的数进行交换。 ...

LeetCode DFS 题目 78 子集 典型的回溯，找出所有可能情况。 class Solution { vector<vector<int>> res; public: vector<vector<int>> subsets(vector<int> &nums) { res = vector<vector<int>>(1, vector<int>()); vector<int> curr; DFS(nums, 0, curr); return res; } void DFS(vector<int> &nums, int idx, vector<int> &curr) { for (int i = idx; i < nums.size(); ++i) { curr.push_back(nums[i]); res.push_back(curr); DFS(nums, i + 1, curr); curr.pop_back(); } } }; 733 图像渲染 从给定的 image[sr][sc] 开始 DFS 或 BFS，将相邻的值相同的点的值全部修改为 newColor，注意要判断给定的 image[sr][sc] 是否等于 newColor，否则如果不使用额外空间的 visited 数组记录已经访问过的点的话会造成死循环栈溢出。 ...

LeetCode 并发 题目 1114 按序打印 C++ mutex class Foo { mutex lock1, lock2; public: Foo() { lock1.lock(); lock2.lock(); } void first(function<void()> printFirst) { printFirst(); lock1.unlock(); } void second(function<void()> printSecond) { lock1.lock(); printSecond(); lock1.unlock(); lock2.unlock(); } void third(function<void()> printThird) { lock2.lock(); printThird(); lock2.unlock(); } }; C++ condition_variable class Foo { int i; mutex mut; condition_variable con_var1, con_var2; public: Foo() : i(1) { } void first(function<void()> printFirst) { unique_lock<mutex> lock(mut); printFirst(); ++i; con_var1.notify_one(); } void second(function<void()> printSecond) { unique_lock<mutex> lock(mut); con_var1.wait(lock, [this]() { return i == 2; }); printSecond(); ++i; con_var2.notify_one(); } void third(function<void()> printThird) { unique_lock<mutex> lock(mut); con_var2.wait(lock, [this]() { return i == 3; }); printThird(); } }; C++ atomic class Foo { atomic_int i; public: Foo() : i(1) { } void first(function<void()> printFirst) { printFirst(); ++i; } void second(function<void()> printSecond) { while (i != 2) {} printSecond(); ++i; } void third(function<void()> printThird) { while (i != 3) {} printThird(); i = 1; } }; C++ promise class Foo { promise<void> pro1, pro2; public: Foo() { } void first(function<void()> printFirst) { printFirst(); pro1.set_value(); } void second(function<void()> printSecond) { pro1.get_future().wait(); printSecond(); pro2.set_value(); } void third(function<void()> printThird) { pro2.get_future().wait(); printThird(); } }; 1115 交替打印FooBar C++ mutex class FooBar { private: int n; mutex mut1, mut2; public: FooBar(int n) { this->n = n; mut2.lock(); } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { mut1.lock(); printFoo(); mut2.unlock(); } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { mut2.lock(); printBar(); mut1.unlock(); } } }; C++ condition_variable class FooBar { private: int m, n; mutex mut; condition_variable con_var1, con_var2; public: FooBar(int n) : n(n), m(0) { } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { unique_lock<mutex> lock(mut); con_var1.wait(lock, [&]() { return m == 0; }); printFoo(); ++m; con_var2.notify_one(); } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { unique_lock<mutex> lock(mut); con_var2.wait(lock, [&]() { return m == 1; }); printBar(); m = 0; con_var1.notify_one(); } } }; C++ atomic class FooBar { private: int n; atomic_int m; public: FooBar(int n) : n(n), m(0) { } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { while (m != 0) {} printFoo(); m = 1; } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { while (m != 1) {} printBar(); m = 0; } } }; C++ promise class FooBar { private: int n; vector<promise<void>> pros1, pros2; public: FooBar(int n) : n(n) { for (int i = 0; i < n; ++i) { pros1.push_back(promise<void>()); pros2.push_back(promise<void>()); } } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { if (i != 0) pros1[i - 1].get_future().wait(); printFoo(); pros2[i].set_value(); } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { pros2[i].get_future().wait(); printBar(); pros1[i].set_value(); } } }; 1116 打印零与奇偶数 C++ mutex class ZeroEvenOdd { private: int m, n; mutex mut_zero, mut_odd, mut_even; public: ZeroEvenOdd(int n) { this->m = 1; this->n = n; mut_odd.lock(); mut_even.lock(); } void zero(function<void(int)> printNumber) { for (int i = 0; i < n; ++i) { mut_zero.lock(); printNumber(0); if (this->m % 2 == 1) mut_odd.unlock(); else mut_even.unlock(); } } void even(function<void(int)> printNumber) { for (int i = 0; i < n / 2; ++i) { mut_even.lock(); printNumber(this->m); ++this->m; mut_zero.unlock(); } } void odd(function<void(int)> printNumber) { for (int i = 0; i < (n + 1) / 2; ++i) { mut_odd.lock(); printNumber(this->m); ++this->m; mut_zero.unlock(); } } }; 1117 H2O 生成 C++ condition variable class H2O { int m = 1; mutex mut; condition_variable con_var; public: void hydrogen(function<void()> releaseHydrogen) { unique_lock<mutex> lock(mut); con_var.wait(lock, [&]() { return m % 3 != 0; }); ++m; releaseHydrogen(); con_var.notify_all(); } void oxygen(function<void()> releaseOxygen) { unique_lock<mutex> lock(mut); con_var.wait(lock, [&]() { return m % 3 == 0; }); ++m; releaseOxygen(); con_var.notify_all(); } };